A strong direct product theorem for corruption and the multiparty communication complexity of disjointness
From MaRDI portal
Publication:2460032
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
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
