| Publication | Date of Publication | Type |
|---|
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 |
Recovery from non-decomposable distance oracles
IEEE Transactions on Information Theory | 2024-07-19 | 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 |
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?)
| 2024-04-09 | Paper |
scientific article; zbMATH DE number 7829323 (Why is no real title available?)
| 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?)
| 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 1/𝜖 1/3 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
| 2023-11-20 | Paper |
Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams.
| 2023-10-31 | Paper |
Tight Bounds for ℓ 1 Oblivious Subspace Embeddings
ACM Transactions on Algorithms | 2023-10-31 | Paper |
Streaming Complexity of SVMs
| 2023-10-31 | Paper |
Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems
| 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?)
| 2023-07-12 | Paper |
Towards Optimal Moment Estimation in Streaming and Distributed Models
| 2023-02-03 | Paper |
Pseudo-Deterministic Streaming.
| 2023-02-03 | Paper |
Graph spanners in the message-passing model
| 2023-02-03 | Paper |
scientific article; zbMATH DE number 7650068 (Why is no real title available?)
| 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 |
Robust communication-optimal distributed clustering algorithms
| 2022-07-21 | Paper |
Querying a Matrix Through Matrix-Vector Products.
| 2022-07-21 | Paper |
scientific article; zbMATH DE number 7561590 (Why is no real title available?)
| 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 |
Tight bounds for the subspace sketch problem with applications
SIAM Journal on Computing | 2021-08-06 | Paper |
On sketching the \(q\) to \(p\) norms
| 2021-08-04 | Paper |
On low-risk heavy hitters and sparse recovery schemes
| 2021-08-04 | Paper |
Nearly optimal distinct elements and heavy hitters on sliding windows
| 2021-08-04 | Paper |
Revisiting frequency moment estimation in random order streams
| 2021-07-28 | Paper |
Sharper bounds for regularized data fitting
| 2021-07-28 | Paper |
Improved algorithms for adaptive compressed sensing
| 2021-07-28 | Paper |
High probability frequency moment sketches
| 2021-07-28 | Paper |
Matrix completion and related problems via strong duality
| 2021-06-15 | Paper |
Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
| 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
| 2020-05-27 | Paper |
Embeddings of Schatten norms with applications to data streams
| 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 ℓp-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 \(\ell_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
| 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 |
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 |
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 |
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 |
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 |
Low-Rank PSD Approximation in Input-Sparsity Time
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
| 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
| 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 M-Estimators: A Unified Approach to Robust Regression
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | 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 |
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 |
Optimal bounds for Johnson-Lindenstrauss transforms and streaming problems with sub-constant error
| 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)
| 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
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 |
Optimal CUR matrix decompositions
Proceedings of the forty-sixth annual ACM symposium on Theory of computing | 2015-06-26 | 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 |
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 |
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 |
How robust are linear sketches to adaptive inputs?
Proceedings of the forty-eighth 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 1 -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
| 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 |
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
| N/A | Paper |
