Communication lower bounds using directional derivatives

DOI10.1145/2629334MaRDI QIDQ5501937zbMATH OpenOpenAlexFDO

Authors 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

directional derivativespolynomial approximationmultiparty 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)

Recommendations

• Communication lower bounds using directional derivatives
• Simplified lower bounds on the multiparty communication complexity of disjointness
• The multiparty communication complexity of set disjointness
• The multiparty communication complexity of set disjointness
• Near-optimal bounds on the bounded-round quantum communication complexity of disjointness

Cites work

• scientific article; zbMATH DE number 5568623 (Why is no real title available?)
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 1775389 (Why is no real title available?)
• scientific article; zbMATH DE number 5485573 (Why is no real title available?)
• scientific article; zbMATH DE number 3314813 (Why is no real title available?)
• A counterexample to strong parallel repetition
• A separation of NP and conp in multiparty communication complexity
• A strong direct product theorem for corruption and the multiparty communication complexity of disjointness
• A strong direct product theorem for disjointness
• A user's guide to measure theoretic probability
• AN INVERSE THEOREM FOR THE GOWERS $U^3(G)$ NORM
• An information statistics approach to data stream and communication complexity
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Asymptotics in statistics. Some basic concepts.
• Boolean derivatives on cellular automata
• Communication Complexity
• Disjointness is hard in the multiparty number-on-the-forehead model
• Finite field models in additive combinatorics
• Lower bounds for local versions of dimension reductions
• Lower bounds in communication complexity based on factorization norms
• Multilinear polynomials modulo composites
• Multiparty Communication Complexity and Threshold Circuit Size of AC^0
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• On complexity of computation of partial derivatives of Boolean functions realized by Zhegalkin polynomials
• On the degree of Boolean functions as real polynomials
• On the distributional complexity of disjointness
• On the power of small-depth threshold circuits
• One-way multiparty communication lower bound for pointer jumping with applications
• Pseudo-Boolean optimization
• Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
• Separating AC\(^0\) from depth-2 majority circuits
• The BNS lower bound for multi-party protocols is nearly optimal
• The NOF multiparty communication complexity of composed functions
• The Probabilistic Communication Complexity of Set Intersection
• The complexity of Boolean functions in different characteristics
• The cost of the missing bit: Communication complexity with help
• The multiparty communication complexity of set disjointness
• The pattern matrix method
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity

Cited in

(19)

• Separation of unbounded-error models in multi-party communication complexity
• On multiparty communication with large versus unbounded error
• The hardest halfspace
• Algorithmic Polynomials
• Rectangles are nonnegative juntas
• Interactive Information Complexity
• Simplified lower bounds on the multiparty communication complexity of disjointness
• Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$
• Communication lower bounds using directional derivatives
• Near-optimal bounds on the bounded-round quantum communication complexity of disjointness
• Interactive information complexity
• scientific article; zbMATH DE number 7650118 (Why is no real title available?)
• The pattern matrix method
• Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
• Sampling on the sphere by mutually orthogonal subspaces
• Approximate Degree in Classical and Quantum Computing
• Simultaneous multiparty communication protocols for composed functions
• The multiparty communication complexity of set disjointness
• The Simultaneous Communication of Disjointness with Applications to Data Streams

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 Q5501937)