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

DOI10.1007/S00037-007-0220-2MaRDI QIDQ2460032zbMATH OpenOpenAlexFDO

Authors Paul Beame, Toniann Pitassi, Nathan Segerlind, A. Wigderson

Publication date 14 November 2007

Published in Computational Complexity (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

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

zbMATH Keywords

Communication complexitydirect productdirect sumlower boundsmultiparty protocols

Mathematics Subject Classification ID

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

Recommendations

• The communication complexity of multiparty set disjointness under product distributions
• A note on the communication complexity of multiparty computation in the correlated randomness model
• Simplified lower bounds on the multiparty communication complexity of disjointness
• The multiparty communication complexity of set disjointness
• The multiparty communication complexity of set disjointness
• A direct product theorem for two-party bounded-round public-coin communication complexity
• The corruption bound, log-rank, and communication complexity
• Separating deterministic from randomized multiparty communication complexity
• A note on multiparty communication complexity and the Hales-Jewett theorem
• A separation of NP and conp in multiparty communication complexity

Cited in

(22)

• The corruption bound, log-rank, and communication complexity
• Simulation theorems via pseudo-random properties
• New strong direct product results in communication complexity
• Upper and lower bounds on the power of advice
• The multiparty communication complexity of set disjointness
• A strong direct product theorem for disjointness
• A direct product theorem for two-party bounded-round public-coin communication complexity
• Simplified lower bounds on the multiparty communication complexity of disjointness
• Simultaneous multiparty communication protocols for composed functions
• One-way multiparty communication lower bound for pointer jumping with applications
• Kolmogorov complexity and combinatorial methods in communication complexity
• Query complexity of sampling and small geometric partitions
• Communication lower bounds using directional derivatives
• A little advice can be very helpful
• Query-to-communication lifting using low-discrepancy gadgets
• Inner product and set disjointness: beyond logarithmically many parties
• scientific article; zbMATH DE number 7650118 (Why is no real title available?)
• Rectangles are nonnegative juntas
• Disjointness is hard in the multiparty number-on-the-forehead model
• Lower bounds for semi-adaptive data structures via corruption
• The approximate degree of DNF and CNF formulas
• Choosing, agreeing, and eliminating in communication complexity

This page was built for publication: A strong direct product theorem for corruption and the multiparty communication complexity of disjointness

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