Theory of Computing
-------------------
Title : Norms, XOR Lemmas, and Lower Bounds for Polynomials and Protocols
Authors : Emanuele Viola and Avi Wigderson
Volume : 4
Number : 7
Pages : 137-168
URL : http://www.theoryofcomputing.org/articles/v004a007
Abstract
--------
This paper presents a unified and simple treatment of
basic questions concerning 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 epsilon
\leq 1/2 with any of these models, then the correlation
of the parity of its values on m independent instances
drops exponentially with m. More specifically:
(i) For polynomials over GF(2) of degree d, the correlation
drops to exp(-m/4^d). No XOR lemma was known even
for d=2.
(ii) For c-bit k-party protocols, the correlation drops
to 2^c epsilon^{m/2^k}. No XOR lemma was known for
k \ge 3 parties.
Another contribution in this paper is a general
derivation of direct product lemmas from XOR lemmas.
In particular, assuming that $f$ has correlation at
most $\epsilon \leq 1/2$ with any of the above models,
we obtain the following bounds on the probability of
computing $m$ independent instances of $f$ correctly:
(i) For polynomials over GF(2) of degree d we again
obtain a bound of exp(-m/4^d).
(ii) For $c$-bit $k$-party protocols we obtain a bound
of 2^{-\Omega(m)} in the special case when
epsilon \leq exp(-c 2^k).
We also use the norms to give improved (or just
simplified) lower bounds in these models. In
particular we give a new proof that the
Mod_m function on n bits, for odd m, has
correlation at most exp(-n/4^d) with
degree-d polynomials over GF(2).