Space lower bounds for distance approximation in the data stream model
From MaRDI portal
Publication:3579208
DOI10.1145/509907.509963zbMath1192.68331OpenAlexW2054081892MaRDI QIDQ3579208
Publication date: 5 August 2010
Published in: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/509907.509963
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items (13)
Sketching and Embedding are Equivalent for Norms ⋮ Finding frequent items in data streams ⋮ Hellinger volume and number-on-the-forehead communication complexity ⋮ The Simultaneous Communication of Disjointness with Applications to Data Streams ⋮ An information statistics approach to data stream and communication complexity ⋮ Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity ⋮ Finding longest increasing and common subsequences in streaming data ⋮ Communication Lower Bounds Via the Chromatic Number ⋮ Sketching information divergences ⋮ How to catch \(L_2\)-heavy-hitters on sliding windows ⋮ The Andoni–Krauthgamer–Razenshteyn Characterization of Sketchable Norms Fails for Sketchable Metrics ⋮ Hierarchical sampling from sketches: Estimating functions over data streams ⋮ Trading information complexity for error. II: The case of a large error and the external information complexity
This page was built for publication: Space lower bounds for distance approximation in the data stream model
