Communication Complexity of Simultaneous Messages

DOI10.1137/S0097539700375944MaRDI QIDQ4441903zbMATH OpenOpenAlexFDO

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

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 theorycommunication complexitycircuit complexity

Mathematics Subject Classification ID

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

Recommendations

• Simultaneous messages vs. communication
• Publication:4508377
• Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity
• scientific article; zbMATH DE number 1769898
• Optimal lower bounds on the multiparty communication complexity

Cited in

(33)

• Separation of unbounded-error models in multi-party communication complexity
• Bounded simultaneous messages
• One-way multiparty communication lower bound for pointer jumping with applications
• Optimality of linear sketching under modular updates
• Allowing each node to communicate only once in a distributed system: shared whiteboard models
• On \(d\)-multiplicative secret sharing
• Limits of preprocessing
• scientific article; zbMATH DE number 2098690 (Why is no real title available?)
• Quadratic multiparty randomized encodings beyond honest majority and their applications
• Separating the communication complexity of truthful and nontruthful algorithms for combinatorial auctions
• Approximate F₂-Sketching of Valuation Functions
• Continuous monitoring of distributed data streams over a time-based sliding window
• Foundations of homomorphic secret sharing
• Three messages are not optimal in worst case interactive communication
• Interleaved Group Products
• SNARK lower bounds via communication complexity
• Individual communication complexity
• Simultaneous messages vs. communication
• Adversarially robust property-preserving hash functions
• Communication Lower Bounds Via the Chromatic Number
• The NOF multiparty communication complexity of composed functions
• scientific article; zbMATH DE number 1769898 (Why is no real title available?)
• A 3-party simultaneous protocol for SUM-INDEX
• Simultaneous multiparty communication protocols for composed functions
• General constructions for information-theoretic private information retrieval
• Quantum multiparty communication complexity and circuit lower bounds
• Public vs. private randomness in simultaneous multi-party communication complexity
• Public vs. private randomness in simultaneous multi-party communication complexity
• Simultaneous Communication in Noisy Channels
• New bounds for the garden-hose model
• scientific article; zbMATH DE number 1512689 (Why is no real title available?)
• scientific article; zbMATH DE number 7561745 (Why is no real title available?)
• Communication lower bounds via critical block sensitivity

This page was built for publication: Communication Complexity of Simultaneous Messages

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