Optimal lower bounds for sketching graph cuts

DOI10.1137/1.9781611975482.158zbMATH Open1432.68343arXiv1712.10261OpenAlexW2780845556MaRDI QIDQ5236348FDOQ5236348

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)

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.

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

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

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)

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)