REVISITING THE XOR LEMMA

I have just posted this report, which contains two previous reports, the counterexample to the dream xor lemma and the simple proof using majority, together with a new proof which appears to improve the parameters of all previous proofs of the xor lemma. Specifically, if a function has correlation epsilon with circuits of size S, the xor of two copies has correlation about epsilon square with circuits of size about S times epsilon square. By contrast, it seems to me that all previous proofs lost at least epsilon to the four in circuit size, and some also had a dependence on N. This loss arose from the need to estimate the final correlation, as is evident, for example, in Levin’s proof. The proof with the hard core set incurs this loss for similar reasons.

The new proof in the report does not do this estimate. Instead, it uses an object which I call BMA for bounded mean amplifier. It is a function that, given iid variables with a small mean returns a variable whose mean is amplified. Majority is a decent BMA but doesn’t quite get to the square of the correlation. A randomized variant of majority does get you that. The function is very similar to what’s used, for example, in Levin’s proof and, I’m sure, in many other places, but as far as I can tell, the analysis is different. I also find it simpler.