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

DOI10.1007/978-3-642-03685-9_42MaRDI QIDQ3638903zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Hellinger volume and number-on-the-forehead communication complexity
• Asymptotically optimal lower bounds on the NIH-multi-party information complexity of the AND-function and disjointness
• An information statistics approach to data stream and communication complexity

Cited in

(16)

• 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
• Hellinger volume and number-on-the-forehead communication complexity
• Zero-information protocols and unambiguity in Arthur-Merlin communication
• Solving the \textsc{induced subgraph} problem in the randomized multiparty simultaneous messages model
• Continuous monitoring of _p norms in data streams
• scientific article; zbMATH DE number 7559107 (Why is no real title available?)
• Separating \(k\)-player from \(t\)-player one-way communication, with applications to data streams
• On approximating matrix norms in data streams
• Advances in Cryptology - EUROCRYPT 2004
• Asymptotically optimal lower bounds on the NIH-multi-party information complexity of the AND-function and disjointness
• Towards Optimal Moment Estimation in Streaming and Distributed Models
• scientific article; zbMATH DE number 7650118 (Why is no real title available?)
• An information statistics approach to data stream and communication complexity
• Towards Optimal Moment Estimation in Streaming and Distributed Models
• Forty years of frequent items

Describes a project that uses

Uses Software

• OEIS

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

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