This paper presents a unified and simple treatment of basic questions concern- ing two computational models: multiparty communication complexity and polynomials over GF(2). The key is the use of (known) norms on Boolean functions, which capture their proximity to each of these models (and are closely related to property testers of this proximity). The main contributions are new XOR lemmas. We show that if a Boolean function has correlation at most e 1/2 with either of these models, then the correlation of the parity of its values on m independent instances drops exponentially with m. More specifically: • For polynomials over GF(2) of degree d, the correlation drops to exp m/4 d . No
['Emanuele Viola', 'Avi Wigderson']
Norms, XOR lemmas, and lower bounds for polynomials and protocols