Separation of unbounded-error models in multi-party communication complexity

DOI10.4086/TOC.2018.V014A021MaRDI QIDQ4612486zbMATH OpenOpenAlexFDO

Authors Arkadev Chattopadhyay, Nikhil S. Mande

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.v014a021

zbMATH Keywords

communication complexitycomplexity theoryNOF modelunbounded errorweakly unbounded error

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• On multiparty communication with large versus unbounded error
• The NOF multiparty communication complexity of composed functions
• Multiparty communication complexity and threshold circuit size of AC^0
• Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity
• scientific article; zbMATH DE number 524134

Cites work

• Approximate degree and the complexity of depth three circuits
• Communication Complexity
• Communication Complexity of Simultaneous Messages
• Communication lower bounds using directional derivatives
• Disjointness is hard in the multiparty number-on-the-forehead model
• Efficient quantum protocols for XOR functions
• Halfspace matrices
• 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 multiparty communication with large versus unbounded error
• On the distributional complexity of disjointness
• On the power of the congested clique model
• On the Size of Weights for Threshold Gates
• Perceptrons, PP, and the polynomial hierarchy
• Polynomial threshold functions and Boolean threshold circuits
• Separating deterministic from randomized multiparty communication complexity
• Simplified lower bounds on the multiparty communication complexity of disjointness
• The BNS lower bound for multi-party protocols is nearly optimal
• The BNS-Chung criterion for multi-party communication complexity
• The intersection of two halfspaces has high threshold degree
• The multiparty communication complexity of set disjointness
• The NOF multiparty communication complexity of composed functions
• The power of super-logarithmic number of players
• The Probabilistic Communication Complexity of Set Intersection
• Towards polynomial lower bounds for dynamic problems

Cited in

(6)

• The hardest halfspace
• Multiparty communication complexity and threshold circuit size of AC^0
• On multiparty communication with large versus unbounded error
• A short list of equalities induces large sign-rank
• scientific article; zbMATH DE number 6292585 (Why is no real title available?)
• A Borsuk-Ulam lower bound for sign-rank and its applications

This page was built for publication: Separation of unbounded-error models in multi-party communication complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4612486)