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)

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

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)