Communication lower bounds using directional derivatives

DOI10.1145/2629334zbMATH Open1321.68289OpenAlexW1989966214MaRDI QIDQ5501937FDOQ5501937

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

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

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)

Cites Work

• Asymptotics in statistics. Some basic concepts.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Pseudo-Boolean optimization
• The Probabilistic Communication Complexity of Set Intersection
• Communication Complexity
• A user's guide to measure theoretic probability
• On the power of small-depth threshold circuits
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• The BNS lower bound for multi-party protocols is nearly optimal
• On the degree of Boolean functions as real polynomials
• The pattern matrix method
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
• Multiparty Communication Complexity and Threshold Circuit Size of AC^0
• The multiparty communication complexity of set disjointness
• An information statistics approach to data stream and communication complexity
• Disjointness is hard in the multiparty number-on-the-forehead model
• Boolean derivatives on cellular automata
• On the distributional complexity of disjointness
• A strong direct product theorem for corruption and the multiparty communication complexity of disjointness
• A strong direct product theorem for disjointness
• A separation of NP and conp in multiparty communication complexity
• Title not available (Why is that?)
• 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
• Finite field models in additive combinatorics
• Lower bounds for local versions of dimension reductions
• Multilinear polynomials modulo composites
• Title not available (Why is that?)
• The NOF multiparty communication complexity of composed functions
• Separating AC\(^0\) from depth-2 majority circuits
• One-way multiparty communication lower bound for pointer jumping with applications
• The cost of the missing bit: Communication complexity with help
• The complexity of Boolean functions in different characteristics
• On complexity of computation of partial derivatives of Boolean functions realized by Zhegalkin polynomials
• A counterexample to strong parallel repetition

Cited In (19)

• 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
• Title not available (Why is that?)
• 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
• Separation of unbounded-error models in multi-party communication complexity
• On multiparty communication with large versus unbounded error

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)