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

circuit complexitycommunication complexitygroup theorylower bounds

Mathematics Subject Classification ID

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

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)

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

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)