Communication lower bounds using directional derivatives

DOI10.1145/2488608.2488725MaRDI QIDQ5495864zbMATH OpenOpenAlexFDO

Authors Alexander A. Sherstov

Publication date 7 August 2014

Published in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2488608.2488725

zbMATH Keywords

directional derivativesmultiparty communication complexitypolynomial approximationquantum communication complexityset disjointness problem

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Communication lower bounds using directional derivatives
• Lower bounds on communication complexity
• scientific article; zbMATH DE number 4068270
• Lower bounds in communication complexity
• Communication lower bounds via critical block sensitivity
• Communication lower bounds via critical block sensitivity
• Lower bounds on communication complexity in distributed computer networks
• Lower bounds for one-way probabilistic communication complexity
• Communication complexity of convex optimization

Cited in

(10)

• Information complexity and applications.
• Simulation theorems via pseudo-random properties
• The multiparty communication complexity of set disjointness
• Hellinger volume and number-on-the-forehead communication complexity
• Communication lower bounds via critical block sensitivity
• The power of asymmetry in constant-depth circuits
• Lifting Theorems for Equality
• A nearly optimal lower bound on the approximate degree of \(\mathrm{AC}^0\)
• The polynomial method strikes back: tight quantum query bounds via dual polynomials
• Communication lower bounds using directional derivatives

This page was built for publication: Communication lower bounds using directional derivatives

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