Partition arguments in multiparty communication complexity

DOI10.1016/j.tcs.2010.01.018zbMath1218.68085OpenAlexW2743006123MaRDI QIDQ541668

Eyal Kushilevitz, Enav Weinreb, Jan Draisma

Publication date: 7 June 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.01.018

zbMATH Keywords

lower boundscommunication complexitylog rank conjecturemultiparty communication complexitypartition arguments

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) Network protocols (68M12)

Related Items

Tensor surgery and tensor rank, Bounded-rank tensors are defined in bounded degree, Multiparty Communication Complexity of Vector–Valued and Sum–Type Functions

Cites Work

• Unnamed Item
• Unnamed Item
• Multiparty communication complexity and very hard functions
• An information statistics approach to data stream and communication complexity
• Private vs. common random bits in communication complexity
• Lower bounds on the multiparty communication complexity
• The space complexity of approximating the frequency moments
• A comparison of two lower-bound methods for communication complexity
• On rank vs. communication complexity
• On the ``log rank-conjecture in communication complexity
• Tensor rank is NP-complete
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Geometry and the complexity of matrix multiplication
• Approximate counting of inversions in a data stream
• Determinism vs. Nondeterminism in Multiparty Communication Complexity
• Amortized Communication Complexity
• Communication Complexity
• Asymptotically Optimal Lower Bounds on the NIH-Multi-Party Information Complexity of the AND-Function and Disjointness