**Hardness Results for Weaver's Discrepancy Problem***LIPIcs, Volume 245, Proceedings of Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)*. 2022- With Peng Zhang
- ArXiv version

**Interlacing Families III: Sharper Restricted Invertibility Estimates***Israel Journal of Mathematics volume 247, pages 519–546*. 2022- With Adam W. Marcus and Nikhil Srivastava
- arXiv version

**Finite free convolutions of polynomials***Probability Theory and Related Fields volume 182, pages 807–848*. 2022- With Adam Marcus and Nikhil Srivastava
- arXiv version

**Balancing covariates in randomized experiments using the Gram-Schmidt walk***https://arxiv.org/abs/1911.03071*. 2019- With Christopher Harshaw, Fredrik Savje and Peng Zhang
- Julia code: GSWDesign.jl
- Video of a talk on this

**Spectral and Algebraic Graph Theory***Book in progress*. 2019

**Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes***SIAM Journal on Computing, Vol 47, no. 6. 2488-2509*. 2018- With Adam W. Marcus and Nikhil Srivastava

**Graphs, Vectors, and Matrices***Bulletin (New Series) of the American Mathematical Society, Vol. 54, no. 1, pp. 45-61*. 2017

**Sparsified Cholesky and Multigrid Solvers for Connection Laplacians***ACM STOC*. 2016- With Rasmus Kyng, Yin Tat Lee, Richard Peng and Sushant Sachdeva

**Algorithms for Lipschitz Learning on Graphs***COLT*. 2015- With Rasmus Kyng, Anup Rao and Sushant Sachdeva
- Code on github

**Sparsified Cholesky Solvers for SDD linear systems***http://arxiv.org/abs/1506.08204*. 2015- With Yin Tat Lee and Richard Peng

**Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees***Annals of Mathematics, 182 (1), pp. 307-325*. 2015- With Adam Marcus and Nikhil Srivastava
- There was an earlier version on arXiv, of which the journal paper is a slight improvement

**Interlacing Families II: Mixed Characteristic Polynomials and the Kadison-Singer Problem***Annals of Mathematics, 182 (1), pp. 327-350*. 2015- With Adam Marcus and Nikhil Srivastava
- An earlier version appeared on arXiv

**Ramanujan Graphs and the Solution of the Kadison-Singer Problem***Proceedings of the 2014 International Congress of Mathematicians, vol. 3, pp. 363-386.*. 2014- With Adam W. Marcus and Nikhil Srivastava

**Twice-Ramanujan Sparsifiers (Sigest)***SIAM Review, Vol. 56, Issue 2, pp. 315-334*. 2014- With Joshua Batson and Nikhil Srivastava

**An Efficient Parallel Solver for SDD Linear Systems***STOC 2014*. 2014- With Richard Peng

**Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems***SIAM J. Matrix Anal. & Appl. 35-3, pp. 835-885*. 2014- With Shang-Hua Teng
- This page contains links to related papers.

**Spectral Sparsification of Graphs: Theory and Algorithms***Communications of the ACM, Vol. 56 No. 8, Pages 87-94*. 2013- With Josh Batson, Nikhil Srivastava and Shang-Hua Teng
- Technical Perspective by Assaf Naor

**A Local Clustering Algorithm for Massive Graphs and its Application to Nearly-Linear Time Graph Partitioning***SIAM Journal on Computing, vol 42 (1), pp. 1-26*. 2013- With Shang-Hua Teng
- A page related to this and related work

**A Cheeger Inequality for the Graph Connection Laplacian***SIAM Journal on Matrix Analysis, Vol. 24, Issue 4, pp. 1611-1630*. 2013- With Afonso S. Bandeira and Amit Singer

**Twice-Ramanujan Sparsifiers***SICOMP, Vol 41, Number 6, pp. 1704-1721*. 2012- With Joshua Batson and Nikhil Srivastava

**Exact Recovery of Sparsely-Used Dictionaries***Conference on Learning Theory*. 2012- With Huan Wang and John Wright
- Won award for best paper.

**Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs***In Proceedings of STOC 2011.*. 2011- With Paul Christiano, Jonathan A. Kelner, Aleksander Madry and Shang-Hua Teng
- Shared award for best paper

**Graph Sparsification by Effective Resistances***SIAM Journal on Computing, Vol. 40, No. 6, pp. 1913-1926*. 2011- With Nikhil Srivastava
- Conference version appeared in STOC '08

**Spectral Sparsification of Graphs***SIAM Journal on Computing, vol. 40, pp. 981-1025*. 2011- With Shang-Hua Teng
- My page about this and the related papers.

**Spectral Graph Theory***to appear in Combinatorial Scientific Computing. Chapman and Hall/CRC Press*. 2011

**Algorithms, Graph Theory, and Linear Equations***Proceedings of the International Congress of Mathematicians, vol IV, pp. 2698--2722.*. 2010

**Smoothed Analysis: An Attempt to Explain the Behavior of Algorithms in Practice***Communications of the ACM, Oct 2009, pp. 76-84*. 2009- With Shang-Hua Teng

**An Elementary Proof of the Restricted Invertibility Theorem***To appear in the Israeli Journal of Mathematics*. 2009- With Nikhil Srivastava

**Fitting a Graph to Vector Data***ICML*. 2009- With Jon Kelner and Sam Daitch

**A Note on Preconditioning by Low-Stretch Spanning Trees***http://arxiv.org/abs/0903.2816*. 2009- With Jaeoh Woo

**Smoothed analysis of condition numbers and complexity implications for linear programming***Mathematical Programming, Series A,*. 2009- With John D. Dunagan and Shang-Hua Teng
- Previously appeared as Smoothed Analysis of Renegar's Condition Number for Linear Programming

**The Minimum Distance of Turbo-Like Codes***IEEE Transactions on Information Theory, Vol 55, Issue 1, Jan 2009, pages 6-15*. 2009- With Louay Bazzi and Mohammad Mahdian

**The beauty of error-correcting codes***Communications of the ACM, March 2009, page 86*. 2009

**Faster Approximate Lossy Generalized Flow via Interior Point Algorithms***STOC '08*. 2008- With Samuel I. Daitch

**Lower-Stretch Spanning Trees***SIAM Journal on Computing, Vol 32 (2), pp. 608--628*. 2008- With Michael Elkin, Yuval Emek and Shang-Hua Teng

**Parallel Delaunay Refinement: Algorithms and Analyses***International Journal of Computational Geometry & Applications, Vol. 17, No. 1 (2007) 1-30*. 2007- With Shang-Hua Teng and Alper Ungor

**Support-Graph Preconditioners for 2-Dimensional Trusses***http://arxiv.org/abs/cs/0703119*. 2007- With Samuel I. Daitch

**Spectral Partitioning Works: Planar graphs and finite element meshes***Linear Algebra and its Applications Volume 421, Issues 2-3, 1 March 2007, Pages 284-305*. 2007- With Shang-Hua Teng

**Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices***SIMAX Volume 28, Issue 2, pp. 446-476*. 2006- With Arvind Sankar and Shang-Hua Teng

**Accelerated Gossip Algorithms for Distributed Computation***44th Annual Allerton Conference on Communication, Control, and Computation*. 2006- With Ming Cao and Edmund Yeh

**A Randomized Polynomial-Time Simplex Algorithm for Linear Programming***Proceedings of the 38th annual ACM symposium on Theory of computing*. 2006- With Jonathan A. Kelner

**A Lower Bound on Convergence of a Distributed Network Consensus Algorithm***44th IEEE Conference on Decision and Control*. 2005- With Ming Cao and Stephen Morse

**Smoothed Analysis of Algorithms: Why The Simplex Algorithm Usually Takes Polynomial Time***Journal of the ACM, Vol 51 (3), pp. 385 - 463*. 2004- With Shang-Hua Teng

**Parallel Delaunay Refinement with Off-Centers***10th International EURO-PAR Conference, pp. 812--819*. 2004- With Shang-Hua Teng and Alper Ungor

**Nearly-Linear Time Algorithms for Graph Partitioning, Graph Sparsification, and Solving Linear Systems***Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pp. 81--90*. 2004- With Shang-Hua Teng

**Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time O (m^{1.31})***Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, pp. 416-427*. 2003- With Shang-Hua Teng

**Smoothed Analysis of Termination of Linear Programming Algorithms***Mathematical Programming, Series B, Vol 97, pp. 375-404*. 2003- With Shang-Hua Teng

**Smoothed Analysis: Motivation and Discrete Models***Proceedings of WADS 2003, Lecture Notes in Computer Science 2748, pp. 256-270*. 2003- With Shang-Hua Teng

**Exponential algorithmic speedup by a quantum walk***Proceedings of the 35th Annual ACM Symposium on the Theory of Computing, pp. 59-68*. 2003- With Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi and Sam Gutmann

**Parallel Delaunay Refinement***Proceedings of the 11th International Meshing Roundtable. Submitted for publication.*. 2002- With Shang-Hua Teng and Alper Ungor

**Smoothed Analysis of Algorithms***Proceedings of the International Congress of Mathematicians, vol I, pp. 597-606*. 2002- With Shang-Hua Teng
- Our personal version of the paper.

**Improved Low-Density Parity-Check Codes Using Irregular Graphs***IEEE Transactions on Information Theory, 47(2), pp. 585-598*. 2001- With Michael G. Luby, Michael Mitzenmacher and M. Amin Shokrollahi

**Efficient Erasure Correcting Codes***IEEE Transactions on Information Theory, 47(2), pp. 569-584*. 2001- With Michael G. Luby, Michael Mitzenmacher and M. Amin Shokrollahi

**Min-Max-Boundary Domain Decomposition***Special issue of Theoretical Computer Science for COCOON'98, volume 261, issue 2, pp. 253-266*. 2001- With Marcos Kiwi and Shang-Hua Teng

**Randomness Efficient Identity Testing***Proceedings of the 33rd Symposium on Theory of Computing*. 2001- With Adam R. Klivans

**Alternation in Interaction***Computational Complexity, 9(3-4):202-246*. 2000- With Marcos Kiwi, Carsten Lund, Alex Russell and Ravi Sundaram

**Finding good LDPC codes***Proceedings of the 36th Annual Allerton Conference on Communication, Control, and Computing*. 1998

**A Remark on Matrix Rigidity***Information Processing Letters, 64(6), pp. 283--285*. 1997- With M. Amin Shokrollahi and Voelker Stemann

**The complexity of error-correcting codes***Plenary lecture at the 11th International Symposium on Fundamentals of Computation Theory, Krakow, Poland, Lecture Notes in Computer Science #1279, pp. 67-84*. 1997

**Linear-time encodable and decodable error-correcting codes***IEEE Transactions on Information Theory, Vol 42, No 6, pp. 1723-1732*. 1996

**Expander Codes***IEEE Transactions on Information Theory, , Vol 42, No 6, pp. 1710-1722*. 1996- With Michael Sipser

**Faster Isomorphism Testing of Strongly Regular Graphs***28th Annual ACM Symposium on Theory of Computing, pages 576-584*. 1996

**Highly Fault-Tolerant Parallel Computation***Proceedings of the 37th Annual IEEE Conference on Foundations of Computer Science, pp. 154-163*. 1996

**Disk Packings and Planar Separators****SCG 96:**12th Annual ACM Symposium on Computational Geometry, pages 349-358- With Shang-Hua Teng

**Constructing Error-Correcting Codes from Expander Graphs***Emerging Applications of Number Theory, IMA volumes in mathematics and its applications, vol 109*. 1996

**Thesis: Computationally Efficient Error-Correcting Codes and Holographic Proofs***My thesis, M.I.T. Department of Mathematics*. 1995

**PP is closed under intersection***Journal of Computer and System Sciences, vol. 50, no. 2, pp. 191-202*. 1995- With Richard Beigel and Nick Reingold

**Nearly linear-size holographic proofs***Proceedings of the 26th Annual ACM Symposium on the Theory of Computing, pp. 194-203*. 1994- With Alexander Polishchuk

**The Power of Adaptiveness and Additional Queries in Random-Self-Reductions***Computational Complexity, vol. 4, pp. 158-174*. 1994- With Joan Feigenbaum, Lance Fortnow and Carsten Lund

**Fault Diagnosis in a Small Constant Number of Parallel Testing Rounds***Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures*. 1993- With Richard Beigel and Grigorii Margulis

**The Perceptron Strikes Back***Proceedings of the 6th Annual IEEE Conference on Structure in Complexity Theory, pp. 286-291*. 1991- With Richard Beigel and Nick Reingold