The Impagliazzo Hard-Core-Set Theorem

This note was originally taken from: https://lucatrevisan.wordpress.com/2007/11/06/the-impagliazzo-hard-core-set-theorem/

The Impagliazzo hard-core set theorem is one of the bits of magic of complexity theory. Say you have a function \(g:\{0,1\}^n\to\{0,1\}\) such that every efficient algorithm makes errors at least \(1\%\) of the times when computing \(g\) on a random input. (We’ll think of \(g\) as exhibiting a weak form of average-case complexity.) Clearly, different algorithms will fail on a different \(1\%\) of the inputs, and it seems that, intuitively, there should be functions for which no particular input is harder than any particular other input, per se. It’s just that whenever you try to come up with an algorithm, some set of mistakes, dependent on the algorithmic technique, will arise.

As a good example, think of the process of generating \(g\) at random, by deciding for every input \(x\) to set \(g(x)=1\) with probability \(99\%\) and \(g(x)=0\) with probability \(1\%\). (Make the choices independently for different inputs.) With very high probability, every efficient algorithm fails with probability at least about \(1\%\), but, if we look at every efficiently recognizable large set \(H\), we see that \(g\) takes the value \(1\) on approximately \(99\%\) of the elements of \(H\), and so the trivial algorithm that always outputs \(1\) has a pretty good success probability.

Consider, however, the set \(H\) of size \(2^{n+1}/100\) that you get by taking the \(\approx 2^n/100\) inputs \(x\) such that \(g(x)=0\) plus a random sample of \(2^n/100\) inputs \(x\) such that \(g(x)=1\). Then we can see that no efficient algorithm can compute \(g\) on much better than \(50\%\) of the inputs of \(H\). This is the highest form of average-case complexity for a boolean function: on such a set \(H\) no algorithm does much better in computing \(g\) than an algorithm that makes a random guess.

The Impagliazzo hard-core theorem states that it is always possible to find such a set \(H\) where the average-case hardness is “concentrated.” Specifically, it states that if every efficient algorithm fails to compute \(g\) on a \(\geq \delta\) fraction of inputs, then there is a set \(H\) of size \(\geq \delta 2^n\) such that every efficient algorithm fails to compute \(g\) on at least a \(\frac{1}{2}-\epsilon\) fraction of the elements of \(H\). This is true for every \(\epsilon,\delta\), and if “efficient” is quantified as “circuits of size \(s\)” in the premise, then “efficient” is quantified as “circuits of size \(\text{poly}(\epsilon,\delta)\)” in the conclusion.

The example of the biased random function given above implies that, if one wants to prove the theorem for arbitrary \(g\), then the set \(H\) cannot be efficiently computable itself. (The example does not forbid, however, that \(H\) be efficiently computable given oracle access to \(g\), or that a random element of \(G\) be samplable given a sampler for the distribution \((x,g(x))\) for uniform \(x\).)

A number of proofs of the hard core theorem are known, and connections have been found with the process of boosting in learning theory and with the construction and the decoding of certain error-correcting codes. Here is a precise statement.

Using the “finitary ergodic theoretic” approach of iterative partitioning, we (Omer Reingold, Madhur Tulsiani, Salil Vadhan and I) are able to prove the following variant.

The difference is that \(H\) is now an efficiently recognizable set (which is good), but we are not able to derive the same strong average-case complexity of \(g\) in \(H\) (which, as discussed as the beginning, is impossible in general). Instead of proving that a “random guess algorithm” is near-optimal on \(H\), we prove that a “fixed answer algorithm” is near-optimal on \(H\). That is, instead of saying that no algorithm can do better than a random guess, we say that no algorithm can do better than either always outputting \(0\) or always outputting \(1\). Note that this conclusion is meaningless if \(g\) is, say, always equal to \(1\) on \(H\), but in our construction we have that \(g\) is not exceedingly biased on \(H\), and if \(\epsilon < \delta/2\), say, then the conclusion is quite non-trivial.

[Update: constructing \(H'\) is somewhat more complicated than we originally thought, the details are in the paper.]

Coming up next, the proof of the “constructive hard core set theorem” and my attempt at explaining what the techniques have to do with “finitary ergodic theory.”