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

DOI10.4086/TOC.2023.V019A010OpenAlexW4390471865MaRDI QIDQ6138070FDOQ6138070

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

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

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)

Cites Work

• Lower bounds for one-way probabilistic communication complexity and their application to space complexity
• Title not available (Why is that?)
• Authors' response

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)