Tight Bounds for the Subspace Sketch Problem with Applications
From MaRDI portal
Publication:5009789
DOI10.1137/20M1311831OpenAlexW3191037578MaRDI QIDQ5009789
David P. Woodruff, Ruosong Wang, Yi Li
Publication date: 6 August 2021
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1904.05543
Local theory of Banach spaces (46B07) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Embeddings of discrete metric spaces into Banach spaces; applications in topology and computer science (46B85) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Smaller coresets for \(k\)-median and \(k\)-means clustering
- Asymptotic theory of finite dimensional normed spaces. With an appendix by M. Gromov: Isoperimetric inequalities in Riemannian manifolds
- On data structures and asymmetric communication complexity
- Introduction to calculus and analysis. Volume I.
- Approximation of zonoids by zonotopes
- Finding frequent items in data streams
- On Sketching Quadratic Forms
- The Fast Cauchy Transform and Faster Robust Linear Regression
- Zero-one frequency laws
- Computational Advertising: Techniques for Targeting Relevant Ads
- Quantile Regression for Large-Scale Applications
- L p Row Sampling by Lewis Weights
- On the Construction of Binary Sequence Families With Low Correlation and Large Sizes
- Tight embedding of subspaces of ๐ฟ_{๐} in โ_{๐}โฟ for even ๐
- Embedding Subspaces of L 1 into l N 1
- Stable distributions, pseudorandom generators, embeddings, and data stream computation
- Generalized Jacobi Weights, Christoffel Functions, and Jacobi Polynomials
- High-Dimensional Probability
- High Probability Frequency Moment Sketches
- Optimal Lower Bounds for Sketching Graph Cuts
- Fast moment estimation in data streams in optimal space
- A Class of Convex Bodies
- Compressed matrix multiplication
- Concentration of Measure for the Analysis of Randomized Algorithms
