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

complexity theorycommunication complexityunbounded errorNOF modelweakly unbounded error

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

• 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 Size of Weights for Threshold Gates
• On the distributional complexity of disjointness
• On the power of the congested clique model
• 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 NOF multiparty communication complexity of composed functions
• The Probabilistic Communication Complexity of Set Intersection
• The intersection of two halfspaces has high threshold degree
• The multiparty communication complexity of set disjointness
• The power of super-logarithmic number of players
• Towards polynomial lower bounds for dynamic problems

Cited in

(6)

• On multiparty communication with large versus unbounded error
• The hardest halfspace
• scientific article; zbMATH DE number 6292585 (Why is no real title available?)
• Multiparty communication complexity and threshold circuit size of AC\(^0\)
• A short list of equalities induces large sign-rank
• 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)