| Publication | Date of Publication | Type |
|---|
Fast sampling of satisfying assignments from random \(k\)-SAT with applications to connectivity
SIAM Journal on Discrete Mathematics | 2024-11-05 | Paper |
| Sums of squares in theoretical computer science | 2024-07-16 | Paper |
| From algorithms to connectivity and back: finding a giant component in random \(k\)-SAT | 2024-05-14 | Paper |
| Robust voting rules from algorithmic robust statistics | 2024-05-14 | Paper |
| Planning and learning in partially observable systems via filter stability | 2024-05-08 | Paper |
Kalman filtering with adversarial corruptions
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | 2023-12-08 | Paper |
Settling the robust learnability of mixtures of Gaussians
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
Algorithmic foundations for the diffraction limit
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
| The Power of an Adversary in Glauber Dynamics | 2023-02-21 | Paper |
| A New Approach to Learning Linear Dynamical Systems | 2023-01-23 | Paper |
| Minimax Rates for Robust Community Detection | 2022-07-25 | Paper |
The Paulsen problem made simple
(available as arXiv preprint) | 2022-07-18 | Paper |
Noisy tensor completion via the sum-of-squares hierarchy
Mathematical Programming. Series A. Series B | 2022-06-14 | Paper |
The Paulsen problem made simple
Israel Journal of Mathematics | 2022-04-25 | Paper |
| Semirandom Stochastic Block Models | 2022-02-04 | Paper |
| Topic Models and Nonnegative Matrix Factorization | 2022-02-04 | Paper |
Efficiently learning structured distributions from untrusted batches
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing | 2021-01-19 | Paper |
| Fast Convergence for Langevin Diffusion with Manifold Structure | 2020-02-13 | Paper |
Spectral methods from tensor networks
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
Beyond the low-degree algorithm: mixtures of subcubes and their applications
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
Learning restricted Boltzmann machines via influence maximization
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
Approximate counting, the Lovász local lemma, and inference in graphical models
Journal of the ACM | 2019-11-21 | Paper |
Improved bounds for randomly sampling colorings via linear programming
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
A polynomial-time approximation scheme for fault-tolerant distributed storage
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
How many subpopulations is too many? Exponential lower bounds for inferring population histories
(available as arXiv preprint) | 2019-05-21 | Paper |
| How many subpopulations is too many? Exponential lower bounds for inferring population histories | 2019-05-21 | Paper |
An almost optimal algorithm for computing nonnegative rank
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-05-15 | Paper |
Robust estimators in high-dimensions without the computational intractability
SIAM Journal on Computing | 2019-05-07 | Paper |
A nearly tight sum-of-squares lower bound for the planted clique problem
SIAM Journal on Computing | 2019-05-07 | Paper |
Message-passing algorithms for synchronization problems over compact groups
Communications on Pure and Applied Mathematics | 2018-11-02 | Paper |
Optimality and sub-optimality of PCA. I: Spiked random matrix models
The Annals of Statistics | 2018-10-24 | Paper |
Optimality and sub-optimality of PCA. I: Spiked random matrix models
The Annals of Statistics | 2018-10-24 | Paper |
The Paulsen Problem Made Simple
(available as arXiv preprint) | 2018-09-12 | Paper |
| Algorithmic aspects of machine learning | 2018-07-26 | Paper |
| Linear Programming Bounds for Randomly Sampling Colorings | 2018-04-09 | Paper |
| Robustly learning a Gaussian: getting optimal error, efficiently | 2018-03-15 | Paper |
Robustly learning a Gaussian: getting optimal error, efficiently
(available as arXiv preprint) | 2018-03-15 | Paper |
| Capacitated metric labeling | 2017-09-29 | Paper |
Approximate counting, the Lovász local lemma, and inference in graphical models
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
| Rates of estimation for determinantal point processes | 2017-06-03 | Paper |
Efficient Coding for Interactive Communication
IEEE Transactions on Information Theory | 2017-05-16 | Paper |
| Learning Determinantal Point Processes with Moments and Cycles | 2017-03-01 | Paper |
| Maximum likelihood estimation of determinantal point processes | 2017-01-23 | Paper |
| Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization | 2016-09-18 | Paper |
Computing a nonnegative matrix factorization -- provably
SIAM Journal on Computing | 2016-09-02 | Paper |
An almost optimal algorithm for computing nonnegative rank
SIAM Journal on Computing | 2016-02-05 | Paper |
Super-resolution, extremal functions and the condition number of Vandermonde matrices
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing | 2015-08-21 | Paper |
Smoothed analysis of tensor decompositions
Proceedings of the forty-sixth annual ACM symposium on Theory of computing | 2015-06-26 | Paper |
Provable ICA with unknown Gaussian noise, and implications for Gaussian mixtures and autoencoders
Algorithmica | 2015-05-21 | Paper |
Efficiently learning mixtures of two Gaussians
Proceedings of the forty-second ACM symposium on Theory of computing | 2014-08-13 | Paper |
Extensions and limits to vertex sparsification
Proceedings of the forty-second ACM symposium on Theory of computing | 2014-08-13 | Paper |
An information complexity approach to extended formulations
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2014-08-07 | Paper |
Efficient and Explicit Coding for Interactive Communication
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science | 2014-07-30 | Paper |
Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size
2009 50th Annual IEEE Symposium on Foundations of Computer Science | 2014-07-25 | Paper |
Dueling algorithms
Proceedings of the forty-third annual ACM symposium on Theory of computing | 2014-06-05 | Paper |
Pareto optimal solutions for smoothed analysts
Proceedings of the forty-third annual ACM symposium on Theory of computing | 2014-06-05 | Paper |
Computing a nonnegative matrix factorization -- provably
Proceedings of the forty-fourth annual ACM symposium on Theory of computing | 2014-05-13 | Paper |
Nearly complete graphs decomposable into large induced matchings and their applications
Proceedings of the forty-fourth annual ACM symposium on Theory of computing | 2014-05-13 | Paper |
Vertex sparsification and oblivious reductions
SIAM Journal on Computing | 2014-04-11 | Paper |
Nearly complete graphs decomposable into large induced matchings and their applications
Journal of the European Mathematical Society (JEMS) | 2013-09-02 | Paper |
Pareto optimal solutions for smoothed analysts
SIAM Journal on Computing | 2013-02-04 | Paper |
Some results on greedy embeddings in metric spaces
Discrete & Computational Geometry | 2010-11-08 | Paper |
Strong spatial mixing for colorings on trees and its algorithmic applications
(available as arXiv preprint) | N/A | Paper |
High-Temperature Gibbs States are Unentangled and Efficiently Preparable
(available as arXiv preprint) | N/A | Paper |
