72 citations · 174 across the 24 of their papers we have counts for
33 papers
The Complexity of Diagonalization
Nikhil Srivastava
We survey recent progress on efficient algorithms for approximately diagonalizing a square complex matrix in the models of rational (variable precision) and finite (floating point)…
On Eigenvalue Gaps of Integer Matrices
Aaron Abrams, Zeph Landau, Jamie Pommersheim +1
Given an matrix with integer entries in the range , how close can two of its distinct eigenvalues be? The best previously known examples have a minimum gap of $…
Global Convergence of Hessenberg Shifted QR II: Numerical Stability
Jess Banks, Jorge Garza-Vargas, Nikhil Srivastava
We develop a framework for proving rapid convergence of shifted QR algorithms which use Ritz values as shifts, in finite arithmetic. Our key contribution is a dichotomy result whic…
Global Convergence of Hessenberg Shifted QR III: Approximate Ritz Values via Shifted Inverse Iteration
Jess Banks, Jorge Garza-Vargas, Nikhil Srivastava
We give a self-contained randomized algorithm based on shifted inverse iteration which provably computes the eigenvalues of an arbitrary matrix up to b…
Many nodal domains in random regular graphs
Shirshendu Ganguly, Theo McKenzie, Sidhanth Mohanty +1
Let be a random -regular graph. We prove that for every constant , with high probability every eigenvector of the adjacency matrix of with eigenvalue less than $-2…
Bit Complexity of Jordan Normal Form and Spectral Factorization
Papri Dey, Ravi Kannan, Nick Ryder +1
We study the bit complexity of two related fundamental computational problems in linear algebra and control theory. Our results are: (1) An $\tilde{O}(n^{ω+3}a+n^4a^2+n^ω\log(1/ε))…
A Spectral Approach to Polytope Diameter
Hariharan Narayanan, Rikhav Shah, Nikhil Srivastava
We prove upper bounds on the graph diameters of polytopes in two settings. The first is a worst-case bound for polytopes defined by integer constraints in terms of the height of th…
Support of Closed Walks and Second Eigenvalue Multiplicity of the Normalized Adjacency Matrix
Theo McKenzie, Peter M. R. Rasmussen, Nikhil Srivastava
We show that the multiplicity of the second normalized adjacency matrix eigenvalue of any connected graph of maximum degree is bounded by for an…
Scalar Poincaré Implies Matrix Poincaré
Ankit Garg, Tarun Kathuria, Nikhil Srivastava
We prove that every reversible Markov semigroup which satisfies a Poincaré inequality satisfies a matrix-valued Poincaré inequality for Hermitian matrix valued function…
Overlaps, Eigenvalue Gaps, and Pseudospectrum under real Ginibre and Absolutely Continuous Perturbations
Jess Banks, Jorge Garza Vargas, Archit Kulkarni +1
Let be an matrix with real i.i.d. entries, let be a real matrix with , and let . We show that with p…
On Concentration Inequalities for Random Matrix Products
Tarun Kathuria, Satyaki Mukherjee, Nikhil Srivastava
Consider complex random matrices of size sampled i.i.d. from a distribution with mean . While the concentration of averages of these matric…
High-girth near-Ramanujan graphs with localized eigenvectors
Noga Alon, Shirshendu Ganguly, Nikhil Srivastava
We show that for every prime and , there is an infinite sequence of -regular graphs with girth at least , second adjac…
Gaussian Regularization of the Pseudospectrum and Davies' Conjecture
Jess Banks, Archit Kulkarni, Satyaki Mukherjee +1
A matrix is diagonalizable if it has a basis of linearly independent eigenvectors. Since the set of nondiagonalizable matrices has measure zero, every…
On Non-localization of Eigenvectors of High Girth Graphs
Shirshendu Ganguly, Nikhil Srivastava
We prove improved bounds on how localized an eigenvector of a high girth regular graph can be, and present examples showing that these bounds are close to sharp. This study was ini…
Optimal Lower Bounds for Sketching Graph Cuts
Charles Carlson, Alexandra Kolla, Nikhil Srivastava +1
We study the space complexity of sketching cuts and Laplacian quadratic forms of graphs. We show that any data structure which approximately stores the sizes of all cuts in an undi…
The Solution of the Kadison-Singer Problem
Adam W. Marcus, Nikhil Srivastava
These lecture notes are meant to accompany two lectures given at the CDM 2016 conference, about the Kadison-Singer Problem. They are meant to complement the survey by the same auth…
Interlacing Families III: Sharper Restricted Invertibility Estimates
Adam W. Marcus, Daniel A. Spielman, Nikhil Srivastava
We use the method of interlacing families of polynomials to derive a simple proof of Bourgain and Tzafriri's Restricted Invertibility Principle, and then to sharpen the result in t…
Exponential lower bounds on spectrahedral representations of hyperbolicity cones
Prasad Raghavendra, Nick Ryder, Nikhil Srivastava +1
The Generalized Lax Conjecture asks whether every hyperbolicity cone is a section of a semidefinite cone of sufficiently high dimension. We prove that the space of hyperbolicity co…
Localization of Electrical Flows
Aaron Schild, Satish Rao, Nikhil Srivastava
We show that in any graph, the average length of a flow path in an electrical flow between the endpoints of a random edge is . This is a consequence of a more general…
An Alon-Boppana Type Bound for Weighted Graphs and Lowerbounds for Spectral Sparsification
Nikhil Srivastava, Luca Trevisan
We prove the following Alon-Boppana type theorem for general (not necessarily regular) weighted graphs: if is an -node weighted undirected graph of average combinatorial deg…
Group Synchronization on Grids
Emmanuel Abbe, Laurent Massoulie, Andrea Montanari +2
Group synchronization requires to estimate unknown elements of a compact group associated to the vertices of a graph , using noisy observa…
Asymptotically Optimal Multi-Paving
Mohan Ravichandran, Nikhil Srivastava
Anderson's paving conjecture, now known to hold due to the resolution of the Kadison-Singer problem asserts that every zero diagonal Hermitian matrix admits non-trivial pavings wit…
Approximating the Largest Root and Applications to Interlacing Families
Nima Anari, Shayan Oveis Gharan, Amin Saberi +1
We study the problem of approximating the largest root of a real-rooted polynomial of degree using its top coefficients and give nearly matching upper and lower bounds. We…
A Matrix Expander Chernoff Bound
Ankit Garg, Yin Tat Lee, Zhao Song +1
We prove a Chernoff-type bound for sums of matrix-valued random variables sampled via a random walk on an expander, confirming a conjecture due to Wigderson and Xiao. Our proof is…