Turnstile streaming algorithms might as well be linear sketches
DOI10.1145/2591796.2591812zbMATH Open1315.68281OpenAlexW2053182026MaRDI QIDQ5259551FDOQ5259551
Huy L. Nguyen, Yi Li, 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
Randomized algorithms (68W20) Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Theory of Cryptography
- The geometry of differential privacy: the small database and approximate cases
- 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
- Collusion-secure fingerprinting for digital data
- Advances in Cryptology – CRYPTO 2004
- 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
- Privately releasing conjunctions and the statistical query barrier
- Efficient algorithms for privately releasing marginals via convex relaxations
Cited In (19)
- Practical Sketching Algorithms for Low-Rank Matrix Approximation
- 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
- On Approximating Matrix Norms in Data Streams
- A Framework for Adversarially Robust Streaming Algorithms
- Perfect $L_p$ Sampling in a Data Stream
- Randomized numerical linear algebra: Foundations and algorithms
- Approximate F_2-Sketching of Valuation Functions
- Deterministic Heavy Hitters with Sublinear Query Time
- Faster Update Time for Turnstile Streaming Algorithms
- Scalable symmetric Tucker tensor decomposition
- Maximum Matching in Turnstile Streams
- Sublinear Estimation of Weighted Matchings in Dynamic Data Streams
- Streaming Low-Rank Matrix Approximation with an Application to Scientific Simulation
- Sketching and Embedding are Equivalent for Norms
- Spiking neural networks through the lens of streaming algorithms
- The Simultaneous Communication of Disjointness with Applications to Data Streams
Uses Software
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)
