pdf icon
Volume 4 (2008) Article 7 pp. 137-168
Norms, XOR Lemmas, and Lower Bounds for Polynomials and Protocols
Received: July 24, 2007
Published: November 18, 2008
Download article from ToC site:
[PDF (451K)]    [PS (615K)]    [PS.GZ (161K)]
[Source ZIP]
Keywords: XOR lemma, direct product, lower bound, polynomial over GF(2), multiparty protocol, communication complexity, correlation, norm, Gowers norm, generalized inner product, small-bias, mod m, explicit construction
ACM Classification: F.2.3
AMS Classification: 68Q17

Abstract: [Plain Text Version]

$ \newcommand{\rb}[1]{\left( #1 \right)} %Round \DeclareMathOperator{\exponential}{exp} \newcommand{\eps}{\epsilon} $

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 $\eps \leq 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 $\exponential\rb{-m/4^d}$. No XOR lemma was known even for $d=2$.
  • For $c$-bit $k$-party protocols, the correlation drops to $2^c \cdot \eps^{m/2^k}$. No XOR lemma was known for $k \geq 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 $\eps \leq 1/2$ with either of the above models, we obtain the following bounds on the probability of computing $m$ independent instances of $f$ correctly:

  • For polynomials over $GF(2)$ of degree $d$ we again obtain a bound of $\exponential\rb{-m/4^d}$.
  • For $c$-bit $k$-party protocols we obtain a bound of $2^{-\Omega(m)}$ in the special case when $\eps \leq \exponential\rb{-c \cdot 2^k}$.

We also use the norms to give improved lower bounds or simplified proofs of known lower bounds in these models. In particular we give a new proof that the $\text{Mod}_m$ function on $n$ bits, for odd $m$, has correlation at most $\exponential(-n/4^d)$ with degree-$d$ polynomials over $GF(2)$.