The Pattern Matrix Method
Author:
- Alexander A. SherstovASAlexander A. Sherstov
- 1 January 2011
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 40 (6) , 1969-2000
Abstract
We develop a novel technique for communication lower bounds, the pattern matrix method. Specifically, fix an arbitrary function $f: \{0,1\}^n \to\{0,1\}$, and let $A_f$ be the matrix whose columns are each an application of f to some subset of the variables $x_1,x_2,\ldots,x_{4n}.$ We prove that $A_f$ has bounded-error communication complexity $\Omega(d),$ where d is the approximate degree of $f.$ This result remains valid in the quantum model, regardless of prior entanglement. In particular, it gives a new and simple proof of Razborov's breakthrough quantum lower bounds for disjointness and other symmetric predicates. We further characterize the discrepancy, approximate rank, and approximate trace norm of $A_f$ in terms of well-studied analytic properties of $f,$ broadly generalizing several recent results on small-bias communication and agnostic learning. The method of this paper has also enabled important progress in multiparty communication complexity.
Keywords
This publication has 55 references indexed in Scilit:
- Learning DNF in time 2Õ(n1/3)Journal of Computer and System Sciences, 2004
- Quantum communication complexity of symmetric predicatesIzvestiya: Mathematics, 2003
- On the computational power of depth-2 circuits with threshold and modulo gatesTheoretical Computer Science, 1997
- Inclusion-exclusion: Exact and approximateCombinatorica, 1996
- Fourier analysis for probabilistic communication complexitycomputational complexity, 1995
- Perceptrons, PP, and the polynomial hierarchycomputational complexity, 1994
- On the degree of boolean functions as real polynomialscomputational complexity, 1994
- The expressive power of voting polynomialsCombinatorica, 1994
- Majority gates vs. general weighted threshold gatescomputational complexity, 1992
- DUALITY OF CONVEX FUNCTIONS AND EXTREMUM PROBLEMSRussian Mathematical Surveys, 1968