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

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

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

(24)

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

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)