| Publication | Date of Publication | Type |
|---|
| Solving sparse, symmetric, diagonally-dominant linear systems in time \(O(m^{1.31})\) | 2026-05-29 | Paper |
| Ramanujan graphs and interlacing families | 2026-01-13 | Paper |
| Interlacing families. IV: Bipartite Ramanujan graphs of all sizes | 2025-08-05 | Paper |
| Interlacing families. I: Bipartite Ramanujan graphs of all degrees | 2025-05-20 | Paper |
Balancing Covariates in Randomized Experiments with the Gram–Schmidt Walk Design
Journal of the American Statistical Association | 2024-12-10 | Paper |
| Hardness results for Weaver's discrepancy problem | 2024-08-22 | Paper |
| Robust and Practical Solution of Laplacian Equations by Approximate Elimination | 2023-03-01 | Paper |
The complexity of error-correcting codes
Fundamentals of Computation Theory | 2022-12-09 | Paper |
Interlacing families. III: Sharper restricted invertibility estimates
Israel Journal of Mathematics | 2022-05-31 | Paper |
Finite free convolutions of polynomials
Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete | 2022-04-21 | Paper |
Interlacing families. IV: Bipartite Ramanujan graphs of all sizes
SIAM Journal on Computing | 2018-12-19 | Paper |
Ramanujan graphs and the solution of the Kadison-Singer problem
(available as arXiv preprint) | 2017-10-25 | Paper |
Sparsified Cholesky and multigrid solvers for connection Laplacians
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2017-09-29 | Paper |
The Minimum Distance of Turbo-Like Codes
IEEE Transactions on Information Theory | 2017-08-08 | Paper |
Graphs, vectors, and matrices
Bulletin of the American Mathematical Society | 2016-12-20 | Paper |
Nearly-linear size holographic proofs
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 | 2016-09-01 | Paper |
A remark on matrix rigidity
Information Processing Letters | 2016-06-09 | Paper |
Interlacing families. I: Bipartite Ramanujan graphs of all degrees
Annals of Mathematics. Second Series | 2015-07-06 | Paper |
Interlacing families. II: Mixed characteristic polynomials and the Kadison-Singer problem
Annals of Mathematics. Second Series | 2015-07-06 | Paper |
An efficient parallel solver for SDD linear systems
Proceedings of the forty-sixth annual ACM symposium on Theory of computing | 2015-06-26 | Paper |
| Algorithms for Lipschitz Learning on Graphs | 2015-05-01 | Paper |
Randomness efficient identity testing of multivariate polynomials
Proceedings of the thirty-third annual ACM symposium on Theory of computing | 2015-02-27 | Paper |
Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time
Proceedings of the thirty-third annual ACM symposium on Theory of computing | 2015-02-27 | Paper |
Twice-Ramanujan sparsifiers
Proceedings of the forty-first annual ACM symposium on Theory of computing | 2015-02-04 | Paper |
Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems
SIAM Journal on Matrix Analysis and Applications | 2014-12-17 | 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 |
Twice-Ramanujan sparsifiers
SIAM Review | 2014-06-26 | 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 |
A Cheeger Inequality for the Graph Connection Laplacian
SIAM Journal on Matrix Analysis and Applications | 2014-04-30 | Paper |
A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning
SIAM Journal on Computing | 2013-07-04 | Paper |
Twice-Ramanujan sparsifiers
SIAM Journal on Computing | 2013-03-19 | Paper |
An elementary proof of the restricted invertibility theorem
Israel Journal of Mathematics | 2012-11-13 | Paper |
Algorithms, graph theory, and the solution of Laplacian linear equations
Automata, Languages, and Programming | 2012-11-01 | Paper |
Graph sparsification by effective resistances
SIAM Journal on Computing | 2012-03-15 | Paper |
| Algorithms, graph theory, and linear equations in Laplacian matrices | 2011-11-11 | Paper |
Spectral sparsification of graphs
SIAM Journal on Computing | 2011-11-07 | Paper |
Smoothed analysis of condition numbers and complexity implications for linear programming
Mathematical Programming. Series A. Series B | 2011-02-14 | Paper |
Smoothed analysis of algorithms
Journal of the ACM | 2010-08-17 | Paper |
Exponential algorithmic speedup by a quantum walk
Proceedings of the thirty-fifth annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Lower-stretch spanning trees
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
Proceedings of the thirty-sixth annual ACM symposium on Theory of computing | 2010-08-15 | Paper |
Smoothed analysis. Motivation and discrete models
Lecture Notes in Computer Science | 2010-04-20 | Paper |
Lower-Stretch Spanning Trees
SIAM Journal on Computing | 2009-04-30 | Paper |
| scientific article; zbMATH DE number 5485569 (Why is no real title available?) | 2009-01-05 | Paper |
| scientific article; zbMATH DE number 5485557 (Why is no real title available?) | 2009-01-05 | Paper |
Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices
SIAM Journal on Matrix Analysis and Applications | 2007-05-03 | Paper |
PARALLEL DELAUNAY REFINEMENT: ALGORITHMS AND ANALYSES
International Journal of Computational Geometry & Applications | 2007-03-21 | Paper |
Spectral partitioning works: planar graphs and finite element meshes
Linear Algebra and its Applications | 2007-03-09 | Paper |
| Smoothed analysis of algorithms and heuristics: progress and open questions | 2007-02-12 | Paper |
Fundamentals of Computation Theory
Lecture Notes in Computer Science | 2006-10-20 | Paper |
Euro-Par 2004 Parallel Processing
Lecture Notes in Computer Science | 2005-08-23 | Paper |
| scientific article; zbMATH DE number 1775410 (Why is no real title available?) | 2004-01-14 | Paper |
Smoothed analysis of termination of linear programming algorithms
Mathematical Programming. Series A. Series B | 2003-09-01 | Paper |
Improved low-density parity-check codes using irregular graphs
IEEE Transactions on Information Theory | 2002-08-04 | Paper |
Efficient erasure correcting codes
IEEE Transactions on Information Theory | 2002-08-04 | Paper |
Alternation in interaction
Computational Complexity | 2002-06-02 | Paper |
scientific article; zbMATH DE number 1962932 (Why is no real title available?)
(available as arXiv preprint) | 2002-01-01 | Paper |
Min-max-boundary domain decomposition
Theoretical Computer Science | 2001-08-20 | Paper |
| scientific article; zbMATH DE number 1552123 (Why is no real title available?) | 2001-08-07 | Paper |
| scientific article; zbMATH DE number 1559530 (Why is no real title available?) | 2001-02-28 | Paper |
Expander codes
IEEE Transactions on Information Theory | 2000-08-28 | Paper |
| scientific article; zbMATH DE number 1335886 (Why is no real title available?) | 1999-09-13 | Paper |
| scientific article; zbMATH DE number 1256777 (Why is no real title available?) | 1999-03-01 | Paper |
| scientific article; zbMATH DE number 1222827 (Why is no real title available?) | 1998-11-11 | Paper |
Linear-time encodable and decodable error-correcting codes
IEEE Transactions on Information Theory | 1997-06-12 | Paper |
PP is closed under intersection
Journal of Computer and System Sciences | 1995-06-08 | Paper |
| scientific article; zbMATH DE number 1263215 (Why is no real title available?) | 1995-01-01 | Paper |
The power of adaptiveness and additional queries in random-self- reductions
Computational Complexity | 1994-09-01 | Paper |
