Hellinger Strikes Back: A Note on the Multi-party Information Complexity of AND

DOI10.1007/978-3-642-03685-9_42zbMath1255.68074OpenAlexW1512493349MaRDI QIDQ3638903

T. S. Jayram

Publication date: 28 October 2009

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-03685-9_42

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Network protocols (68M12)

Related Items (13)

Hellinger volume and number-on-the-forehead communication complexity ⋮ Solving the Induced Subgraph Problem in the Randomized Multiparty Simultaneous Messages Model ⋮ Zero-information protocols and unambiguity in Arthur-Merlin communication ⋮ Towards Optimal Moment Estimation in Streaming and Distributed Models ⋮ Towards Optimal Moment Estimation in Streaming and Distributed Models ⋮ Unnamed Item ⋮ Forty years of frequent items ⋮ Continuous Monitoring of l_p Norms in Data Streams ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On Approximating Matrix Norms in Data Streams ⋮ Connectivity and connected components in the number-in-hand computation model ⋮ Trading information complexity for error. II: The case of a large error and the external information complexity

Uses Software

• OEIS

This page was built for publication: Hellinger Strikes Back: A Note on the Multi-party Information Complexity of AND