Space lower bounds for distance approximation in the data stream model
From MaRDI portal
Publication:3579208
DOI10.1145/509907.509963zbMath1192.68331MaRDI 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
68Q25: Analysis of algorithms and problem complexity
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25: Approximation algorithms
68W20: Randomized algorithms
Related Items
Sketching and Embedding are Equivalent for Norms, Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity, Communication Lower Bounds Via the Chromatic Number, Hellinger volume and number-on-the-forehead communication complexity, An information statistics approach to data stream and communication complexity, How to catch \(L_2\)-heavy-hitters on sliding windows, Sketching information divergences, Hierarchical sampling from sketches: Estimating functions over data streams, Finding frequent items in data streams, Trading information complexity for error. II: The case of a large error and the external information complexity, Finding longest increasing and common subsequences in streaming data, The Andoni–Krauthgamer–Razenshteyn Characterization of Sketchable Norms Fails for Sketchable Metrics, The Simultaneous Communication of Disjointness with Applications to Data Streams
