## Nikhil SrivastavaAssociate Professor of Mathematics1035 Evans Hall, UC Berkeley. email: firstname at math.berkeley.edu.
I am |

**Seminar:** Student Discrete Analysis Seminar. Wednesdays at 4pm. See Berkeley Math events for details.

**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]**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),*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)*preprint*. [arxiv] [video].**Bit Complexity of Jordan Normal Form and Spectral Factorization**(with P. Dey, R. Kannan, N. Ryder)*preprint*. [arxiv].**Global Convergence of Hessenberg Shifted QR I: Dynamics**(with J. Banks, J. Garza-Vargas)*preprint*. [arxiv].**Global Convergence of Hessenberg Shifted QR II: Numerical Stability**(with J. Banks, J. Garza-Vargas)*preprint*. [arxiv].**Global Convergence of Hessenberg Shifted QR III: Approximate Ritz Values via Shifted Inverse Iteration**(with J. Banks, J. Garza-Vargas)*preprint*. [arxiv].

**CV**: [PDF]

**Thesis: Spectral Sparsification and Restricted Invertibility** [PDF] [slides]

Advisor: Dan Spielman.

** Current Graduate Students:**Jorge Garza Vargas (co-advised with Dan Voiculescu), Theo McKenzie, Jess Banks, Rikhav Shah.

**Past Graduate Students:** Satyaki Mukherjee, Archit Kulkarni, Nick Ryder, Aaron Schild (EECS, co-advised with Satish Rao)

**Program Committees**: 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)

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.