scientific article; zbMATH DE number 6469144

zbMath1317.68059MaRDI QIDQ5501255

David P. Woodruff

Publication date: 3 August 2015

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Theory of data (68P99) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items

Sketching and Embedding are Equivalent for Norms ⋮ Taylor Polynomial Estimator for Estimating Frequency Moments ⋮ The Simultaneous Communication of Disjointness with Applications to Data Streams ⋮ A Framework for Adversarially Robust Streaming Algorithms ⋮ The Cost of Fault Tolerance in Multi-Party Communication Complexity ⋮ Towards Optimal Moment Estimation in Streaming and Distributed Models ⋮ Towards Optimal Moment Estimation in Streaming and Distributed Models ⋮ On differential privacy and adaptive data analysis with bounded space ⋮ Unnamed Item ⋮ Estimating hybrid frequency moments of data streams ⋮ Unnamed Item ⋮ A Simple Algorithm for Approximating the Text-To-Pattern Hamming Distance ⋮ Towards Unified Approximate Pattern Matching for Hamming and L_1 Distance ⋮ Continuous Monitoring of l_p Norms in Data Streams ⋮ One-Sided Error Communication Complexity of Gap Hamming Distance. ⋮ Unnamed Item ⋮ Applying approximate counting for computing the frequency moments of long data streams ⋮ Unnamed Item ⋮ Sketching information divergences ⋮ Space‐efficient tracking of persistent items in a massive data stream ⋮ Hierarchical sampling from sketches: Estimating functions over data streams ⋮ Everywhere-Tight Information Cost Tradeoffs for Augmented Index ⋮ Approximating Approximate Pattern Matching ⋮ A Note on Estimating Hybrid Frequency Moment of Data Streams ⋮ Recent advances in text-to-pattern distance algorithms