On multiparty communication with large versus unbounded error

DOI10.4086/TOC.2018.V014A022MaRDI QIDQ4612487zbMATH OpenOpenAlexFDO

Authors Alexander A. Sherstov

Publication date 31 January 2019

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2018.v014a022

zbMATH Keywords

PPlower boundsmultiparty communication complexityseparation of complexity classesUPPunbounded-error communication complexity

Mathematics Subject Classification ID

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)

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

Cites work

• A separation of NP and conp in multiparty communication complexity
• Communication Complexity
• Communication lower bounds using directional derivatives
• Disjointness is hard in the multiparty number-on-the-forehead model
• Halfspace matrices
• Improved separations between nondeterministic and randomized multiparty communication
• Lower Bounds for Lovász–Schrijver Systems and Beyond Follow from Multiparty Communication Complexity
• Lower bounds for the approximate degree of block-composed functions
• Majority gates vs. general weighted threshold gates
• Multiparty communication complexity and threshold circuit size of AC\(^0\)
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• On the power of small-depth threshold circuits
• Perceptrons, PP, and the polynomial hierarchy
• Probabilistic communication complexity
• Quantum communication complexity of symmetric predicates
• Robust polynomials and quantum algorithms
• Separating AC\(^0\) from depth-2 majority circuits
• Separating deterministic from randomized multiparty communication complexity
• Separation of unbounded-error models in multi-party communication complexity
• The multiparty communication complexity of set disjointness
• The pattern matrix method
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
• \(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom

Cited in

(7)

• Separation of unbounded-error models in multi-party communication complexity
• 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

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)