Improved Separations between Nondeterministic and Randomized Multiparty Communication

DOI10.1007/978-3-540-85363-3_30MaRDI QIDQ5900476zbMATH OpenOpenAlexFDO

Authors Matei David, Toniann Pitassi, Emanuele Viola

Publication date 27 November 2008

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.167.1860

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Network protocols (68M12)

Recommendations

• Improved separations between nondeterministic and randomized multiparty communication
• Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity
• Separating deterministic from randomized multiparty communication complexity
• Partition arguments in multiparty communication complexity
• A separation of NP and conp in multiparty communication complexity

Cited in

(10)

• On multiparty communication with large versus unbounded error
• Separating deterministic from randomized multiparty communication complexity
• One-way multiparty communication lower bound for pointer jumping with applications
• Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity
• Partition arguments in multiparty communication complexity
• The power of super-logarithmic number of players
• scientific article; zbMATH DE number 1688365 (Why is no real title available?)
• Improved separations between nondeterministic and randomized multiparty communication
• Determinism vs. Nondeterminism in Multiparty Communication Complexity
• A separation of NP and conp in multiparty communication complexity

This page was built for publication: Improved Separations between Nondeterministic and Randomized Multiparty Communication

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