Today we prove the Goldreich-Levin theorem.
1. Goldreich-Levin Theorem
We use the notation
Theorem 1 (Goldreich and Levin) Let be a permutation computable in time . Suppose that is an algorithm of complexity such that
Then there is an algorithm of complexity at most such that
Last time we proved the following partial result.
where is an unknown string.
Then there is an algorithm that runs in time and makes oracle queries into and, with probability at least , outputs .
This gave us a proof of a variant of the Goldreich-Levin Theorem in which the right-hand-side in (2) was . We could tweak the proof Lemma 2 so that the right-hand-side of (4) is , leading to proving a variant of the Goldreich-Levin Theorem in which the right-hand-side in (2) is also .
We need, however, the full Goldreich-Levin Theorem in order to construct a pseudorandom generator, and so it seems that we have to prove a strengthening of Lemma 2 in which the right-hand-side in (4) is .
Unfortunately such a stronger version of Lemma 2 is just false: for any two different we can construct an such that
so no algorithm can be guaranteed to find given an arbitrary function such that , because need not be uniquely defined by .
We can, however, prove the following:
where is an unknown string, and is given.
Then there is an algorithm that runs in time and makes oracle queries into and, with probability at least , outputs a set such that and .
The Goldreich-Levin Theorem is an easy consequence of Lemma 3. The Goldreich-Levin algorithm has other interpretations (an algorithm that learns the Fourier coefficients of , an algorithm that decodes the Hadamard code is sub-linear time) and various applications outside cryptography.