Communication Complexity of Simultaneous Messages

DOI10.1137/S0097539700375944zbMath1069.68051OpenAlexW2007654329MaRDI QIDQ4441903

László Babai, Satyanarayana V. Lokam, Anna Gál, Peter G. Kimmel

Publication date: 8 January 2004

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539700375944

zbMATH Keywords

lower boundsgroup theorycircuit complexitycommunication complexity

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Communication Lower Bounds via Critical Block Sensitivity ⋮ Separating the Communication Complexity of Truthful and Nontruthful Algorithms for Combinatorial Auctions ⋮ On \(d\)-multiplicative secret sharing ⋮ Quadratic multiparty randomized encodings beyond honest majority and their applications ⋮ Continuous monitoring of distributed data streams over a time-based sliding window ⋮ Unnamed Item ⋮ Foundations of Homomorphic Secret Sharing ⋮ Interleaved Group Products ⋮ Approximate F_2-Sketching of Valuation Functions ⋮ The NOF multiparty communication complexity of composed functions ⋮ One-way multiparty communication lower bound for pointer jumping with applications ⋮ General constructions for information-theoretic private information retrieval ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Communication Lower Bounds Via the Chromatic Number ⋮ Public vs. private randomness in simultaneous multi-party communication complexity ⋮ Optimality of linear sketching under modular updates ⋮ Public vs. Private Randomness in Simultaneous Multi-party Communication Complexity ⋮ Unnamed Item ⋮ Allowing each node to communicate only once in a distributed system: shared whiteboard models