Image de couverture de livre

Characterizing Streaming Decidability of CSPs via Non-Redundancy

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Sharma, Amatya, Velusamy, Santhoshini
Format:	Preprint
Publié:	2026
Sujets:	Data Structures and Algorithms Computational Complexity
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Non-Redundancy of Low-Arity Symmetric Boolean CSPs
par: Sharma, Amatya, et autres
Publié: (2026)

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
par: Singer, Noah G., et autres
Publié: (2026)

Linear Space Streaming Lower Bounds for Approximating CSPs
par: Chou, Chi-Ning, et autres
Publié: (2021)

Sketching approximations and LP approximations for finite CSPs are related
par: Singer, Noah G., et autres
Publié: (2025)

Streaming approximation resistance of every ordering CSP
par: Singer, Noah G., et autres
Publié: (2021)

Near-Optimal Space Lower Bounds for Streaming CSPs
par: Fei, Yumou, et autres
Publié: (2026)

A Dichotomy Theorem for Multi-Pass Streaming CSPs
par: Fei, Yumou, et autres
Publié: (2025)

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

Search-space Reduction for Boolean MinCSPs via Essential Constraints
par: Jansen, Bart M. P., et autres
Publié: (2026)

Unbounded-width CSPs are Untestable in a Sublinear Number of Queries
par: Fei, Yumou
Publié: (2025)

Nine lower bound conjectures on streaming approximation algorithms for CSPs
par: Singer, Noah G.
Publié: (2025)

Going Beyond Twin-width? CSPs with Unbounded Domain and Few Variables
par: Jonsson, Peter, et autres
Publié: (2025)

Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
par: Kim, Eun Jung, et autres
Publié: (2022)

Optimally detecting uniformly-distributed $\ell_2$ heavy hitters in data streams
par: Velusamy, Santhoshini, et autres
Publié: (2025)

Deciding if a DAG is Interesting is Hard
par: De Carufel, Jean-Lou, et autres
Publié: (2025)

Streaming Algorithms via Local Algorithms for Maximum Directed Cut
par: Saxena, Raghuvansh R., et autres
Publié: (2024)

A Decomposition Approach to the Weighted $k$-server Problem
par: Ayyadevara, Nikhil, et autres
Publié: (2024)

New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs
par: Brakensiek, Joshua, et autres
Publié: (2026)

Self-referential instances of the dominating set problem are irreducible
par: Zhou, Guangyan
Publié: (2026)

Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams
par: Jiang, Cheng, et autres
Publié: (2026)

Streaming Zero-Knowledge Proofs
par: Cormode, Graham, et autres
Publié: (2023)

Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT
par: Anand, Aditya, et autres
Publié: (2025)

A Dividing Line for Structural Kernelization of Component Order Connectivity via Distance to Bounded Pathwidth
par: Greilhuber, Jakob, et autres
Publié: (2026)

Streaming Complexity Separations for Dense and Sparse Graphs
par: Liu, Yang P., et autres
Publié: (2026)

Semi-Streaming Algorithms for Graph Property Certification
par: Das, Avinandan, et autres
Publié: (2025)

Deterministic Independent Sets in the Semi-Streaming Model
par: Ye, Daniel
Publié: (2025)

Coloring Graphs with Few Colors in the Streaming Model
par: Assadi, Sepehr, et autres
Publié: (2025)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
par: Wang, Yichuan
Publié: (2024)

Multi-Pass Streaming Lower Bounds for Uniformity Testing
par: Li, Qian, et autres
Publié: (2025)

Space Complexity Dichotomies for Subgraph Finding Problems in the Streaming Model
par: Shih, Yu-Sheng, et autres
Publié: (2026)

Better Bounds for Semi-Streaming Single-Source Shortest Paths
par: Assadi, Sepehr, et autres
Publié: (2025)

Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
par: Assadi, Sepehr, et autres
Publié: (2024)

Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy
par: Assadi, Sepehr, et autres
Publié: (2024)

A New Information Complexity Measure for Multi-pass Streaming with Applications
par: Braverman, Mark, et autres
Publié: (2024)

Oblivious Algorithms for Maximum Directed Cut: New Upper and Lower Bounds
par: Hwang, Samuel, et autres
Publié: (2024)

Covering a Polyomino-Shaped Stain with Non-Overlapping Identical Stickers
par: Oka, Keigo, et autres
Publié: (2026)

TwinArray Sort: An Ultrarapid Conditional Non-Comparison Based Sorting Algorithm
par: Amini, Amin
Publié: (2024)

Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
par: Esmer, Barış Can, et autres
Publié: (2022)

Non-Boolean OMv: One More Reason to Believe Lower Bounds for Dynamic Problems
par: Hu, Bingbing, et autres
Publié: (2024)

Subset Balancing and Generalized Subset Sum via Lattices
par: Gao, Yiming, et autres
Publié: (2026)