Research map / Learning theory and algorithms / Submodular and game algorithms

Learning-Augmented Streaming Algorithms for Approximating Boolean Max-CSPs

NeurIPS 2026 · Learning theory and algorithms › Submodular and game algorithms · approach: Streaming submodular algorithms

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Gives learning-augmented streaming algorithms that, given an ε-accurate label oracle, estimate Boolean Max-2CSP/Max-kCSP optimum to within (1−η) using space independent of n (insertion-only) or polylog n (dynamic).

Problem

Estimating the optimum value of Boolean Max-CSPs in streaming (insertion-only and dynamic) where classical streaming algorithms face strong approximation barriers, using an ε-accurate predictor of an optimal assignment.

Approach

Treat oracle labels as a binary symmetric channel over an optimal assignment and invert the noise via linear decoders (Gaussian elimination) on counts of constraint types among low-degree variables; handle high-degree variables by enumerating their assignments and keeping per-variable sketches (reservoir sampling and CountMin, or l0-sampling in dynamic streams).

Key results

• For Max-2CSPs, a single-pass (1-η)-approximation in insertion-only streams using O(1/(ε^10 δ^5 η^6) log(1/(εδη))) words of space, independent of n.
• In dynamic streams, Max-2CSP (1-η)-approximation with O(log^2 n/(ε^10 δ^5 η^6) log(1/(εδη))) bits, i.e., polylog n space.
• For Max-kAND with k≥3 and unbounded degree, insertion-only space is exp(O(k^3 ε^{-2k} η^{-2} log(16/δ))) words, independent of n.

Surprising findings

• Prediction-following (evaluating the cut induced by predictions) is inherently limited to about 1/4+O(ε) for Max-Dicut, so the noise-inversion approach is needed.

Limitations

• Requires the accuracy parameter ε to be known (or a highly accurate estimate of it).
• For k≥3 the space is exponential in k, 1/ε and 1/η.
• Only estimates the optimum value rather than outputting an assignment.

Experimental setup

Metrics: approximation ratio space complexity (words)

Baselines: Dong-Peng-Vakilian Max-Cut algorithm classical streaming Max-2AND/Max-Dicut lower bounds (Chou et al.)

Builds on: DPV25 learning-augmented streaming Max-Cut CountMin sketch reservoir sampling l0-sampling

Closest papers by meaning

• Streaming k-Submodular Maximization under Noise subject to Size Constraint (ICML 2020 · similarity 0.88)
• Streaming Robust Submodular Maximization: A Partitioned Thresholding Approach (NeurIPS 2017 · similarity 0.87)
• Learning-Augmented Approximation Algorithms for Maximum Cut and Related Problems (NeurIPS 2024 · similarity 0.87)
• Consistent Submodular Maximization (ICML 2024 · similarity 0.86)
• Parsimonious Learning-Augmented Approximations for Dense Instances of $\mathcal{NP}$-hard Problems (ICML 2024 · similarity 0.85)
• Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs (NeurIPS 2024 · similarity 0.84)