A separation of NP and conp in multiparty communication complexity

DOI10.4086/TOC.2010.V006A010MaRDI QIDQ3002823zbMATH OpenOpenAlexFDO

Authors Dmitry Gavinsky, Alexander A. Sherstov

Publication date 24 May 2011

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.2010.v006a010

zbMATH Keywords

Merlin-Arthur computationsmultiparty communication complexitynondeterminismseparations and lower bounds

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Separating deterministic from randomized multiparty communication complexity
• Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity
• Improved separations between nondeterministic and randomized multiparty communication
• Improved Separations between Nondeterministic and Randomized Multiparty Communication
• On the P versus NP intersected with co-NP question in communication complexity

Cited in

(32)

• On the P versus NP intersected with co-NP question in communication complexity
• The landscape of communication complexity classes
• Non-interactive proofs of proximity
• A note on multiparty communication complexity and the Hales-Jewett theorem
• On multi-partition communication complexity
• A strong direct product theorem for corruption and the multiparty communication complexity of disjointness
• The multiparty communication complexity of set disjointness
• Separating deterministic from randomized multiparty communication complexity
• Finite groups and complexity theory: from Leningrad to Saint Petersburg via Las Vegas
• Zero-information protocols and unambiguity in Arthur-Merlin communication
• Hardness amplification and the approximate degree of constant-depth circuits
• Languages with Bounded Multiparty Communication Complexity
• Partition Arguments in Multiparty Communication Complexity
• Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
• The power of asymmetry in constant-depth circuits
• The landscape of communication complexity classes
• On multiparty communication with large versus unbounded error
• scientific article; zbMATH DE number 1418336 (Why is no real title available?)
• scientific article; zbMATH DE number 1419257 (Why is no real title available?)
• Approximate Degree in Classical and Quantum Computing
• scientific article; zbMATH DE number 7559107 (Why is no real title available?)
• A nearly optimal lower bound on the approximate degree of \(\mathrm{AC}^0\)
• The polynomial method strikes back: tight quantum query bounds via dual polynomials
• scientific article; zbMATH DE number 6292585 (Why is no real title available?)
• Communication lower bounds using directional derivatives
• The Multiparty Communication Complexity of Exact-T: Improved Bounds and New Problems
• scientific article; zbMATH DE number 7650118 (Why is no real title available?)
• Rectangles are nonnegative juntas
• Improved separations between nondeterministic and randomized multiparty communication
• Improved Separations between Nondeterministic and Randomized Multiparty Communication
• Multiparty communication complexity and very hard functions
• The approximate degree of DNF and CNF formulas

This page was built for publication: A separation of NP and conp in multiparty communication complexity

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