72 citations · 174 across the 24 of their papers we have counts for
3 papers · 2 filters
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…
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…
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…