
Nikhil Srivastava
Associate Professor of Mathematics
1035 Evans Hall, UC Berkeley.
email: firstname at math.berkeley.edu.
Research Interests: theoretical computer science, algebraic graph theory, random matrices, asymptotic convex geometry, geometry of polynomials.
Office Hours: by appointment.

Current Teaching: none
Seminar: Student Discrete Analysis Seminar: schedule. Fridays at 12:30pm in 891 Evans.
Papers:
 Tight Bounds on Plurality (with A. Taylor), IPL 96 (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), to appear in Mathematical Social Sciences. [LINK]
 On the Longest Path Algorithm for Reconstructing Trees from Distance Matrices (with L. Reyzin), IPL 101 (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]
 TwiceRamanujan 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]
 ZeroOne 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 KadisonSinger 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 SH. Teng), Communications of the ACM 2013. [PDF] and [technical perspective] by Assaf Naor.
 Ramanujan Graphs and the Solution of the KadisonSinger 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 MultiPaving (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 AlonBoppana 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 KadisonSinger 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 NonLocalization 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]
 Highgirth nearRamanujan 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), submitted. [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. [arxiv].
 Many Nodal Domains in Random Regular Graphs (with S. Ganguly, T. McKenzie, S. Mohanty) Communications in Mathematical Physics, to appear. [arxiv] [video].
 Bit Complexity of Jordan Normal Form and Spectral Factorization (with P. Dey, R. Kannan, N. Ryder) ITCS 2023. [arxiv].
 Global Convergence of Hessenberg Shifted QR I: Dynamics (with J. Banks, J. GarzaVargas) preprint. [arxiv].
 Global Convergence of Hessenberg Shifted QR II: Numerical Stability (with J. Banks, J. GarzaVargas) preprint. [arxiv].
 Global Convergence of Hessenberg Shifted QR III: Approximate Ritz Values via Shifted Inverse Iteration (with J. Banks, J. GarzaVargas) preprint. [arxiv].
 On Eigenvalue Gaps of Integer Matrices (with A. Abrams, J. Pommersheim, Z. Landau). Mathematics of Computation, to appear.[arxiv].
CV: [PDF]
Thesis: Spectral Sparsification and Restricted Invertibility [PDF] [slides]
Advisor: Dan Spielman.
Current Graduate Students:Jorge Garza Vargas (coadvised with Dan Voiculescu), Rikhav Shah, Zack Stier.
Past Graduate Students: Theo McKenzie, Jess Banks, Satyaki Mukherjee, Archit Kulkarni, Nick Ryder, Aaron Schild (EECS, coadvised with Satish Rao)
Program Committees: ITCS 2023, ITCS 2021, STOC 2019, FOCS 2018, ITCS 2017, ICALP 2016, STOC 2015, FSTTCS 2012.
Organizational Activities: MSRI Hot Topics 3/15, BIRS Algebraic Graph Theory 7/16, IPAM Quantitative Linear Algebra, Spring 2018, Simons Geometry of Polynomials, Spring 2019.
IPAM lectures on Expected Characteristic Polynomials: one, two, three.
Simons Institute Tutorial on Graph Sparsification: one, two, three.
General Audience Talk on Graph Sparsification: [vimeo] (Kavli Frontiers of Science, Agra 2013)
Previous Teaching
Math 55, Discrete Mathematics
Fall 2021: Math 55, Discrete Mathematics
Spring 2021:Berkeley Connect
Spring 2021: Math 54
Fall 2020:Math 224A: Mathematical Methods for Physical Sciences.
Spring 2020: Math 54
Fall 2019:Math 224A: Mathematical Methods for Physical Sciences.
Fall 2018: Math 54
Spring 2018: Math 53, Multivariable Calculus.
Spring 2017/18: Berkeley Connect
Fall 2016: Math 54, Linear Algebra and Differential Equations.
Spring 2016: Math 55, Discrete Mathematics
Fall 2015: Math 185, Complex Analysis
Fall 2015: Math 270, Hot Topics: The Geometry of Polynomials in Algorithms, Combinatorics, and Probability
Spring 2015: Math 121A, Mathematical Tools for the Physical Sciences
Spring 2012: COS 521 Advanced Algorithms (Princeton)
Funding: I am grateful to the NSF and to the Sloan Foundation for generously supporting my research.
Previously, I was at Microsoft Research India, Princeton, MSRI, IAS, Yale, and Union College.