Optimality of linear sketching under modular updates
From MaRDI portal
Publication:5091764
DOI10.4230/LIPIcs.CCC.2019.13OpenAlexW2952381510MaRDI QIDQ5091764
Kaave Hosseini, Shachar Lovett, Grigory Yaroslavtsev
Publication date: 27 July 2022
Full work available at URL: https://arxiv.org/abs/1809.09063
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A probabilistic technique for finding almost-periods of convolutions
- The space complexity of approximating the frequency moments
- A polynomial bound in Freiman's theorem.
- ROTH’S THEOREM FOR FOUR VARIABLES AND ADDITIVE STRUCTURES IN SUMS OF SPARSE SETS
- Tight Approximations of Degeneracy in Large Graphs
- Computational Advertising: Techniques for Targeting Relevant Ads
- Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams
- Densest Subgraph in Dynamic Graph Streams
- Extensions of Lipschitz mappings into a Hilbert space
- Maximum Matching in Turnstile Streams
- Stable distributions, pseudorandom generators, embeddings, and data stream computation
- Lower Bounds on Frequency Estimation of Data Streams (Extended Abstract)
- Communication Complexity of Simultaneous Messages
- Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
- Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model
- On Estimating Maximum Matching Size in Graph Streams
- Semi-Streaming Algorithms for Annotated Graph Streams
- Turnstile streaming algorithms might as well be linear sketches
- Parameterized Streaming: Maximal Matching and Vertex Cover
This page was built for publication: Optimality of linear sketching under modular updates
