Separating deterministic from randomized multiparty communication complexity

DOI10.4086/TOC.2010.V006A009MaRDI QIDQ3002822zbMATH OpenOpenAlexFDO

Authors Matei David, Toniann Pitassi, Philipp Woelfel, Paul Beame

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

zbMATH Keywords

communication complexitynumber on forehead

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity
• Improved Separations between Nondeterministic and Randomized Multiparty Communication
• Improved separations between nondeterministic and randomized multiparty communication
• A separation of NP and conp in multiparty communication complexity
• Rounds in Communication Complexity Revisited

Cited in

(23)

• Separation of unbounded-error models in multi-party communication complexity
• On multiparty communication with large versus unbounded error
• Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity
• Equality alone does not simulate randomness
• Improved Separations between Nondeterministic and Randomized Multiparty Communication
• A strong direct product theorem for corruption and the multiparty communication complexity of disjointness
• scientific article; zbMATH DE number 1419257 (Why is no real title available?)
• scientific article; zbMATH DE number 6292585 (Why is no real title available?)
• scientific article; zbMATH DE number 1418336 (Why is no real title available?)
• scientific article; zbMATH DE number 7204504 (Why is no real title available?)
• The landscape of communication complexity classes
• The landscape of communication complexity classes
• Nondeterministic and randomized Boolean hierarchies in communication complexity
• Improved separations between nondeterministic and randomized multiparty communication
• An improved protocol for ExactlyN with more than 3 players
• Partition Arguments in Multiparty Communication Complexity
• A note on multiparty communication complexity and the Hales-Jewett theorem
• The NOF multiparty communication complexity of composed functions
• The Multiparty Communication Complexity of Exact-T: Improved Bounds and New Problems
• The approximate degree of DNF and CNF formulas
• The communication complexity of addition
• The multiparty communication complexity of set disjointness
• A separation of NP and conp in multiparty communication complexity

This page was built for publication: Separating deterministic from randomized multiparty communication complexity

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