Separating k-player from t-player one-way communication, with applications to data streams

DOI10.4086/TOC.2023.V019A010OpenAlexMaRDI QIDQ6138070FDO

Authors Michael Mitzenmacher, David P. Woodruff, Guang Yang

Publication date 16 January 2024

Published in Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.4086/toc.2023.v019a010

zbMATH Keywords

approximationspace complexitydirect sumstreamingHamming normalgorithms with predictions

Mathematics Subject Classification ID

Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Theory of computing (68Qxx)

Recommendations

• Separating \(k\)-player from \(t\)-player one-way communication, with applications to data streams
• An information statistics approach to data stream and communication complexity
• The Simultaneous Communication of Disjointness with Applications to Data Streams
• Robust lower bounds for communication and stream computation
• Better Gap-Hamming Lower Bounds via Better Round Elimination

Cites work

• scientific article; zbMATH DE number 6789285 (Why is no real title available?)
• Authors' response
• Lower bounds for one-way probabilistic communication complexity and their application to space complexity

This page was built for publication: Separating \(k\)-player from \(t\)-player one-way communication, with applications to data streams

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