Yao’s XOR lemma

Yao’s XOR lemma states that if circuits of size compute a Boolean function correctly on at most a fraction of inputs, then for every , circuits of size at most compute the XOR of on independent inputs with probability at most . The lemma is attributed to Yao and conventionally cited to Yao82a; the bound in this form follows from the hard-core lemma — Imp95a.

Hardness of a Boolean function

For and , is -hard for size if every circuit of size at most satisfies

A -hard function is predicted with advantage at most over a uniform guess. The -wise XOR of is on .

Hard-core lemma

If is -hard for size , then for every there is a set of density such that every circuit of size satisfies — Imp95a.

XOR lemma

Let have density and satisfy for every circuit of size at most . Then for every , every circuit of size less than satisfies

With the hard-core lemma, and , so is -hard for size once , a threshold that is . Deriving the XOR lemma from a hard-core set is due to Imp95a.

The bound is proved as follows. With probability no lies in . Otherwise let be the first index with ; conditioned on and on the other inputs, is uniform on . Fixing and the other inputs to their best values, and hard-wiring the XOR of their values under , turns into a circuit of size at most for on , which is correct with probability at most — Imp95a.

Direct products

The XOR lemma amplifies the hardness of computing a predicate. For inverting a function the corresponding statement is a direct product: if on is weakly one-way, with a polynomial such that every efficient inverter fails with probability at least for all sufficiently large , then for independent blocks is one-way (Weak OWF ⇒ OWF) — Yao82a.

Notes

  • The XOR-lemma reduction above is non-uniform: it fixes the other inputs and their values of inside the circuit (uniform and non-uniform adversaries) — standard. The direct-product reduction is uniform: its inverter samples the other blocks and evaluates on them itself — Gol01.
  • The information-theoretic lemma also called the XOR lemma, used for simultaneously hardcore bits, is a different statement: it bounds the distance from uniform of a distribution on in terms of the largest bias of its nonempty parities — standard.