18 citations · 66 across the 15 of their papers we have counts for
3 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…
From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More
Parinya Chalermsook, Marek Cygan, Guy Kortsarz +4
We consider questions that arise from the intersection between the areas of polynomial-time approximation algorithms, subexponential-time algorithms, and fixed-parameter tractable…
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…