The BNS lower bound for multi-party protocols is nearly optimal

DOI10.1006/inco.1994.1051zbMath0822.68042OpenAlexW2074564146MaRDI QIDQ1327389

Vince Grolmusz

Publication date: 19 June 1994

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.1994.1051

zbMATH Keywords

multi-party protocol

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Distributed algorithms (68W15)

Related Items

Hellinger volume and number-on-the-forehead communication complexity, Hadamard tensors and lower bounds on multiparty communication complexity, Unnamed Item, Unnamed Item, Unexpected upper bounds on the complexity of some communication games, Interleaved Group Products, The NOF multiparty communication complexity of composed functions, Harmonic analysis, real approximation, and the communication complexity of Boolean functions, Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs, Unnamed Item, Quantum multiparty communication complexity and circuit lower bounds, The Multiparty Communication Complexity of Set Disjointness, Unnamed Item, Communication Lower Bounds Using Directional Derivatives