Communication is Bounded by Root of Rank

DOI10.1145/2724704zbMath1426.68132arXiv1306.1877OpenAlexW2282727044MaRDI QIDQ3177758

Shachar Lovett

Publication date: 2 August 2018

Published in: Journal of the ACM, Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1306.1877

zbMATH Keywords

communication complexitylog rank conjecturelog-rank conjecture

Mathematics Subject Classification ID

Related Items (13)

Near-Optimal Upper Bound on Fourier Dimension of Boolean Functions in Terms of Fourier Sparsity ⋮ Alternation, sparsity and sensitivity: bounds and exponential gaps ⋮ The augmentation property of binary matrices for the binary and Boolean rank ⋮ Around the log-rank conjecture ⋮ Approximate nonnegative rank is equivalent to the smooth rectangle bound ⋮ Unnamed Item ⋮ Fourier Sparsity of GF(2) Polynomials ⋮ On the structure of Boolean functions with small spectral norm ⋮ Unnamed Item ⋮ A generalization of a theorem of Rothschild and van Lint ⋮ A generalization of a theorem of Rothschild and van Lint ⋮ An Additive Combinatorics Approach Relating Rank to Communication Complexity ⋮ Upper bounds on communication in terms of approximate rank

Uses Software

• SuLQ

Cites Work

• Unnamed Item
• Unnamed Item
• Efficient algorithms for privately releasing marginals via convex relaxations
• The Geometry of Differential Privacy: The Small Database and Approximate Cases
• Faster Algorithms for Privately Releasing Marginals
• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
• Privately Releasing Conjunctions and the Statistical Query Barrier
• On the geometry of differential privacy
• Interactive privacy via the median mechanism
• The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
• Lower Bounds in Differential Privacy
• Iterative Constructions and Private Data Release
• Characterizing the sample complexity of private learners
• Faster private release of marginals on small databases
• Bounds on the Sample Complexity for Private Learning and Private Data Release
• Differential Privacy and the Fat-Shattering Dimension of Linear Queries
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• New Efficient Attacks on Statistical Disclosure Control Mechanisms
• Collusion-secure fingerprinting for digital data
• On the complexity of differentially private data release
• Advances in Cryptology – CRYPTO 2004
• Answering n _{2+o(1)} counting queries with differential privacy is hard
• Theory of Cryptography

This page was built for publication: Communication is Bounded by Root of Rank