Optimal lower bounds for sketching graph cuts

DOI10.1137/1.9781611975482.158MaRDI QIDQ5236348zbMATH OpenOpenAlexFDO

Authors Charles Carlson, Alexandra Kolla, Nikhil Srivastava, Luca Trevisan

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1712.10261

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: 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(nlogn/epsilo{n}^2)$ bits of space in the worst case, improving the $Omega(n/epsilo{n}^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.

Recommendations

• On sketching quadratic forms
• Sketching cuts in graphs and hypergraphs
• Dynamic Sketching for Graph Optimization Problems with Applications to Cut-Preserving Sketches
• \((1 + \Omega(1))\)-approximation to MAX-CUT requires linear space
• scientific article; zbMATH DE number 7053292

Cited in

(5)

• Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions
• Dynamic Sketching for Graph Optimization Problems with Applications to Cut-Preserving Sketches
• Tight bounds for the subspace sketch problem with applications
• Sketching cuts in graphs and hypergraphs
• On sketching quadratic forms

This page was built for publication: Optimal lower bounds for sketching graph cuts

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236348)