Improved Separations between Nondeterministic and Randomized Multiparty Communication

DOI10.1145/1595391.1595392zbMath1322.68074OpenAlexW2035762900MaRDI QIDQ5892180

Emanuele Viola, Matei David, Toniann Pitassi

Publication date: 24 September 2015

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1595391.1595392

zbMATH Keywords

randomizationlower boundnondeterminismcommunication complexitynumber on forehead

Mathematics Subject Classification ID

Related Items (5)

A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$ ⋮ Simulation theorems via pseudo-random properties ⋮ The Multiparty Communication Complexity of Set Disjointness ⋮ Unnamed Item ⋮ Unnamed Item

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