Buchumschlag

Linear Space Streaming Lower Bounds for Approximating CSPs

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Chou, Chi-Ning, Golovnev, Alexander, Sudan, Madhu, Velingker, Ameya, Velusamy, Santhoshini
Format:	Preprint
Veröffentlicht:	2021
Schlagworte:	Computational Complexity Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
von: Singer, Noah G., et al.
Veröffentlicht: (2026)

Characterizing Streaming Decidability of CSPs via Non-Redundancy
von: Sharma, Amatya, et al.
Veröffentlicht: (2026)

Streaming approximation resistance of every ordering CSP
von: Singer, Noah G., et al.
Veröffentlicht: (2021)

Non-Redundancy of Low-Arity Symmetric Boolean CSPs
von: Sharma, Amatya, et al.
Veröffentlicht: (2026)

Sketching approximations and LP approximations for finite CSPs are related
von: Singer, Noah G., et al.
Veröffentlicht: (2025)

Sketching approximability of all finite CSPs
von: Chou, Chi-Ning, et al.
Veröffentlicht: (2021)

Near-Optimal Space Lower Bounds for Streaming CSPs
von: Fei, Yumou, et al.
Veröffentlicht: (2026)

Streaming Algorithms via Local Algorithms for Maximum Directed Cut
von: Saxena, Raghuvansh R., et al.
Veröffentlicht: (2024)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
von: Wang, Yichuan
Veröffentlicht: (2024)

A Dichotomy Theorem for Multi-Pass Streaming CSPs
von: Fei, Yumou, et al.
Veröffentlicht: (2025)

Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
von: Grossman, Ofer, et al.
Veröffentlicht: (2023)

Multi-Pass Streaming Lower Bounds for Uniformity Testing
von: Li, Qian, et al.
Veröffentlicht: (2025)

Multi-Pass Streaming Lower Bounds for Approximating Max-Cut
von: Fei, Yumou, et al.
Veröffentlicht: (2025)

A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy
von: Assadi, Sepehr, et al.
Veröffentlicht: (2024)

Near-optimal streaming approximation for Max-DICUT in sublinear space using two passes
von: Velusamy, Santhoshini
Veröffentlicht: (2025)

Oblivious Algorithms for Maximum Directed Cut: New Upper and Lower Bounds
von: Hwang, Samuel, et al.
Veröffentlicht: (2024)

Online Orthogonal Vectors Revisited
von: Gajulapalli, Karthik, et al.
Veröffentlicht: (2026)

Lower Bounds for Linear Operators
von: Ko, Young Kun
Veröffentlicht: (2025)

Unbounded-width CSPs are Untestable in a Sublinear Number of Queries
von: Fei, Yumou
Veröffentlicht: (2025)

Nine lower bound conjectures on streaming approximation algorithms for CSPs
von: Singer, Noah G.
Veröffentlicht: (2025)

Going Beyond Twin-width? CSPs with Unbounded Domain and Few Variables
von: Jonsson, Peter, et al.
Veröffentlicht: (2025)

Search-space Reduction for Boolean MinCSPs via Essential Constraints
von: Jansen, Bart M. P., et al.
Veröffentlicht: (2026)

Lower Bounds for Convexity Testing
von: Chen, Xi, et al.
Veröffentlicht: (2024)

Improved Space Bounds for Subset Sum
von: Belova, Tatiana, et al.
Veröffentlicht: (2024)

Sensitivity Lower Bounds for Approximaiton Algorithms
von: Fleming, Noah, et al.
Veröffentlicht: (2024)

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

Treedepth Inapproximability and Exponential ETH Lower Bound
von: Bonnet, Édouard, et al.
Veröffentlicht: (2025)

Approximating Klee's Measure Problem and a Lower Bound for Union Volume Estimation
von: Bringmann, Karl, et al.
Veröffentlicht: (2024)

Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams
von: Jiang, Cheng, et al.
Veröffentlicht: (2026)

Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
von: Assadi, Sepehr, et al.
Veröffentlicht: (2024)

Better Bounds for Semi-Streaming Single-Source Shortest Paths
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

Unifying the Landscape of Super-Logarithmic Dynamic Cell-Probe Lower Bounds
von: Ko, Young Kun
Veröffentlicht: (2025)

Optimally detecting uniformly-distributed $\ell_2$ heavy hitters in data streams
von: Velusamy, Santhoshini, et al.
Veröffentlicht: (2025)

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

The Structure of In-Place Space-Bounded Computation
von: Cook, James, et al.
Veröffentlicht: (2025)

Automated Lower Bounds for Small Matrix Multiplication Complexity over Finite Fields
von: Wang, Chengu
Veröffentlicht: (2026)

A Tight Double-Exponentially Lower Bound for High-Multiplicity Bin Packing
von: Jansen, Klaus, et al.
Veröffentlicht: (2025)

Space Complexity Dichotomies for Subgraph Finding Problems in the Streaming Model
von: Shih, Yu-Sheng, et al.
Veröffentlicht: (2026)

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