On multiparty communication with large versus unbounded error
DOI10.4086/TOC.2018.V014A022zbMATH Open1412.68061OpenAlexW2908449032MaRDI QIDQ4612487FDOQ4612487
Authors: Alexander A. Sherstov 
Publication date: 31 January 2019
Published in: Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.4086/toc.2018.v014a022
Recommendations
- Separation of unbounded-error models in multi-party communication complexity
- Unbounded-Error Classical and Quantum Communication Complexity
- The unbounded-error communication complexity of symmetric functions
- Improved Separations between Nondeterministic and Randomized Multiparty Communication
- Partition arguments in multiparty communication complexity
PPlower boundsmultiparty communication complexityseparation of complexity classesUPPunbounded-error communication complexity
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Communication Complexity
- Majority gates vs. general weighted threshold gates
- \(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom
- On the power of small-depth threshold circuits
- Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
- The pattern matrix method
- Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
- Quantum communication complexity of symmetric predicates
- Disjointness is hard in the multiparty number-on-the-forehead model
- Probabilistic communication complexity
- A separation of NP and conp in multiparty communication complexity
- Perceptrons, PP, and the polynomial hierarchy
- Halfspace matrices
- Robust polynomials and quantum algorithms
- Lower Bounds for Lovász–Schrijver Systems and Beyond Follow from Multiparty Communication Complexity
- Separating deterministic from randomized multiparty communication complexity
- Separating AC\(^0\) from depth-2 majority circuits
- The multiparty communication complexity of set disjointness
- Multiparty communication complexity and threshold circuit size of AC\(^0\)
- Lower bounds for the approximate degree of block-composed functions
- Separation of unbounded-error models in multi-party communication complexity
- Communication lower bounds using directional derivatives
- Improved separations between nondeterministic and randomized multiparty communication
Cited In (7)
- The hardest halfspace
- Unbounded-Error Classical and Quantum Communication Complexity
- The unbounded-error communication complexity of symmetric functions
- Direct sum fails for zero error average communication
- Approximate Degree in Classical and Quantum Computing
- Tight bounds for communication-assisted agreement distillation
- Separation of unbounded-error models in multi-party communication complexity
This page was built for publication: On multiparty communication with large versus unbounded error
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4612487)
