Turnstile streaming algorithms might as well be linear sketches

DOI10.1145/2591796.2591812zbMATH Open1315.68281OpenAlexW2053182026MaRDI QIDQ5259551FDOQ5259551

Authors: Yi Li, Huy L. Nguyen, David P. Woodruff 

Publication date: 26 June 2015

Published in: Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2591796.2591812

Recommendations

• scientific article; zbMATH DE number 6789285
• Time lower bounds for nonadaptive turnstile streaming algorithms
• Tight lower bound for linear sketches of moments
• Numerical linear algebra in the streaming model
• Deterministic heavy hitters with sublinear query time

zbMATH Keywords

lower boundscommunication complexitystreaming algorithmslinear sketches

Mathematics Subject Classification ID

Randomized algorithms (68W20) Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05)

Cites Work

• Theory of Cryptography
• On the geometry of differential privacy
• Interactive privacy via the median mechanism
• The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
• Lower bounds in differential privacy
• Iterative Constructions and Private Data Release
• Differential privacy and the fat-shattering dimension of linear queries
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• On the complexity of differentially private data release, efficient algorithms and hardness results
• Title not available (Why is that?)
• Collusion-secure fingerprinting for digital data
• Advances in Cryptology – CRYPTO 2004
• Title not available (Why is that?)
• New Efficient Attacks on Statistical Disclosure Control Mechanisms
• Bounds on the sample complexity for private learning and private data release
• Answering \(n^{2+o(1)}\) counting queries with differential privacy is hard
• Characterizing the sample complexity of private learners
• Faster algorithms for privately releasing marginals
• Faster private release of marginals on small databases
• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
• Efficient algorithms for privately releasing marginals via convex relaxations

Cited In (21)

• Title not available (Why is that?)
• Optimal lower bounds for matching and vertex cover in dynamic graph streams
• Querying a Matrix Through Matrix-Vector Products.
• Optimality of linear sketching under modular updates
• Time lower bounds for nonadaptive turnstile streaming algorithms
• A Framework for Adversarially Robust Streaming Algorithms
• Maximum matching in turnstile streams
• Sublinear estimation of weighted matchings in dynamic data streams
• Randomized numerical linear algebra: Foundations and algorithms
• Approximate F_2-Sketching of Valuation Functions
• On approximating matrix norms in data streams
• Perfect \(L_p\) sampling in a data stream
• Faster Update Time for Turnstile Streaming Algorithms
• Sketching and embedding are equivalent for norms
• Practical sketching algorithms for low-rank matrix approximation
• Scalable symmetric Tucker tensor decomposition
• Zero-one laws for sliding windows and universal sketches
• Spiking neural networks through the lens of streaming algorithms
• Deterministic heavy hitters with sublinear query time
• Streaming low-rank matrix approximation with an application to scientific simulation
• The Simultaneous Communication of Disjointness with Applications to Data Streams

Uses Software

• SuLQ

This page was built for publication: Turnstile streaming algorithms might as well be linear sketches

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5259551)