| Publication | Date of Publication | Type |
|---|
| Matrix completion in almost-verification time | 2025-08-15 | Paper |
| On the power of preconditioning in sparse linear regression | 2025-08-13 | Paper |
| High-precision estimation of random walks in small space | 2025-08-12 | Paper |
| Solving directed Laplacian systems in nearly-linear time through sparse LU factorizations | 2025-08-12 | Paper |
| Faster algorithms for computing the stationary distribution, simulating random walks, and more | 2025-08-06 | Paper |
| A nearly tight sum-of-squares lower bound for the planted clique problem | 2025-08-06 | Paper |
An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
A nearly tight sum-of-squares lower bound for the planted clique problem
SIAM Journal on Computing | 2019-05-07 | Paper |
Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
Rumor spreading with no dependence on conductance
SIAM Journal on Computing | 2017-02-15 | Paper |
Randomized accuracy-aware program transformations for efficient approximate computations
Proceedings of the 39th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages | 2015-09-11 | Paper |
Dictionary learning and tensor decomposition via the sum-of-squares method
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing | 2015-08-21 | Paper |
Rounding sum-of-squares relaxations
Proceedings of the forty-sixth annual ACM symposium on Theory of computing | 2015-06-26 | Paper |
A randomized polynomial-time simplex algorithm for linear programming
Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing | 2014-11-25 | Paper |
A simple, combinatorial algorithm for solving SDD systems in nearly-linear time
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2014-08-07 | Paper |
Local Graph Partitions for Approximation and Testing
2009 50th Annual IEEE Symposium on Foundations of Computer Science | 2014-07-25 | Paper |
Faster Generation of Random Spanning Trees
2009 50th Annual IEEE Symposium on Foundations of Computer Science | 2014-07-25 | Paper |
Higher Eigenvalues of Graphs
2009 50th Annual IEEE Symposium on Foundations of Computer Science | 2014-07-25 | Paper |
Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs
Proceedings of the forty-third annual ACM symposium on Theory of computing | 2014-06-05 | Paper |
Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs
Proceedings of the forty-third annual ACM symposium on Theory of computing | 2014-06-05 | Paper |
Global computation in a poorly connected world
Proceedings of the forty-fourth annual ACM symposium on Theory of computing | 2014-05-13 | Paper |
Hypercontractivity, sum-of-squares proofs, and their applications
Proceedings of the forty-fourth annual ACM symposium on Theory of computing | 2014-05-13 | Paper |
Faster approximate multicommodity flow using quadratically coupled flows
Proceedings of the forty-fourth annual ACM symposium on Theory of computing | 2014-05-13 | Paper |
Spectral sparsification in the semi-streaming setting
Theory of Computing Systems | 2013-10-21 | Paper |
Topology discovery of sparse random graphs with few participants
Random Structures & Algorithms | 2013-08-27 | Paper |
Metric uniformization and spectral bounds for graphs
Geometric and Functional Analysis. GAFA | 2012-01-24 | Paper |
| Spectral sparsification in the semi-streaming setting | 2012-01-23 | Paper |
| scientific article; zbMATH DE number 5983877 (Why is no real title available?) | 2011-12-01 | Paper |
Electric routing and concurrent flow cutting
Theoretical Computer Science | 2011-07-27 | Paper |
Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus
Proceedings of the thirty-sixth annual ACM symposium on Theory of computing | 2010-08-15 | Paper |
Electric routing and concurrent flow cutting
Algorithms and Computation | 2009-12-17 | Paper |
Stochastic Shortest Paths Via Quasi-convex Maximization
Lecture Notes in Computer Science | 2008-03-11 | Paper |
Spectral Partitioning, Eigenvalue Bounds, and Circle Packings for Graphs of Bounded Genus
SIAM Journal on Computing | 2006-06-01 | Paper |
Multiple description vector quantization with a coarse lattice
IEEE Transactions on Information Theory | 2002-08-04 | Paper |
Quantized frame expansions with erasures
Applied and Computational Harmonic Analysis | 2001-09-09 | Paper |
Learning Mixtures of Gaussians Using Diffusion Models
(available as arXiv preprint) | N/A | Paper |
