Fetching the paper…

Reading the bibliography…

2017

Optimal Lower Bounds for Sketching Graph Cuts

Carlson, Charles, Kolla, Alexandra, Srivastava, Nikhil et al.

Original
PDF
Post on X

Understand

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 undirected graph on $n$ vertices up to a $1+\epsilon$ error must use $\Omega(n\log n/\epsilon^2)$ bits of space in the worst case, improving the $\Omega(n/\epsilon^2)$ bound of Andoni et al.
and matching the best known upper bound achieved by spectral sparsifiers.
Our proof is based on a rigidity phenomenon for cut (and spectral) approximation which may be of independent interest: any two $d-$regular graphs which approximate each other's cuts significantly better than a random graph approximates the complete graph must overlap in a constant fraction of their edges.

Optimal Lower Bounds for Sketching Graph Cuts · Around

Built on

On the second eigenvalue of a graph
Alon Nilli · 1991
Earlier work this paper cites.
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
Michel X Goemans and David P Williamson · 1995
Earlier work this paper cites.
Approximating st minimum cuts in õ (n 2) time
András A Benczúr and David R Karger · 1996
Earlier work this paper cites.
Models of random regular graphs
Nicholas C Wormald · 1999
Earlier work this paper cites.
A proof of alon’s second eigenvalue conjecture
Joel Friedman · 2003
Earlier work this paper cites.

Similar

Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
Daniel A Spielman and Shang-Hua Teng · 2004
Cited alongside, same era.
A general framework for graph sparsification
Wai Shing Fung, Ramesh Hariharan, Nicholas JA Harvey, and Debmalya Panigrahi · 2011
Cited alongside, same era.
Graph sparsification by effective resistances
Daniel A Spielman and Nikhil Srivastava · 2011
Cited alongside, same era.
Twice-ramanujan sparsifiers
Joshua Batson, Daniel A Spielman, and Nikhil Srivastava · 2012
Cited alongside, same era.

Then

Spectral sparsification and regret minimization beyond matrix multiplicative updates
Zeyuan Allen-Zhu, Zhenyu Liao, and Lorenzo Orecchia · 2015
Later among the works it cites.
On sketching quadratic forms
Alexandr Andoni, Jiecao Chen, Robert Krauthgamer, Bo Qin, David P Woodruff, and Qin Zhang · 2016
Later among the works it cites.
Efficient o ⁡ ( n / ϵ ) o(n/\epsilon) spectral sketches for the laplacian and its pseudoinverse
Original
Arun Jambulapati and Aaron Sidford · 2017
Closest in time.
An sdp-based algorithm for linear-sized spectral sparsification
Original
Yin Tat Lee and He Sun · 2017
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…