Tracking the l_2 Norm with Constant Update Time

DOI10.4230/LIPIcs.APPROX-RANDOM.2019.2OpenAlexW2978820221MaRDI QIDQ5875453

Preetum Nakkiran, Zhixian Lei, Chi-Ning Chou

Publication date: 3 February 2023

Full work available at URL: https://arxiv.org/abs/1807.06479

zbMATH Keywords

trackingstreaming algorithmscountsketchsketching algorithms

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Asymptotic optimality of new adaptive test in regression model
• A sparse Johnson
• Tabulation-Based 5-Independent Hashing with Applications to Linear Probing and Second Moment Estimation
• Optimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Subconstant Error
• Time Lower Bounds for Nonadaptive Turnstile Streaming Algorithms
• Almost Optimal Explicit Johnson-Lindenstrauss Families
• Sparser Johnson-Lindenstrauss Transforms
• Stable distributions, pseudorandom generators, embeddings, and data stream computation
• An improved data stream summary: the count-min sketch and its applications
• Continuous Monitoring of l_p Norms in Data Streams
• Beating CountSketch for heavy hitters in insertion streams
• Fast moment estimation in data streams in optimal space
• A Bound on Tail Probabilities for Quadratic Forms in Independent Random Variables
• The Accuracy of the Gaussian Approximation to the Sum of Independent Variates