Communication Lower Bounds Using Directional Derivatives

DOI10.1145/2629334zbMath1321.68289OpenAlexW1989966214MaRDI QIDQ5501937

Alexander A. Sherstov

Publication date: 14 August 2015

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

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

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

The Simultaneous Communication of Disjointness with Applications to Data Streams, Interactive Information Complexity, Approximate Degree in Classical and Quantum Computing, Breaking the Minsky--Papert Barrier for Constant-Depth Circuits, Interactive Information Complexity, Near-Optimal Bounds on the Bounded-Round Quantum Communication Complexity of Disjointness, Unnamed Item, Unnamed Item, Algorithmic Polynomials, The hardest halfspace, Rectangles Are Nonnegative Juntas, Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$, The Multiparty Communication Complexity of Set Disjointness, Unnamed Item, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The NOF multiparty communication complexity of composed functions
• One-way multiparty communication lower bound for pointer jumping with applications
• An information statistics approach to data stream and communication complexity
• Disjointness is hard in the multiparty number-on-the-forehead model
• The complexity of Boolean functions in different characteristics
• On the power of small-depth threshold circuits
• Pseudo-Boolean optimization
• The cost of the missing bit: Communication complexity with help
• Boolean derivatives on cellular automata
• Lower bounds for local versions of dimension reductions
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• On the distributional complexity of disjointness
• The BNS lower bound for multi-party protocols is nearly optimal
• On the degree of Boolean functions as real polynomials
• On complexity of computation of partial derivatives of Boolean functions realized by Zhegalkin polynomials
• Asymptotics in statistics. Some basic concepts.
• A strong direct product theorem for corruption and the multiparty communication complexity of disjointness
• A User's Guide to Measure Theoretic Probability
• A strong direct product theorem for disjointness
• A Counterexample to Strong Parallel Repetition
• The Pattern Matrix Method
• Separating ${AC}^0$ from Depth-2 Majority Circuits
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
• The Probabilistic Communication Complexity of Set Intersection
• Communication Complexity
• Strong Direct Product Theorems for Quantum Communication and Query Complexity
• Multiparty Communication Complexity and Threshold Circuit Size of AC^0
• The multiparty communication complexity of set disjointness
• Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
• AN INVERSE THEOREM FOR THE GOWERS $U^3(G)$ NORM
• Lower bounds in communication complexity based on factorization norms