Next: On Constructing 1-1 One-way
Up: The First 1.5 Years
Previous: Honest Verifier vs Dishonest
A fundamental lemma of Yao states that computational weak-unpredictability
of functions gets amplified if the results of several independent instances
are XOR-ed together.
This work provides an exposition of three alternative
proofs of Yao's Lemma, where the first one is due to Levin,
the second one to Impagliazzo, and the third one is new.
Comments:
Authored by O. Goldreich, N. Nisan and A. Wigderson. Appeared in
ECCC, TR95-050, 1995.
Oded Goldreich
2003-07-30