| Publication | Date of Publication | Type |
|---|
| Tight lower bounds for the distinct elements problem | 2026-05-29 | Paper |
| Explicit exclusive set systems with applications to broadcast encryption | 2026-05-29 | Paper |
| Lower bounds for additive spanners, emulators, and more | 2026-05-29 | Paper |
| A very sketchy talk (invited talk) | 2026-05-12 | Paper |
| Separations for estimating large frequency moments on data streams | 2026-05-12 | Paper |
| Simple heuristics yield provable algorithms for masked low-rank approximation | 2026-04-15 | Paper |
| Near-linear time and fixed-parameter tractable algorithms for tensor decompositions | 2025-11-04 | Paper |
| Space-optimal profile estimation in data streams with applications to symmetric functions | 2025-11-04 | Paper |
| Universal matrix sparsifiers and fast deterministic algorithms for linear algebra | 2025-11-04 | Paper |
Online Lewis weight sampling
ACM Transactions on Algorithms | 2025-11-03 | Paper |
| Faster algorithms for Schatten-p low rank approximation | 2025-10-06 | Paper |
| Pseudorandom hashing for space-bounded computation with applications in streaming | 2025-08-15 | Paper |
| Streaming euclidean k-median and k-means with o( n) space | 2025-08-15 | Paper |
| Active linear regression for _p norms and beyond | 2025-08-15 | Paper |
| High-dimensional geometric streaming in polynomial space | 2025-08-15 | Paper |
| Testing positive semidefiniteness using linear measurements | 2025-08-15 | Paper |
| Tight bounds for adversarially robust streams and sliding windows via difference estimators | 2025-08-13 | Paper |
| Near optimal linear algebra in the online and sliding window models | 2025-08-12 | Paper |
| Robust and sample optimal algorithms for PSD low rank approximation | 2025-08-12 | Paper |
| The coin problem with applications to data streams | 2025-08-12 | Paper |
| Strong coresets for k-median and subspace approximation: goodbye dimension | 2025-08-12 | Paper |
| Perfect L_p sampling in a data stream | 2025-08-12 | Paper |
| Sublinear time low-rank approximation of positive semidefinite matrices | 2025-08-06 | Paper |
| Optimal lower bounds for universal relation, and for samplers and finding duplicates in streams | 2025-08-06 | Paper |
| Input sparsity and hardness for robust subspace approximation | 2025-08-05 | Paper |
| Sublinear optimization for machine learning | 2025-04-29 | Paper |
| Recovery from non-decomposable distance oracles | 2024-09-25 | Paper |
| Streaming algorithms with large approximation factors | 2024-08-22 | Paper |
| Adaptive sketches for robust regression with importance sampling | 2024-08-22 | Paper |
| Frequency estimation with one-sided error | 2024-07-19 | Paper |
| Improved algorithms for low rank approximation from sparsity | 2024-07-19 | Paper |
| Near-optimal algorithms for linear algebra in the current matrix multiplication time | 2024-07-19 | Paper |
Recovery from non-decomposable distance oracles
IEEE Transactions on Information Theory | 2024-07-19 | Paper |
| The \(\ell_p\)-subspace sketch problem in small dimensions with applications to support vector machines | 2024-05-14 | Paper |
| Near-linear sample complexity for L_p polynomial regression | 2024-05-14 | Paper |
| Optimal algorithms for linear algebra in the current matrix multiplication time | 2024-05-14 | Paper |
| Online Lewis weight sampling | 2024-05-14 | Paper |
| Optimal eigenvalue approximation via sketching | 2024-05-08 | Paper |
| New subset selection algorithms for low rank approximation: offline and online | 2024-05-08 | Paper |
scientific article; zbMATH DE number 7829248 (Why is no real title available?)
(available as arXiv preprint) | 2024-04-09 | Paper |
scientific article; zbMATH DE number 7829323 (Why is no real title available?)
(available as arXiv preprint) | 2024-04-09 | Paper |
Separating k-player from t-player one-way communication, with applications to data streams
Theory of Computing | 2024-01-16 | Paper |
scientific article; zbMATH DE number 7788372 (Why is no real title available?)
(available as arXiv preprint) | 2024-01-15 | Paper |
On differential privacy and adaptive data analysis with bounded space
Advances in Cryptology – EUROCRYPT 2023 | 2023-12-12 | Paper |
Low-rank approximation with <i> 1/𝜖 <sup>1/3</sup> </i> matrix-vector products
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | 2023-12-08 | Paper |
Memory bounds for the experts problem
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | 2023-12-08 | Paper |
The Product of Gaussian Matrices is Close to Gaussian
(available as arXiv preprint) | 2023-11-20 | Paper |
Streaming Complexity of SVMs
(available as arXiv preprint) | 2023-10-31 | Paper |
Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems
(available as arXiv preprint) | 2023-10-31 | Paper |
Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams.
(available as arXiv preprint) | 2023-10-31 | Paper |
Tight Bounds for ℓ <sub>1</sub> Oblivious Subspace Embeddings
ACM Transactions on Algorithms | 2023-10-31 | Paper |
Towards Optimal Moment Estimation in Streaming and Distributed Models
ACM Transactions on Algorithms | 2023-10-23 | Paper |
scientific article; zbMATH DE number 7711619 (Why is no real title available?)
(available as arXiv preprint) | 2023-07-12 | Paper |
scientific article; zbMATH DE number 7650068 (Why is no real title available?)
(available as arXiv preprint) | 2023-02-03 | Paper |
Towards Optimal Moment Estimation in Streaming and Distributed Models
(available as arXiv preprint) | 2023-02-03 | Paper |
Pseudo-Deterministic Streaming.
(available as arXiv preprint) | 2023-02-03 | Paper |
Graph spanners in the message-passing model
(available as arXiv preprint) | 2023-02-03 | Paper |
| A fast, provably accurate approximation algorithm for sparse principal component analysis reveals human genetic variation across the world | 2022-08-30 | Paper |
scientific article; zbMATH DE number 7561590 (Why is no real title available?)
(available as arXiv preprint) | 2022-07-21 | Paper |
Robust communication-optimal distributed clustering algorithms
(available as arXiv preprint) | 2022-07-21 | Paper |
| Querying a Matrix Through Matrix-Vector Products. | 2022-07-21 | Paper |
| scientific article; zbMATH DE number 7559216 (Why is no real title available?) | 2022-07-18 | Paper |
| High-Dimensional Geometric Streaming in Polynomial Space | 2022-04-07 | Paper |
A Framework for Adversarially Robust Streaming Algorithms
Journal of the ACM | 2022-03-31 | Paper |
Querying a Matrix through Matrix-Vector Products
ACM Transactions on Algorithms | 2022-02-22 | Paper |
Querying a Matrix through Matrix-Vector Products
ACM Transactions on Algorithms | 2022-02-22 | Paper |
Tight bounds for the subspace sketch problem with applications
SIAM Journal on Computing | 2021-08-06 | Paper |
Nearly optimal distinct elements and heavy hitters on sliding windows
(available as arXiv preprint) | 2021-08-04 | Paper |
On sketching the \(q\) to \(p\) norms
(available as arXiv preprint) | 2021-08-04 | Paper |
On low-risk heavy hitters and sparse recovery schemes
(available as arXiv preprint) | 2021-08-04 | Paper |
Revisiting frequency moment estimation in random order streams
(available as arXiv preprint) | 2021-07-28 | Paper |
Sharper bounds for regularized data fitting
(available as arXiv preprint) | 2021-07-28 | Paper |
Improved algorithms for adaptive compressed sensing
(available as arXiv preprint) | 2021-07-28 | Paper |
High probability frequency moment sketches
(available as arXiv preprint) | 2021-07-28 | Paper |
Matrix completion and related problems via strong duality
(available as arXiv preprint) | 2021-06-15 | Paper |
Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
(available as arXiv preprint) | 2021-06-15 | Paper |
Perfect \(L_p\) sampling in a data stream
SIAM Journal on Computing | 2021-04-14 | Paper |
The Communication Complexity of Optimization
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms | 2021-02-02 | Paper |
Oblivious Sketching of High-Degree Polynomial Kernels
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms | 2021-02-02 | Paper |
Tight Bounds for the Subspace Sketch Problem with Applications
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms | 2021-02-02 | Paper |
Non-adaptive adaptive sampling on turnstile streams
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing | 2021-01-19 | Paper |
| Hutch++: Optimal Stochastic Trace Estimation | 2020-10-19 | Paper |
Fast regression with an \(\ell_{\infty}\) guarantee
(available as arXiv preprint) | 2020-05-27 | Paper |
Embeddings of Schatten norms with applications to data streams
(available as arXiv preprint) | 2020-05-27 | Paper |
| Non-convex matrix completion and related problems via strong duality | 2020-02-07 | Paper |
On approximating matrix norms in data streams
SIAM Journal on Computing | 2019-11-21 | Paper |
Testing matrix rank, optimally
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
A PTAS for <i>ℓ<sub>p</sub></i>-Low Rank Approximation
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
Relative error tensor low rank approximation
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
Tight bounds for _p oblivious subspace embeddings
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
The Query Complexity of Mastermind with \ell_p Distances
(available as arXiv preprint) | 2019-09-23 | Paper |
| Data streams and applications in computer science | 2019-07-03 | Paper |
An optimal lower bound for distinct elements in the message passing model
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
On sketching matrix norms and the top singular vector
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
Beating the Direct Sum Theorem in Communication Complexity with Implications for Sketching
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-05-15 | Paper |
Lower bounds for adaptive sparse recovery
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-05-15 | Paper |
The fast Cauchy transform and faster robust linear regression
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-05-15 | Paper |
| Transitive-closure spanners | 2019-05-06 | Paper |
An optimal algorithm for \(\ell_1\)-heavy hitters in insertion streams and related problems
ACM Transactions on Algorithms | 2019-03-28 | Paper |
Low-rank approximation and regression in input sparsity time
Journal of the ACM | 2018-08-02 | Paper |
Low-Rank PSD Approximation in Input-Sparsity Time
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Nearly-optimal bounds for sparse recovery in generic norms, with applications to k-median sketching
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Adaptive Matrix Vector Product
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Tight bounds for sketching the operator norm, Schatten norms, and subspace embeddings
(available as arXiv preprint) | 2018-04-19 | Paper |
| Stochastic streams: sample complexity vs. space complexity | 2018-03-02 | Paper |
When distributed computation is communication expensive
Distributed Computing | 2018-01-17 | Paper |
Optimal Approximate Matrix Product in Terms of Stable Rank
(available as arXiv preprint) | 2017-12-19 | Paper |
Faster kernel ridge regression using sketching and preconditioning
SIAM Journal on Matrix Analysis and Applications | 2017-11-06 | Paper |
| scientific article; zbMATH DE number 6789285 (Why is no real title available?) | 2017-10-10 | Paper |
Sketching for <i>M</i>-Estimators: A Unified Approach to Robust Regression
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | Paper |
| Optimal bounds for Johnson-Lindenstrauss transforms and streaming problems with sub-constant error | 2017-09-29 | Paper |
Weighted low rank approximations with provable guarantees
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2017-09-29 | Paper |
On approximating functions of the singular values in a stream
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2017-09-29 | Paper |
Communication lower bounds for statistical estimation problems via a distributed data processing inequality
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2017-09-29 | Paper |
Optimal principal component analysis in distributed and streaming models
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2017-09-29 | Paper |
Beating CountSketch for heavy hitters in insertion streams
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2017-09-29 | Paper |
| Tight bounds for graph problems in insertion streams | 2017-08-31 | Paper |
Low rank approximation with entrywise \(\ell_1\)-norm error
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
New algorithms for heavy hitters in data streams (invited talk)
(available as arXiv preprint) | 2017-07-14 | Paper |
| Certifying equality with limited interaction | 2017-03-22 | Paper |
Optimal CUR matrix decompositions
SIAM Journal on Computing | 2017-03-10 | Paper |
How does your crystal grow? A commentary on Burton, Cabrera and Frank (1951) ‘The growth of crystals and the equilibrium structure of their surfaces’
Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences | 2017-01-13 | Paper |
Certifying equality with limited interaction
Algorithmica | 2016-11-29 | Paper |
Frequent directions: simple and deterministic matrix sketching
SIAM Journal on Computing | 2016-09-23 | Paper |
The fast Cauchy transform and faster robust linear regression
SIAM Journal on Computing | 2016-06-16 | Paper |
On sketching quadratic forms
Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science | 2016-04-15 | Paper |
Space-efficient estimation of statistics over sub-sampled streams
Algorithmica | 2016-03-29 | Paper |
The Simultaneous Communication of Disjointness with Applications to Data Streams
Automata, Languages, and Programming | 2015-10-27 | Paper |
Amplification of One-Way Information Complexity via Codes and Noise Sensitivity
Automata, Languages, and Programming | 2015-10-27 | Paper |
A general method for estimating correlated aggregates over a data stream
Algorithmica | 2015-10-19 | Paper |
Beyond set disjointness: the communication complexity of finding the intersection
Proceedings of the 2014 ACM symposium on Principles of distributed computing | 2015-09-03 | Paper |
Spanners and sparsifiers in dynamic streams
Proceedings of the 2014 ACM symposium on Principles of distributed computing | 2015-09-03 | Paper |
| Optimal space lower bounds for all frequency moments | 2015-08-03 | Paper |
Turnstile streaming algorithms might as well be linear sketches
Proceedings of the forty-sixth annual ACM symposium on Theory of computing | 2015-06-26 | Paper |
Optimal CUR matrix decompositions
Proceedings of the forty-sixth annual ACM symposium on Theory of computing | 2015-06-26 | Paper |
Numerical linear algebra in the streaming model
Proceedings of the forty-first annual ACM symposium on Theory of computing | 2015-02-04 | Paper |
Sketching as a tool for numerical linear algebra
Foundations and Trends® in Theoretical Computer Science | 2015-01-22 | Paper |
| The communication and streaming complexity of computing the longest common and increasing subsequences | 2014-12-18 | Paper |
Optimal bounds for Johnson-Lindenstrauss transforms and streaming problems with subconstant error
ACM Transactions on Algorithms | 2014-12-05 | Paper |
When distributed computation is communication expensive
Lecture Notes in Computer Science | 2014-09-29 | Paper |
Steiner transitive-closure spanners of low-dimensional posets
Combinatorica | 2014-08-14 | Paper |
How robust are linear sketches to adaptive inputs?
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2014-08-07 | Paper |
Low rank approximation and regression in input sparsity time
Proceedings of the forty-fifth annual ACM symposium on Theory of Computing | 2014-08-07 | Paper |
On the Power of Adaptivity in Sparse Recovery
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science | 2014-07-30 | Paper |
(1 + eps)-Approximate Sparse Recovery
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science | 2014-07-30 | Paper |
The Data Stream Space Complexity of Cascaded Norms
2009 50th Annual IEEE Symposium on Foundations of Computer Science | 2014-07-25 | Paper |
Efficient Sketches for Earth-Mover Distance, with Applications
2009 50th Annual IEEE Symposium on Foundations of Computer Science | 2014-07-25 | Paper |
Fast moment estimation in data streams in optimal space
Proceedings of the forty-third annual ACM symposium on Theory of computing | 2014-06-05 | Paper |
Subspace embeddings for the L <sub>1</sub> -norm with applications
Proceedings of the forty-third annual ACM symposium on Theory of computing | 2014-06-05 | Paper |
Near-optimal private approximation protocols via a black box transformation
Proceedings of the forty-third annual ACM symposium on Theory of computing | 2014-06-05 | Paper |
| On the exact space complexity of sketching and streaming small norms | 2014-05-22 | Paper |
Lower bounds for sparse recovery
(available as arXiv preprint) | 2014-05-22 | Paper |
| Coresets and sketches for high dimensional subspace approximation problems | 2014-05-22 | Paper |
| 1-pass relative-error L_p-sampling with applications | 2014-05-22 | Paper |
Tight bounds for distributed functional monitoring
Proceedings of the forty-fourth annual ACM symposium on Theory of computing | 2014-05-13 | Paper |
| Fast approximation of matrix coherence and statistical leverage | 2014-04-01 | Paper |
Fast approximation of matrix coherence and statistical leverage
(available as arXiv preprint) | 2014-04-01 | Paper |
On deterministic sketching and streaming for sparse recovery and norm estimation
Linear Algebra and its Applications | 2014-03-03 | Paper |
Sublinear optimization for machine learning
Journal of the ACM | 2014-02-17 | Paper |
A quadratic lower bound for three-query linear locally decodable codes over any field
Journal of Computer Science and Technology | 2014-02-11 | Paper |
A Tight Lower Bound for High Frequency Moment Estimation with Small Error
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2013-10-04 | Paper |
Transitive-closure spanners
SIAM Journal on Computing | 2013-03-19 | Paper |
On deterministic sketching and streaming for sparse recovery and norm estimation
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2012-11-02 | Paper |
Lower bounds for local monotonicity reconstruction from transitive-closure spanners
SIAM Journal on Discrete Mathematics | 2012-09-12 | Paper |
Optimal Random Sampling from Distributed Streams Revisited
Lecture Notes in Computer Science | 2011-10-28 | Paper |
Tolerant algorithms
Algorithms – ESA 2011 | 2011-09-16 | Paper |
Streaming algorithms with one-sided estimation
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2011-08-17 | Paper |
Steiner transitive-closure spanners of low-dimensional posets
Automata, Languages and Programming | 2011-07-06 | Paper |
Epistemic privacy
Journal of the ACM | 2011-05-16 | Paper |
Lower bounds for local monotonicity reconstruction from transitive-closure spanners
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2010-09-10 | Paper |
A quadratic lower bound for three-query linear locally decodable codes over any field
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2010-09-10 | Paper |
Additive spanners in nearly quadratic time
Automata, Languages and Programming | 2010-09-07 | Paper |
Optimal approximations of the frequency moments of data streams
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Corruption and Recovery-Efficient Locally Decodable Codes
Lecture Notes in Computer Science | 2008-11-27 | Paper |
A Geometric Approach to Information-Theoretic Private Information Retrieval
SIAM Journal on Computing | 2008-08-14 | Paper |
Practical Cryptography in High Dimensional Tori
Lecture Notes in Computer Science | 2008-05-06 | Paper |
Revisiting the Efficiency of Malicious Two-Party Computation
Advances in Cryptology - EUROCRYPT 2007 | 2007-11-29 | Paper |
Fast Algorithms for the Free Riders Problem in Broadcast Encryption
Lecture Notes in Computer Science | 2007-09-04 | Paper |
Better Approximations for the Minimum Common Integer Partition Problem
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2007-08-28 | Paper |
Theory of Cryptography
Lecture Notes in Computer Science | 2007-02-12 | Paper |
Advances in Cryptology – CRYPTO 2004
Lecture Notes in Computer Science | 2005-08-23 | Paper |
| scientific article; zbMATH DE number 2086704 (Why is no real title available?) | 2004-08-11 | Paper |
Distributed Low Rank Approximation of Implicit Functions of a Matrix
(available as arXiv preprint) | N/A | Paper |
