scientific article; zbMATH DE number 7009620

DOI10.4086/toc.2018.v014a021zbMath1414.68027OpenAlexW2908369137MaRDI QIDQ4612486

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

communication complexitycomplexity theoryunbounded errorNOF modelweakly unbounded error

Mathematics Subject Classification ID

Related Items (2)

The hardest halfspace ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The NOF multiparty communication complexity of composed functions
• Disjointness is hard in the multiparty number-on-the-forehead model
• Halfspace matrices
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• On the distributional complexity of disjointness
• Majority gates vs. general weighted threshold gates
• The BNS lower bound for multi-party protocols is nearly optimal
• Perceptrons, PP, and the polynomial hierarchy
• Polynomial threshold functions and Boolean threshold circuits
• The Multiparty Communication Complexity of Set Disjointness
• Towards polynomial lower bounds for dynamic problems
• Multiparty Communication Complexity and Threshold Circuit Size of $\ensuremath{\sfAC}^0$
• On the power of the congested clique model
• The Probabilistic Communication Complexity of Set Intersection
• On the Size of Weights for Threshold Gates
• Communication Complexity of Simultaneous Messages
• Communication Complexity
• Efficient quantum protocols for XOR functions
• The Intersection of Two Halfspaces Has High Threshold Degree
• Communication Lower Bounds Using Directional Derivatives
• The BNS-Chung criterion for multi-party communication complexity

This page was built for publication: