Revisiting the XOR lemmaResearch Paper
Yao's XOR lemma is a basic hardness-amplification result in complexity theory: if a Boolean function has correlation at most with every circuit of size , then the XOR of independent copies of has correlation about with circuits of size close to (Goldreich–Nisan–Wigderson 1995). It is used throughout pseudorandomness,…