Cover Image

Near-Optimal Space Lower Bounds for Streaming CSPs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Fei, Yumou, Minzer, Dor, Wang, Shuo
Format:	Preprint
Published:	2026
Subjects:	Computational Complexity Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Dichotomy Theorem for Multi-Pass Streaming CSPs
by: Fei, Yumou, et al.
Published: (2025)

Multi-Pass Streaming Lower Bounds for Approximating Max-Cut
by: Fei, Yumou, et al.
Published: (2025)

Unbounded-width CSPs are Untestable in a Sublinear Number of Queries
by: Fei, Yumou
Published: (2025)

Linear Space Streaming Lower Bounds for Approximating CSPs
by: Chou, Chi-Ning, et al.
Published: (2021)

Near Optimal Alphabet-Soundness Tradeoff PCPs
by: Minzer, Dor, et al.
Published: (2024)

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
by: Singer, Noah G., et al.
Published: (2026)

Testing Properties of Edge Distributions
by: Fei, Yumou
Published: (2026)

Characterizing Streaming Decidability of CSPs via Non-Redundancy
by: Sharma, Amatya, et al.
Published: (2026)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
by: Wang, Yichuan
Published: (2024)

Multi-Pass Streaming Lower Bounds for Uniformity Testing
by: Li, Qian, et al.
Published: (2025)

A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams
by: Khanna, Sanjeev, et al.
Published: (2025)

Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy
by: Assadi, Sepehr, et al.
Published: (2024)

Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
by: Grossman, Ofer, et al.
Published: (2023)

Non-Redundancy of Low-Arity Symmetric Boolean CSPs
by: Sharma, Amatya, et al.
Published: (2026)

Sketching approximations and LP approximations for finite CSPs are related
by: Singer, Noah G., et al.
Published: (2025)

Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Nine lower bound conjectures on streaming approximation algorithms for CSPs
by: Singer, Noah G.
Published: (2025)

Search-space Reduction for Boolean MinCSPs via Essential Constraints
by: Jansen, Bart M. P., et al.
Published: (2026)

Going Beyond Twin-width? CSPs with Unbounded Domain and Few Variables
by: Jonsson, Peter, et al.
Published: (2025)

Lower Bounds for Convexity Testing
by: Chen, Xi, et al.
Published: (2024)

Sensitivity Lower Bounds for Approximaiton Algorithms
by: Fleming, Noah, et al.
Published: (2024)

Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
by: Kim, Eun Jung, et al.
Published: (2022)

Treedepth Inapproximability and Exponential ETH Lower Bound
by: Bonnet, Édouard, et al.
Published: (2025)

Automated Lower Bounds for Small Matrix Multiplication Complexity over Finite Fields
by: Wang, Chengu
Published: (2026)

Near-Optimal Bounds for Parameterized Euclidean k-means
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Better Bounds for Semi-Streaming Single-Source Shortest Paths
by: Assadi, Sepehr, et al.
Published: (2025)

Unifying the Landscape of Super-Logarithmic Dynamic Cell-Probe Lower Bounds
by: Ko, Young Kun
Published: (2025)

Near-Optimal Averaging Samplers and Matrix Samplers
by: Xun, Zhiyang, et al.
Published: (2024)

The Structure of In-Place Space-Bounded Computation
by: Cook, James, et al.
Published: (2025)

Improved Space Bounds for Subset Sum
by: Belova, Tatiana, et al.
Published: (2024)

A New Information Complexity Measure for Multi-pass Streaming with Applications
by: Braverman, Mark, et al.
Published: (2024)

A Tight Double-Exponentially Lower Bound for High-Multiplicity Bin Packing
by: Jansen, Klaus, et al.
Published: (2025)

Near-Optimality for Single-Source Personalized PageRank
by: Jiang, Xinpeng, et al.
Published: (2025)

Space Complexity Dichotomies for Subgraph Finding Problems in the Streaming Model
by: Shih, Yu-Sheng, et al.
Published: (2026)

Non-Boolean OMv: One More Reason to Believe Lower Bounds for Dynamic Problems
by: Hu, Bingbing, et al.
Published: (2024)

Subset Sum in Near-Linear Pseudopolynomial Time and Polynomial Space
by: Sajith, Thejas Radhika
Published: (2025)

Near Optimal Algorithms for Noisy $k$-XOR under Low-Degree Heuristic
by: Mao, Songtao
Published: (2026)

Lower Bounds for Linear Operators
by: Ko, Young Kun
Published: (2025)

Keeping a Secret Requires a Good Memory: Space Lower-Bounds for Private Algorithms
by: Epasto, Alessandro, et al.
Published: (2026)

New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs
by: Brakensiek, Joshua, et al.
Published: (2026)