An Additive Combinatorics Approach Relating Rank to Communication Complexity

DOI10.1145/2629598zbMath1321.68271arXiv1111.5884OpenAlexW1985006965MaRDI QIDQ5501927

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

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

zbMATH Keywords

communication complexityadditive combinatoricspolynomial Freiman-Ruzsa conjecturelow-rank matricesapproximate dualitylog-rank conjecture

Mathematics Subject Classification ID

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

Related Items

From Affine to Two-Source Extractors via Approximate Duality ⋮ Around the log-rank conjecture ⋮ 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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Equivalence of polynomial conjectures in additive combinatorics
• A probabilistic technique for finding almost-periods of convolutions
• On conjectures of Graffiti
• Complexity measures of sign matrices
• A new proof of Szemerédi's theorem for arithmetic progressions of length four
• On rank vs. communication complexity
• On the Bogolyubov-Ruzsa lemma
• On Sums of Generating Sets in ℤ₂ⁿ
• Communication is Bounded by Root of Rank
• SETS WITH SMALL SUMSET AND RECTIFICATION
• From Affine to Two-Source Extractors via Approximate Duality
• A Note on Freĭman's Theorem in Vector Spaces
• Freiman's Theorem in Finite Fields via Extremal Set Theory
• Learning Complexity vs Communication Complexity
• An equivalence between inverse sumset theorems and inverse conjectures for theU³norm
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
• A Bound for the Chromatic Number of a Graph
• Rank and chromatic number of a graph
• Communication Complexity
• From affine to two-source extractors via approximate duality
• New bounds for matching vector families