Communication lower bounds using directional derivatives

DOI10.1145/2488608.2488725zbMath1293.68154OpenAlexW2009405883MaRDI QIDQ5495864

Alexander A. Sherstov

Publication date: 7 August 2014

Published in: Proceedings of the forty-fifth 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

polynomial approximationdirectional derivativesmultiparty communication complexityquantum communication complexityset disjointness problem

Mathematics Subject Classification ID

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

Related Items (8)

Hellinger volume and number-on-the-forehead communication complexity ⋮ Communication Lower Bounds via Critical Block Sensitivity ⋮ The Power of Asymmetry in Constant-Depth Circuits ⋮ A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$ ⋮ Information complexity and applications. ⋮ Simulation theorems via pseudo-random properties ⋮ Lifting Theorems for Equality ⋮ Unnamed Item

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