# Streaming Euclidean Max-Cut: Dimension vs Data Reduction

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Nov 2022.

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

- [Beyond Worst-Case Dimensionality Reduction for Sparse Vectors](https://mlsanity.com/paper/2502.19865/) (2025)
- [Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures](https://mlsanity.com/paper/2506.00165/) (2025)

## Abstract (arXiv)

Max-Cut is a fundamental problem that has been studied extensively in various settings. We design an algorithm for Euclidean Max-Cut, where the input is a set of points in ℝd, in the model of dynamic geometric streams, where the input Xsubseteq [Delta]d is presented as a sequence of point insertions and deletions. Previously, Frahling and Sohler [STOC 2005] designed a (1+ε)-approximation algorithm for the low-dimensional regime, i.e., it uses space exp(d). To tackle this problem in the high-dimensional regime, which is of growing interest, one must improve the dependence on the dimension d, ideally to space complexity poly(ε-1 d logDelta). Lammersen, Sidiropoulos, and Sohler [WADS 2009] proved that Euclidean Max-Cut admits dimension reduction with target dimension d' = poly(ε-1). Combining this with the aforementioned algorithm that uses space exp(d'), they obtain an algorithm whose overall space complexity is indeed polynomial in d, but unfortunately exponential in ε-1. We devise an alternative approach of data reduction, based on importance sampling, and achieve space bound poly(ε-1 d logDelta), which is exponentially better (in ε) than the dimension-reduction approach. To implement this scheme in the streaming model, we employ a randomly-shifted quadtree to construct a tree embedding. While this is a well-known method, a key feature of our algorithm is that the embedding's distortion O(dlogDelta) affects only the space complexity, and the approximation ratio remains 1+ε.