A strong direct product theorem for corruption and the multiparty communication complexity of disjointness

DOI10.1007/s00037-007-0220-2zbMath1125.68054OpenAlexW1972068724MaRDI QIDQ2460032

Nathan Segerlind, P. W. Beame, Toniann Pitassi, Avi Wigderson

Publication date: 14 November 2007

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-007-0220-2

zbMATH Keywords

lower boundsdirect productdirect sumCommunication complexitymultiparty protocols

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

The corruption bound, log-rank, and communication complexity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Query Complexity of Sampling and Small Geometric Partitions ⋮ One-way multiparty communication lower bound for pointer jumping with applications ⋮ Kolmogorov complexity and combinatorial methods in communication complexity ⋮ Simulation theorems via pseudo-random properties ⋮ New Strong Direct Product Results in Communication Complexity ⋮ Rectangles Are Nonnegative Juntas ⋮ Choosing, agreeing, and eliminating in communication complexity ⋮ Upper and Lower Bounds on the Power of Advice ⋮ The Multiparty Communication Complexity of Set Disjointness ⋮ Communication Lower Bounds Using Directional Derivatives ⋮ Query-to-Communication Lifting Using Low-Discrepancy Gadgets ⋮ Unnamed Item