Optimal Lower Bounds for Sketching Graph Cuts

DOI10.1137/1.9781611975482.158zbMath1432.68343arXiv1712.10261OpenAlexW2780845556MaRDI QIDQ5236348

Luca Trevisan, Alexandra Kolla, Charles Carlson, Nikhil Srivastava

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)

Related Items (2)

Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions ⋮ Tight Bounds for the Subspace Sketch Problem with Applications

This page was built for publication: Optimal Lower Bounds for Sketching Graph Cuts