Associate Professor of Mathematics (1035 Evans Hall)
Senior Scientist, Simons Institute (204 Calvin Lab)
UC Berkeley.
email: firstname at math.berkeley.edu.
Research Interests: theory of computing, spectral graph theory, random matrices, convex geometry, geometry of polynomials, numerical algorithms.
Fall 2025 Office Hours: by appointment
Current Teaching: none
Seminars: Student Discrete Analysis Seminar: schedule. Thursdays at 12:30pm in 732 Evans.
Spectral Theory Seminar (w/ Jitomirskaya and Zworski): schedule. Wednesdays 12:00pm-1:00pm in 939 Evans.
Papers:
Tight Bounds on Plurality (with A. Taylor), IPL96 (2005). [PDF]
Voting with Rubber Bands, Weights, and Strings (with D. Cervone, R. Dai, D. Gnoutcheff, G. Lanterman, A. Mackenzie, A. Morse, and W. Zwicker), Mathematical Social Sciences. [LINK]
On the Longest Path Algorithm for Reconstructing Trees from Distance Matrices (with L. Reyzin), IPL101 (2007). [PDF]
Learning and Verifying Graphs Using Queries, with a Focus on Edge Counting (with L. Reyzin), ALT 2007. [PDF][slides]
Graph Sparsification by Effective Resistances (with D. Spielman), STOC 2008, SICOMP special issue (2011). [arXiv][slides]
Twice-Ramanujan Sparsifiers (with J. Batson and D. Spielman), STOC 2009, SICOMP special issue + SIAM Review (2012),. [arXiv][slides][video] and [bourbaki notes] by Assaf Naor.
An Elementary Proof of the Restricted Invertibility Theorem (with D. Spielman), Israel J. Math 190 (2012).[arXiv][video]
On Contact Points of Convex Bodies, Geometric Aspects of Functional Analysis, Springer Lec. Notes in Math. (2012) [PDF]
Covariance Estimation for Distributions with 2+epsilon Moments (with R. Vershynin), Annals of Probability. [arXiv][slides]
Graph Densification (with M. Hardt and M. Tulsiani), ITCS 2012. [PDF]
Zero-One Rounding of Singular Vectors (with A. Deshpande and R. Kannan), ICALP 2012.[PDF]
A New Approach to Computing Maximum Flows using Electrical Flows (with Y. Lee and S. Rao), STOC 2013.[PDF][slides]
Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees (with A. Marcus and D. Spielman), Annals of Mathematics & FOCS 2013[arXiv][slides]
Interlacing Families II: Mixed Characteristic Polynomials and the Kadison-Singer Problem (with A. Marcus and D. Spielman), Annals of Mathematics [arXiv] and [blog post]
Spectral Sparsification of Graphs: Theory and Algorithms (with J. Batson, D. Spielman, and S-H. Teng), Communications of the ACM 2013. [PDF] and [technical perspective] by Assaf Naor.
Ramanujan Graphs and the Solution of the Kadison-Singer Problem. (with A. Marcus and D. Spielman), Proc. ICM 2014.[arxiv]
Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes (with A. Marcus and D. Spielman), FOCS 2015, SICOMP special issue.[arxiv]
Real Stability Testing (with P. Raghavendra and N. Ryder), ITCS 2017. [arxiv]
Aproximating the Largest Root and Applications to Interlacing Families (with N. Anari, S. Oveis Gharan, and A. Saberi), SODA 2018. [arxiv]
Asymptotically Optimal Multi-Paving (with M. Ravichandran), IMRN. [arxiv]
Group Synchronization on Grids (with E. Abbe, L. Massoulie, A. Montanari, and A. Sly), Mathematical Statistics and Learning. [arxiv]
An Alon-Boppana Type Bound for Weighted Graphs and Lowerbounds for Spectral Sparsification (with L. Trevisan), SODA 2018. [arxiv]
Localization of Electrical Flows (with A. Schild and S. Rao), SODA 2018. [arxiv]
A Matrix Expander Chernoff Bound (with A. Garg, Y. Lee, and Z. Song), STOC 2018. [arxiv][slides]
Exponential Lower Bounds on Spectrahedral Representations of Hyperbolicity Cones (with P. Raghavendra, N. Ryder, B. Weitz), SODA 2019. [arxiv][video]
Interlacing Families III: Sharper Restricted Invertibility Estimates (with A. Marcus and D. Spielman), Israel J. Math. [arxiv]
The Solution of the Kadison-Singer Problem (with A. Marcus), Proc. CDM 2016. [arxiv]
Optimal Lower Bounds for Sketching Graph Cuts (with C. Carlson, A. Kolla, and L. Trevisan), SODA 2019. [arxiv]
On Non-Localization of Eigenvectors of High Girth Graphs (with S. Ganguly), IMRN. [arxiv]
Finite Free Convolutions of Polynomials (with A. Marcus and D. Spielman), Probability Theory and Related Fields. [arxiv]
Gaussian Regularization of the Pseudospectrum and Davies' Conjecture (with J. Banks, S. Mukherjee, A. Kulkarni), Commun. Pure Appl. Math. [arxiv][video]
High-girth near-Ramanujan Graphs with Localized Eigenvectors (with N. Alon and S. Ganguly), Israel J. Math. [arxiv][slides]
Pseudospectral Shattering, the Sign Function, and Diagonalization in Nearly Matrix Multiplication Time (with J. Banks, J. Garza Vargas, A. Kulkarni), FOCS 2020, Found. Comp. Math.[arxiv][video]
On Concentration Inequalities for Random Matrix Products (with T. Kathuria and S. Mukherjee), unpublished note. [arxiv]
Overlaps, Eigenvalue Gaps, and Pseudospectrum under Real Ginibre and Absolutely Continuous Perturbations (with J. Banks, J. Garza Vargas, A. Kulkarni), Ann. l'Institute Henri Poincare B. [arxiv]
Scalar Poincare Implies Matrix Poincare (with A. Garg and T. Kathuria) Electron. Comm. Probab.[arxiv]
Support of Closed Walks and Second Eigenvalue Multiplicity of Graphs (with T. McKenzie and P. Rasmussen) STOC 2021. [arxiv]
A Spectral Approach to Polytope Diameter (with H. Narayanan and R. Shah) ITCS 2022, Discrete Comput. Geom. [arxiv].
Many Nodal Domains in Random Regular Graphs (with S. Ganguly, T. McKenzie, S. Mohanty) Comm. Math. Phys.. [arxiv][video].
Bit Complexity of Jordan Normal Form and Spectral Factorization (with P. Dey, R. Kannan, N. Ryder) ITCS 2023. [arxiv][video].
Global Convergence of Hessenberg Shifted QR I: Exact Arithmetic (with J. Banks, J. Garza-Vargas) Found. Comp. Math. [arxiv][slides].
Global Convergence of Hessenberg Shifted QR II: Finite Arithmetic (with J. Banks, J. Garza-Vargas) SIAM J. Matrix Analysis. [arxiv].
Global Convergence of Hessenberg Shifted QR III: Approximate Ritz Values via Shifted Inverse Iteration (with J. Banks, J. Garza-Vargas) SIAM J. Matrix Analysis. [arxiv].
On Eigenvalue Gaps of Integer Matrices (with A. Abrams, J. Pommersheim, Z. Landau). Mathematics of Computation. [arxiv].
The Complexity of Diagonalization. ISSAC 2023.[arxiv].
On the Ground State Energies of Discrete and Semiclassical Schrödinger Operators (with I. Detherage and Z. Stier). Pure and Applied Analysis. [arxiv].
Ramanujan Graphs and Interlacing Families. Proc. ICBS 2024. [arxiv].
Sparse Pseudospectral Shattering (with R. Shah and E. Zeng). Submitted. [arxiv].
On quantum to classical comparison for Davies generators (with J. Basso, S. Ganguly, A. Sinclair, Z. Stier, T-D. Vuong). QIP 2026. [arxiv].
Current Graduate Students:Zack Stier, Isabel Detherage, Joao Basso (co-advised with Lin Lin). Past Graduate Students: Rikhav Shah, Jorge Garza Vargas (co-advised with Dan Voiculescu), Theo McKenzie, Jess Banks, Satyaki Mukherjee, Archit Kulkarni, Nick Ryder, Aaron Schild (EECS, co-advised with Satish Rao)
