Separation of unbounded-error models in multi-party communication complexity
DOI10.4086/TOC.2018.V014A021zbMATH Open1414.68027OpenAlexW2908369137MaRDI QIDQ4612486FDOQ4612486
Arkadev Chattopadhyay, Nikhil S. Mande
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.v014a021
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
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
- Towards polynomial lower bounds for dynamic problems
- The Probabilistic Communication Complexity of Set Intersection
- Communication Complexity
- Majority gates vs. general weighted threshold gates
- Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
- The BNS lower bound for multi-party protocols is nearly optimal
- The BNS-Chung criterion for multi-party communication complexity
- Disjointness is hard in the multiparty number-on-the-forehead model
- On the distributional complexity of disjointness
- On the Size of Weights for Threshold Gates
- Perceptrons, PP, and the polynomial hierarchy
- Halfspace matrices
- Title not available (Why is that?)
- Communication Complexity of Simultaneous Messages
- The NOF multiparty communication complexity of composed functions
- On the power of the congested clique model
- Efficient quantum protocols for XOR functions
- Title not available (Why is that?)
- Title not available (Why is that?)
- The multiparty communication complexity of set disjointness
- Multiparty communication complexity and threshold circuit size of AC\(^0\)
- Title not available (Why is that?)
- Title not available (Why is that?)
- The Intersection of Two Halfspaces Has High Threshold Degree
- Communication Lower Bounds Using Directional Derivatives
- Polynomial threshold functions and Boolean threshold circuits
- Title not available (Why is that?)
Cited In (4)
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)
