Improved Separations between Nondeterministic and Randomized Multiparty Communication
From MaRDI portal
Publication:5892180
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
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)
Related Items
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