Nine Lower Bound Conjectures on Streaming Approximation Algorithms for CSPs

Basic Information

• Paper ID: 2510.10714
• Title: Nine lower bound conjectures on streaming approximation algorithms for CSPs
• Author: Noah G. Singer (Carnegie Mellon University)
• Classification: cs.CC (Computational Complexity), cs.DS (Data Structures and Algorithms)
• Publication Date: October 14, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2510.10714

Abstract

This paper surveys recent progress in understanding the approximability of constraint satisfaction problems (CSPs) in the low-space streaming model. Motivated by these advances, the author systematically compiles nine lower bound conjectures for streaming algorithms for CSPs, some of which are formally presented for the first time.

Research Background and Motivation

Core Problem

This research focuses on the approximation algorithm complexity of constraint satisfaction problems under the streaming computation model. Specifically, it addresses the question: what is the optimal approximation ratio achievable by streaming algorithms under finite storage space constraints?

Significance Analysis

1. Theoretical Significance: Lower bound research on streaming algorithms provides information-theoretic compression limits, revealing fundamental constraints in maintaining sufficient information to recover optimal values of CSP instances
2. Practical Applications: In big data processing, streaming algorithms are essential tools for handling large-scale data that cannot be completely stored in memory
3. Unconditional Lower Bounds: Unlike polynomial-time complexity, streaming algorithms can prove unconditional lower bounds through communication complexity techniques

Existing Limitations

1. Significant complexity gaps between single-pass and multi-pass algorithms
2. Differential handling capabilities between adversarial and random input orderings
3. Unclear algorithmic capability boundaries at different space complexity thresholds (e.g., √n vs n)

Core Contributions

1. Systematic Organization: First systematic collection and organization of nine important lower bound conjectures in the field of streaming CSP approximation algorithms
2. Novel Conjectures: Several conjectures are formally presented for the first time in this paper
3. Unified Theoretical Framework: Provides a unified theoretical framework for understanding the complexity of different CSP problems under the streaming model
4. Research Direction Guidance: Provides clear objectives and challenges for future research in this field

Methodology Details

CSP Problem Definition

For Boolean CSPs, the following definitions apply:

• Constraints: C = (j₁,...,jₖ; π), where jᵢ ∈ n are variable indices and π ∈ Π is a predicate function
• Assignment Value: valΦ(x) := Prx satisfies C, where C is uniformly sampled from Φ
• Objective: Approximate max-val(Φ) := max_{x∈{0,1}ⁿ} valΦ(x)

Streaming Algorithm Model

Algorithms have the following characteristics:

• Input Access: Sequentially receive constraints C₁,...,Cₘ
• Space Limitation: Can only store s bits of memory at any given time
• Output Requirement: Output an α-approximation of max-val(Φ)

Key Concepts

• Trivial Approximation Ratio: αₜᵣᵢᵥ(Π) = best lower bound independent of specific instances
• Sketch Algorithms: Special class of streaming algorithms satisfying combinatorial properties

Nine Core Conjectures

Single-Pass Linear Space Lower Bounds (Conjectures 1-2)

Conjecture 1: For any ε > 0, every single-pass random-order streaming algorithm achieving a (½ + ε)-approximation for Max-Cut requires Ω(n) space.

Conjecture 2: For any ε > 0, every single-pass adversarial-order streaming algorithm achieving a (½ + ε)-approximation for Max-Cut requires Ω(n log n) space.

Multi-Pass Streaming Lower Bounds (Conjectures 3-5)

Conjecture 3: For any ε > 0, every two-pass adversarial-order streaming algorithm achieving a (½ + ε)-approximation for Max-Cut requires Ω(n) space.

Conjecture 4: For any ε > 0, every k-pass, s-space streaming algorithm achieving a (½ + ε)-approximation for Max-Cut satisfies ks = Ω(√n).

Conjecture 5: For any C > 0, there exists ε > 0 such that every streaming algorithm achieving a (1-ε)-approximation for Max-Cut requires either Ω(nᶜ) passes or Ω(n) space.

o(√n) Space Lower Bounds (Conjectures 6-7)

Conjecture 6: For any ε > 0, every single-pass streaming algorithm achieving a (2/9 + ε)-approximation for Max-3And requires Ω(√n) space.

Conjecture 7: For any k ≥ 5 and ε > 0, every single-pass streaming algorithm achieving a (½ + ε)-approximation for Max-kMonarchy requires Ω(√n) space.

Lower Bounds Beyond √n Space (Conjectures 8-9)

Conjecture 8: Every predicate family that cannot be non-trivially approximated by o(√n)-space sketch algorithms also cannot be non-trivially approximated by o(n)-space streaming algorithms.

Conjecture 9: There exist constants ε, δ > 0 such that every single-pass sketch algorithm achieving a (½ - ε)-approximation for Max-DiCut requires Ω(n^{½+δ}) space.

Theoretical Foundations and Technical Framework

Lower Bound Proof Techniques

All known streaming CSP lower bounds employ the following framework:

1. Define two distributions D_Yes and D_No
2. Prove significant gaps in Max-CSP values of corresponding instances
3. Prove these distributions are indistinguishable in the streaming model through reductions from one-way communication problems

Key Technical Insights

Differences between Max-Cut and Max-DiCut:

• Max-Cut requires global reasoning (finding odd-length cycles)
• Max-DiCut allows local reasoning (checking vertex neighborhoods)

Significance of Space Thresholds:

• √n: Critical point for random walk techniques
• n: Linear space, approaching information-theoretic lower bounds

Related Work Overview

Historical Development

• Origins: Open problem from the 2011 Bertinoro workshop
• Single-Pass Lower Bounds: Series of works by Kapralov et al. KK15; KKS15; KKSV17; KK19
• Multi-Pass Breakthrough: Innovative results by Fei, Minzer, Wang FMW25b
• Dichotomy Theorem: Complete characterization of sketch algorithms by Chou et al. CGSV24

Technical Development Timeline

1. Early Work: Foundational lower bounds based on communication complexity
2. Refined Analysis: Distinguishing adversarial vs. random orderings
3. Multi-Pass Algorithms: Analysis of component growth protocols
4. Unified Theory: Dichotomy theorem for sketch algorithms

In-Depth Analysis and Evaluation

Theoretical Contributions

1. Systematicity: First systematic compilation of core open problems in this field
2. Forward-Looking: Identifies multiple critical research directions
3. Unification: Understanding complexity of different CSPs under a unified framework

Technical Depth

1. Precise Characterization: Fine-grained analysis across different parameter regimes
2. Technical Innovation: Theoretical analysis of component growth algorithms
3. Cross-Domain Connections: Linking communication complexity and streaming algorithms

Practical Impact

1. Research Guidance: Provides clear objectives for theoretical computer science research
2. Algorithm Design: Guides space-accuracy tradeoff optimization in practical streaming algorithms
3. Complexity Theory: Advances understanding of computational complexity boundaries

Technical Challenges and Future Directions

Major Technical Obstacles

1. √n vs n Gap: Multiple conjectures involve this critical threshold
2. Multi-Pass Algorithm Analysis: Technical difficulties beyond cubic-root space
3. Streaming vs Sketch: Characterizing capability differences between the two models

Potential Breakthrough Directions

1. Novel Lower Bound Techniques: Transcending existing communication complexity methods
2. Algorithm Design: Optimized algorithms for specific space regimes
3. Unified Theory: More general theory of streaming CSP complexity

Conclusions and Outlook

Main Conclusions

Through nine carefully designed conjectures, this paper systematically delineates frontier problems in streaming CSP approximation algorithm complexity. These conjectures not only summarize current theoretical understanding but also provide direction for future research.

Academic Value

1. Theoretical Completeness: Fills important gaps in streaming algorithm theory
2. Problem-Oriented: Provides researchers with concrete targets to tackle
3. Cross-Domain Impact: Connects multiple branches of theoretical computer science

Practical Significance

Although primarily focused on theoretical lower bounds, these results have important implications for practical large-scale data processing algorithm design, particularly in optimizing space-accuracy tradeoffs.

Overall Assessment: This is a high-quality theoretical survey paper that not only systematically reviews the current state of streaming CSP algorithms but, more importantly, provides a clear roadmap for future development in this field through nine well-considered conjectures. The paper demonstrates the author's deep understanding of the field and forward-thinking perspective, with significant value for advancing related theoretical research.