Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity

DOI10.1007/978-3-540-73420-8_14MaRDI QIDQ5428804zbMATH OpenOpenAlexFDO

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

Publication date 28 November 2007

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-73420-8_14

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Separating deterministic from randomized multiparty communication complexity
• Improved Separations between Nondeterministic and Randomized Multiparty Communication
• Improved separations between nondeterministic and randomized multiparty communication
• Partition arguments in multiparty communication complexity
• Determinism vs. Nondeterminism in Multiparty Communication Complexity

Cited in

(27)

• Separation of unbounded-error models in multi-party communication complexity
• The hardest halfspace
• Separating deterministic from randomized multiparty communication complexity
• Larger Corner-Free Sets from Better NOF Exactly-$N$ Protocols
• One-way multiparty communication lower bound for pointer jumping with applications
• The NOF multiparty communication complexity of composed functions
• scientific article; zbMATH DE number 1948494 (Why is no real title available?)
• NOF-Multiparty Information Complexity Bounds for Pointer Jumping
• Improved Separations between Nondeterministic and Randomized Multiparty Communication
• Partition arguments in multiparty communication complexity
• scientific article; zbMATH DE number 6292585 (Why is no real title available?)
• The power of super-logarithmic number of players
• Different Modes of Communication
• Nondeterministic and randomized Boolean hierarchies in communication complexity
• Nondeterministic communication complexity with help and graph functions
• Improved separations between nondeterministic and randomized multiparty communication
• On the communication complexity of high-dimensional permutations
• Communication Complexity of Simultaneous Messages
• A note on multiparty communication complexity and the Hales-Jewett theorem
• The NOF multiparty communication complexity of composed functions
• The approximate degree of DNF and CNF formulas
• Public vs. private randomness in simultaneous multi-party communication complexity
• Non-deterministic communication complexity with few witnesses
• Public vs. private randomness in simultaneous multi-party communication complexity
• Determinism vs. Nondeterminism in Multiparty Communication Complexity
• 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 Nondeterministic NOF Multiparty Communication Complexity

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