Cover Image

Characterizing Streaming Decidability of CSPs via Non-Redundancy

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Sharma, Amatya, Velusamy, Santhoshini
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

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

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

Streaming approximation resistance of every ordering CSP
by: Singer, Noah G., et al.
Published: (2021)

Near-Optimal Space Lower Bounds for Streaming CSPs
by: Fei, Yumou, et al.
Published: (2026)

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

Near-optimal streaming approximation for Max-DICUT in sublinear space using two passes
by: Velusamy, Santhoshini
Published: (2025)

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

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

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

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

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

Optimally detecting uniformly-distributed $\ell_2$ heavy hitters in data streams
by: Velusamy, Santhoshini, et al.
Published: (2025)

Deciding if a DAG is Interesting is Hard
by: De Carufel, Jean-Lou, et al.
Published: (2025)

Streaming Algorithms via Local Algorithms for Maximum Directed Cut
by: Saxena, Raghuvansh R., et al.
Published: (2024)

A Decomposition Approach to the Weighted $k$-server Problem
by: Ayyadevara, Nikhil, et al.
Published: (2024)

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

Self-referential instances of the dominating set problem are irreducible
by: Zhou, Guangyan
Published: (2026)

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

Streaming Zero-Knowledge Proofs
by: Cormode, Graham, et al.
Published: (2023)

Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT
by: Anand, Aditya, et al.
Published: (2025)

A Dividing Line for Structural Kernelization of Component Order Connectivity via Distance to Bounded Pathwidth
by: Greilhuber, Jakob, et al.
Published: (2026)

Streaming Complexity Separations for Dense and Sparse Graphs
by: Liu, Yang P., et al.
Published: (2026)

Semi-Streaming Algorithms for Graph Property Certification
by: Das, Avinandan, et al.
Published: (2025)

Deterministic Independent Sets in the Semi-Streaming Model
by: Ye, Daniel
Published: (2025)

Coloring Graphs with Few Colors in the Streaming Model
by: Assadi, Sepehr, et al.
Published: (2025)

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)

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

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

Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
by: Assadi, Sepehr, et al.
Published: (2024)

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

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

Oblivious Algorithms for Maximum Directed Cut: New Upper and Lower Bounds
by: Hwang, Samuel, et al.
Published: (2024)

Covering a Polyomino-Shaped Stain with Non-Overlapping Identical Stickers
by: Oka, Keigo, et al.
Published: (2026)

TwinArray Sort: An Ultrarapid Conditional Non-Comparison Based Sorting Algorithm
by: Amini, Amin
Published: (2024)

Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
by: Esmer, Barış Can, et al.
Published: (2022)

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

Subset Balancing and Generalized Subset Sum via Lattices
by: Gao, Yiming, et al.
Published: (2026)