# Sketching Cuts in Graphs and Hypergraphs

arXiv: https://arxiv.org/abs/1409.2391 · HTML: https://mlsanity.com/paper/1409.2391/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Sep 2014.

## Built on by (most cited first, 2 of 2)

- [Sparsification of Decomposable Submodular Functions](https://mlsanity.com/paper/2201.07289/) (2022)
- [Sparsifying Suprema of Gaussian Processes](https://mlsanity.com/paper/2411.14664/) (2024)

## Abstract (arXiv)

Sketching and streaming algorithms are in the forefront of current research directions for cut problems in graphs. In the streaming model, we show that (1-ε)-approximation for Max-Cut must use n1-O(ε) space; moreover, beating 4/5-approximation requires polynomial space. For the sketching model, we show that r-uniform hypergraphs admit a (1+ε)-cut-sparsifier (i.e., a weighted subhypergraph that approximately preserves all the cuts) with O(ε-2 n (r+log n)) edges. We also make first steps towards sketching general CSPs (Constraint Satisfaction Problems).