| 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
| 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
| 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 |
The Paulsen Problem Made Simple
| 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 |
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
| N/A | Paper |
High-Temperature Gibbs States are Unentangled and Efficiently Preparable
| N/A | Paper |
