Imagen de Portada

Going Beyond Twin-width? CSPs with Unbounded Domain and Few Variables

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Jonsson, Peter, Lagerkvist, Victor, de Vlas, Jorke M., Wahlström, Magnus
Formato:	Preprint
Publicado:	2025
Materias:	Data Structures and Algorithms Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

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

Improved Bounds for Twin-Width Parameter Variants with Algorithmic Applications to Counting Graph Colorings
por: Baril, Ambroise, et al.
Publicado: (2025)

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

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

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

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

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

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

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

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

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

CSPs with Few Alien Constraints
por: Jonsson, Peter, et al.
Publicado: (2024)

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

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

Emit As You Go: Enumerating Edges of a Spanning Tree
por: Casel, Katrin, et al.
Publicado: (2025)

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

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

From Chinese Postman to Salesman and Beyond II: Inapproximability and Parameterized Complexity
por: Frei, Fabian, et al.
Publicado: (2025)

From Chinese Postman to Salesman and Beyond I: Approximating Shortest Tours $δ$-Covering All Points on All Edges
por: Frei, Fabian, et al.
Publicado: (2024)

Inapproximability of Maximum Diameter Clustering for Few Clusters
por: Fleischmann, Henry, et al.
Publicado: (2023)

Resilient functions: Optimized, simplified, and generalized
por: Ivanov, Peter, et al.
Publicado: (2024)

Computing Balanced Solutions for Large International Kidney Exchange Schemes When Cycle Length Is Unbounded
por: Benedek, Márton, et al.
Publicado: (2023)

Gray Codes With Constant Delay and Constant Auxiliary Space
por: Amarilli, Antoine, et al.
Publicado: (2026)

Removable Online Knapsack and Advice
por: Böckenhauer, Hans-Joachim, et al.
Publicado: (2020)

Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width
por: Kluk, Kacper, et al.
Publicado: (2025)

Breadth-First Search Trees with Many or Few Leaves
por: Beisegel, Jesse, et al.
Publicado: (2026)

Representative set statements for delta-matroids and the Mader delta-matroid
por: Wahlström, Magnus
Publicado: (2023)

Most Juntas Saturate the Hardcore Lemma
por: Kumar, Vinayak M.
Publicado: (2025)

Beyond Bits: An Introduction to Computation over the Reals
por: Miltzow, Tillmann
Publicado: (2026)

Finding Diverse Solutions in Combinatorial Problems with a Distributive Lattice Structure
por: de Berg, Mark, et al.
Publicado: (2025)

Parameterized Approximability for Modular Linear Equations
por: Dabrowski, Konrad K., et al.
Publicado: (2025)

Optimal FPT-Approximability for Modular Linear Equations
por: Dabrowski, Konrad K., et al.
Publicado: (2026)

Linear Hashing Is Optimal
por: Jaber, Michael, et al.
Publicado: (2025)

On the Advantage of Adaptivity for Sampling with Cell Probes
por: Byramji, Farzan, et al.
Publicado: (2026)

The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
por: Greilhuber, Jakob, et al.
Publicado: (2025)

The Trichotomy of Regular Property Testing
por: Bathie, Gabriel, et al.
Publicado: (2025)

Downward self-reducibility in the total function polynomial hierarchy
por: Gajulapalli, Karthik, et al.
Publicado: (2025)

Tight Additive Sensitivity on LZ-style Compressors and String Attractors
por: Fujie, Yuto, et al.
Publicado: (2025)

Sublinear-Time Approximation for Graph Frequency Vectors in Hyperfinite Graphs
por: Moroie, Gregory
Publicado: (2025)