Yao's XOR lemma states that for every function f:{0, 1}^ k→{0, 1}, if f has hardness 2/3 for
P/poly (meaning that for every circuit C in P/poly, Pr [C (X)= f (X)]≤ 2/3 on a uniform input X),
then the task of computing f (X₁)⊕…⊕ f (X_t) for sufficiently large t has hardness 1/2+ ε for
P/poly.

Yao's XOR lemma states that for every function f:{0, 1} k→{0, 1}, if f has hardness 2/3 for
P/poly (meaning that for every circuit C in P/poly, Pr [C (X)= f (X)]≤ 2/3 on a uniform input X),
then the task of computing f (X 1)⊕…⊕ f (X t) for sufficiently large t has hardness 1 2+ ϵ for
P/poly. Known proofs of this lemma cannot achieve ϵ= 1 k ω (1), and even for ϵ= 1 k, we do
not know how to replace P/poly by AC0 [parity](the class of constant depth circuits with the
gates {and, or, not, parity} of unbounded fan-in). Grinberg, Shaltiel and Viola (FOCS …