Streaming Max-Cut in General Metrics
Pith reviewed 2026-05-18 09:53 UTC · model grok-4.3
The pith
A (1+ε)-approximation for Max-Cut in sliding-window streams uses only poly-logarithmic space in general metrics.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
We give a (1 + ε)-approximate algorithm for estimating the Max-Cut value in sliding-window streams using only poly-logarithmic space in general metric spaces with distance oracles. This is the first such algorithm even for Euclidean spaces. The algorithm builds on the smooth histogram framework after establishing a smoothness bound for metric Max-Cut, and uses a new metric reservoir sampling technique for the insertion-only case. In the dynamic streaming model, a poly(n)-space lower bound is shown for general metrics.
What carries the argument
The smoothness bound for the Max-Cut objective on general metrics, which enables the smooth-histogram framework to track the value over sliding windows with low space.
If this is right
- The sliding-window algorithm achieves (1+ε) approximation with polylog space.
- It is the first sliding-window result for Max-Cut in Euclidean spaces as well.
- It matches the known insertion-only space bound for Euclidean spaces.
- In dynamic streams, poly(n) space is required for general metrics unlike the Euclidean case.
Where Pith is reading between the lines
- Similar smoothness arguments could apply to other graph problems on metric spaces in streaming models.
- The separation between sliding-window and dynamic models highlights the importance of update type in streaming complexity.
- The reservoir sampling technique may generalize to other distance-based problems in streams.
Load-bearing premise
The Max-Cut value in general metric spaces changes smoothly enough when old data points expire in a sliding window to fit the smooth-histogram technique.
What would settle it
A metric space and stream where the Max-Cut value cannot be maintained to (1+ε) accuracy with polylog space after accounting for window slides.
read the original abstract
Max-Cut is a fundamental combinatorial optimization problem that has been studied in various computational settings. We initiate the study of its streaming complexity in \emph{general metric spaces} with access to distance oracles. We give a $(1 + \epsilon)$-approximate algorithm for estimating the Max-Cut value in \emph{sliding-window} streams using only poly-logarithmic space. This is the first sliding-window algorithm for Max-Cut even in Euclidean spaces, and it matches a known insertion-only space bound in the special case of Euclidean spaces [Chen, Jiang, Krauthgamer, STOC'23]. In sharp contrast, we give a $\poly(n)$-space lower bound in the \emph{dynamic} streaming setting. This yields a separation from the Euclidean case, where the polylogarithmic-space $(1+\epsilon)$-approximation extends to dynamic streams. On the technical side, our sliding-window algorithm builds on the smooth histogram framework of [Braverman and Ostrovsky, SICOMP'10]. To make this framework applicable, we establish the first smoothness bound for metric Max-Cut. Moreover, we develop a streaming algorithm for metric Max-Cut in insertion-only streams, whose key ingredient is a new metric reservoir sampling technique.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper initiates the study of Max-Cut in general metric spaces under streaming access to distance oracles. It presents a (1+ε)-approximation algorithm for estimating the Max-Cut value in sliding-window streams that uses only polylogarithmic space; this is claimed to be the first sliding-window result for Max-Cut even in Euclidean spaces and matches the known insertion-only bound of Chen et al. (STOC'23) in the Euclidean case. The algorithm relies on establishing a smoothness bound for metric Max-Cut to apply the Braverman-Ostrovsky smooth-histogram framework, together with a new metric reservoir sampling primitive for insertion-only streams. In contrast, the paper proves a polynomial-space lower bound for the dynamic streaming model, yielding a separation from the Euclidean setting where polylogarithmic space suffices.
Significance. If the smoothness bound and reservoir-sampling analysis hold with parameters depending only on ε, the result is significant: it extends the smooth-histogram technique to a new combinatorial objective in general metrics and provides the first sliding-window algorithm for Max-Cut. The dynamic lower bound and the resulting separation from Euclidean metrics are also of interest. The work supplies machine-checkable-style technical ingredients (explicit smoothness proof and reservoir technique) that could be reusable.
major comments (3)
- [smoothness section (around the first smoothness bound)] The central claim that metric Max-Cut is (α,β)-smooth with α,β depending only on ε (not on n or the underlying metric) is load-bearing for the polylog-space sliding-window result via the Braverman-Ostrovsky framework. The manuscript must make explicit in the smoothness section that the derived β is independent of n; otherwise the histogram maintenance cost inflates beyond polylog.
- [reservoir sampling section] The reservoir-sampling analysis for insertion-only metric Max-Cut must be verified to compose correctly with the sliding-window deletions implicit in the smooth-histogram construction; any dependence on the window size or metric diameter would invalidate the claimed space bound.
- [dynamic lower bound section] The dynamic lower bound (poly(n) space) is stated to separate general metrics from Euclidean; the reduction or hard instance should be checked to confirm it does not inadvertently apply to Euclidean metrics, which would contradict the known polylog dynamic result.
minor comments (2)
- [preliminaries] Notation for the distance oracle and the precise definition of the sliding-window model should be introduced earlier and used consistently.
- [introduction] The abstract claims this is the 'first smoothness bound' for metric Max-Cut; a brief comparison paragraph with prior smoothness results for other objectives would help readers.
Simulated Author's Rebuttal
We thank the referee for their careful reading of the manuscript and for the constructive comments. We address each of the major comments below. Where appropriate, we will incorporate clarifications into the revised version of the paper.
read point-by-point responses
-
Referee: [smoothness section (around the first smoothness bound)] The central claim that metric Max-Cut is (α,β)-smooth with α,β depending only on ε (not on n or the underlying metric) is load-bearing for the polylog-space sliding-window result via the Braverman-Ostrovsky framework. The manuscript must make explicit in the smoothness section that the derived β is independent of n; otherwise the histogram maintenance cost inflates beyond polylog.
Authors: We agree that explicit independence from n is essential for the polylogarithmic space claim. In the smoothness section, the proof establishes that both α and β are functions of ε alone (with β = O(1/ε)), with no dependence on n or the specific metric appearing in the derivation. We will revise the section to state this independence explicitly at the beginning of the smoothness argument and to flag the steps where the bound is shown to be metric- and n-independent. This will ensure the Braverman-Ostrovsky histogram cost remains polylogarithmic as claimed. revision: yes
-
Referee: [reservoir sampling section] The reservoir-sampling analysis for insertion-only metric Max-Cut must be verified to compose correctly with the sliding-window deletions implicit in the smooth-histogram construction; any dependence on the window size or metric diameter would invalidate the claimed space bound.
Authors: We appreciate the request for explicit verification of the composition. The reservoir sampler is invoked only on the active buckets maintained by the smooth-histogram framework; the framework itself handles the implicit deletions arising from the sliding window by discarding obsolete buckets. The sampling probabilities and space bounds depend solely on ε and the length of the current bucket, with no dependence on the global window size or metric diameter. We will add a short clarifying paragraph (or subsection) in the reservoir-sampling section that spells out this composition and confirms the space bound remains polylogarithmic. revision: yes
-
Referee: [dynamic lower bound section] The dynamic lower bound (poly(n) space) is stated to separate general metrics from Euclidean; the reduction or hard instance should be checked to confirm it does not inadvertently apply to Euclidean metrics, which would contradict the known polylog dynamic result.
Authors: We have re-examined the hard instance and reduction in the dynamic lower-bound section. The construction relies on a general metric (specifically, a graph metric on n points with distances 0 or 1 that cannot be isometrically embedded into Euclidean space while preserving the cut structure) whose properties are incompatible with the dimensionality-reduction techniques used in the Euclidean dynamic-streaming algorithms. Consequently, the lower bound does not carry over to Euclidean metrics. We will add a brief remark in the section that explicitly notes this distinction and why the instance is non-Euclidean. revision: partial
Circularity Check
Minor self-citation on Euclidean special case; new smoothness and reservoir proofs independent
full rationale
The derivation relies on the external Braverman-Ostrovsky smooth-histogram framework and introduces a new smoothness bound for metric Max-Cut plus a metric reservoir sampling technique for the insertion-only case. These appear as independent technical contributions. The cited Euclidean insertion-only bound [Chen, Jiang, Krauthgamer, STOC'23] shares an author but is invoked only to match a known special-case space bound, not as load-bearing justification for the general-metric sliding-window result. No self-definitional equations, fitted inputs renamed as predictions, or ansatz smuggling via self-citation are present in the provided claims.
Axiom & Free-Parameter Ledger
axioms (2)
- domain assumption Distances satisfy the triangle inequality and symmetry (standard metric axioms)
- standard math Streaming model allows one-pass processing with limited memory and sliding-window semantics
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.