Beating the Direct Sum Theorem in Communication Complexity with Implications for Sketching

DOI10.1137/1.9781611973105.125zbMath1422.68075OpenAlexW4242137535MaRDI QIDQ5741834

Grigory Yaroslavtsev, David P. Woodruff, Marco Molinaro

Publication date: 15 May 2019

Published in: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611973105.125

Mathematics Subject Classification ID

Database theory (68P15) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)

Related Items (9)

Amplification of One-Way Information Complexity via Codes and Noise Sensitivity ⋮ Interactive Information Complexity ⋮ Interactive Information Complexity ⋮ Certifying equality with limited interaction ⋮ Optimal (Euclidean) Metric Compression ⋮ Unnamed Item ⋮ Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems ⋮ Unnamed Item ⋮ Unnamed Item

This page was built for publication: Beating the Direct Sum Theorem in Communication Complexity with Implications for Sketching