Hard-core Set Theorem: Magic of Average Case Complexity

Suppose you are trying to build a circuit using limited number of AND, OR, NOT gates to compute some boolean function f over inputs in {0,1}n. But the function is such that every circuit with the above limit on its resources fails to compute f correctly on a small fraction of the inputs, i.e. the function is 'hard' for circuits of this given size.

In the above case, two things might be happening:

a) All the circuits that you are trying out are failing for different sets of inputs, and intuitively, there should be functions for which no particular input is harder than any particular other input, per se.

b) There can be one small set H hidden in the input set which is extremely hard to compute by any circuit, and on that set H, no circuit can do any better than guessing f randomly.

Impagliazzo's hardcore set lemma is 'one bit of magic in complexity theory' which says that it is always the second case, as if the hardness of the function is concentrated on a small 'hardcore' set H inside the input space. I will state and prove this result in the talk.