An additive combinatorics approach relating rank to communication complexity

DOI10.1145/2629598MaRDI QIDQ5501927zbMATH OpenOpenAlexFDO

Authors Eli Ben-Sasson, Shachar Lovett, Noga Ron-Zewi

Publication date 14 August 2015

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1111.5884, https://escholarship.org/uc/item/8m94p9zk

zbMATH Keywords

additive combinatoricsapproximate dualitycommunication complexitylog-rank conjecturelow-rank matricespolynomial Freiman-Ruzsa conjecture

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05)

Abstract: For a $0,1$-valued matrix $M$ let $mCC(M)$ denote the deterministic communication complexity of the boolean function associated with $M$. The log-rank conjecture of Lov'{a}sz and Saks [FOCS 1988] states that $mCC(M)leqlo{g}^c(mrank(M))$ for some absolute constant $c$ where $mrank(M)$ denotes the rank of $M$ over the field of real numbers. We show that $mCC(M)leqccdotmrank(M)/logmrank(M)$ for some absolute constant $c$, assuming a well-known conjecture from additive combinatorics known as the Polynomial Freiman-Ruzsa (PFR) conjecture. Our proof is based on the study of the "approximate duality conjecture" which was recently suggested by Ben-Sasson and Zewi [STOC 2011] and studied there in connection to the PFR conjecture. First we improve the bounds on approximate duality assuming the PFR conjecture. Then we use the approximate duality conjecture (with improved bounds) to get the aforementioned upper bound on the communication complexity of low-rank martices, where this part uses the methodology suggested by Nisan and Wigderson [Combinatorica 1995].

Recommendations

• En route to the log-rank conjecture: new reductions and equivalent formulations
• On the ``log rank-conjecture in communication complexity
• The log rank conjecture for modular communication complexity
• scientific article; zbMATH DE number 1405679

Cites work

• A Bound for the Chromatic Number of a Graph
• A new proof of Szemerédi's theorem for arithmetic progressions of length four
• A Note on Freĭman's Theorem in Vector Spaces
• A probabilistic technique for finding almost-periods of convolutions
• Additive combinatorics
• Almost k-wise vs. k-wise independent permutations, and uniformity for general group actions
• An equivalence between inverse sumset theorems and inverse conjectures for the \(U^{3}\) norm
• Communication Complexity
• Complexity measures of sign matrices
• Equivalence of polynomial conjectures in additive combinatorics
• Finite field models in additive combinatorics
• Freiman's theorem in finite fields via extremal set theory
• From affine to two-source extractors via approximate duality
• From affine to two-source extractors via approximate duality
• scientific article; zbMATH DE number 1315276 (Why is no real title available?)
• Learning complexity vs communication complexity
• Low-degree tests at large distances
• New bounds for matching vector families
• On conjectures of Graffiti
• On rank vs. communication complexity
• On sums of generating sets in Z₂^n
• On the Bogolyubov-Ruzsa lemma
• Rank and chromatic number of a graph
• SETS WITH SMALL SUMSET AND RECTIFICATION
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity

Cited in

(12)

• Still another rank determination of set intersection matrices with an application in communication complexity
• Matrix rank and communication complexity
• From affine to two-source extractors via approximate duality
• scientific article; zbMATH DE number 1405679 (Why is no real title available?)
• On the structure of the spectrum of small sets
• A generalization of a theorem of Rothschild and van Lint
• A generalization of a theorem of Rothschild and van Lint
• Around the log-rank conjecture
• Upper bounds on communication in terms of approximate rank
• Efficient randomized strong 2-source non-malleable extractor for any linear min-entropy
• Quantum and classical communication complexity of permutation-invariant functions
• Testing sumsets is hard

This page was built for publication: An additive combinatorics approach relating rank to communication complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5501927)