72 citations · 174 across the 24 of their papers we have counts for
10 papers · 1 filter
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…