The XOR Lemma -- A Quarter Century of Proofs

COMPUTER SCIENCE/DISCRETE MATH II
Topic:The XOR Lemma -- A Quarter Century of Proofs
Speaker:Avi Wigderson
Affiliation:School of Mathematics, Institute for Advanced Study
Date:Tuesday, January 27
Time/Room:10:30am - 12:30pm/S-101

Amplifying the difficulty of a somewhat hard function is a central technique in complexity, cryptography and pseudorandomness. By far the most common method of amplification is by repetition - asking to compute the original function in many independent inputs (and return all answers, or some combination thereof. e.g. their XOR). The fact that the new function is much harder than the original received many different proofs since Yao's original statement in 1982. Each proof has certain advantage over the others in different contexts. I will attempt to describe a few of these, and discuss their utilities.