Turnstile streaming algorithms might as well be linear sketches

DOI10.1145/2591796.2591812MaRDI QIDQ5259551zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(23)

• scientific article; zbMATH DE number 7250148 (Why is no real title available?)
• 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
• Universal streaming of subset norms
• 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₂-Sketching of Valuation Functions
• Sketching approximability of all finite CSPs
• 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
• Deterministic heavy hitters with sublinear query time
• Spiking neural networks through the lens of streaming algorithms
• Streaming low-rank matrix approximation with an application to scientific simulation
• The Simultaneous Communication of Disjointness with Applications to Data Streams

Describes a project that uses

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)