Buchumschlag

An order out of nowhere: a new algorithm for infinite-domain CSPs

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Mottet, Antoine, Nagy, Tomáš, Pinsker, Michael
Format:	Preprint
Veröffentlicht:	2023
Schlagworte:	Logic in Computer Science Computational Complexity Logic
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Collapsing the bounded width hierarchy for infinite-domain CSPs: when symmetries are enough
von: Mottet, Antoine, et al.
Veröffentlicht: (2021)

Algebraic and algorithmic synergies between promise and infinite-domain CSPs
von: Mottet, Antoine
Veröffentlicht: (2025)

Strict width for Constraint Satisfaction Problems over homogeneous strucures of finite duality
von: Nagy, Tomáš, et al.
Veröffentlicht: (2024)

The sorrows of a smooth digraph: the first hardness criterion for infinite directed graph-colouring problems
von: Brunar, Johanna, et al.
Veröffentlicht: (2025)

Complexity Classification Transfer for CSPs via Algebraic Products
von: Bodirsky, Manuel, et al.
Veröffentlicht: (2022)

An algebraic proof of the dichotomy for graph orientation problems with forbidden tournaments
von: Feller, Roman, et al.
Veröffentlicht: (2024)

Satisfiability of commutative vs. non-commutative CSPs
von: Bulatov, Andrei A., et al.
Veröffentlicht: (2024)

Restricted CSPs and F-free Digraph Algorithmics
von: Guzmán-Pro, Santiago, et al.
Veröffentlicht: (2025)

Functional variant of Polynomial Analogue of Gandy's Fixed Point Theorem
von: Nechesov, Andrey
Veröffentlicht: (2024)

Proof Complexity of Linear Logics
von: Tabatabai, Amirhossein Akbar, et al.
Veröffentlicht: (2026)

The Proof Analysis Problem
von: Arteche, Noel, et al.
Veröffentlicht: (2025)

Proof complexity of positive branching programs
von: Das, Anupam, et al.
Veröffentlicht: (2021)

Parallelism and Adaptivity in Student-Teacher Witnessing
von: Ježil, Ondřej, et al.
Veröffentlicht: (2026)

Effective Versions of Strong Measure Zero
von: Rayman, Matthew
Veröffentlicht: (2025)

The complete classification for quantified equality constraints
von: Zhuk, Dmitriy, et al.
Veröffentlicht: (2021)

Meta-Mathematics of Computational Complexity Theory
von: Oliveira, Igor C.
Veröffentlicht: (2025)

On the consistency of stronger lower bounds for NEXP
von: Thapen, Neil
Veröffentlicht: (2025)

Feasibly Constructive Proof of Schwartz-Zippel Lemma and the Complexity of Finding Hitting Sets
von: Atserias, Albert, et al.
Veröffentlicht: (2024)

$Π_{2}^{P}$ vs PSpace Dichotomy for the Quantified Constraint Satisfaction Problem
von: Zhuk, Dmitriy
Veröffentlicht: (2024)

New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs
von: Brakensiek, Joshua, et al.
Veröffentlicht: (2026)

Singleton algorithms for the Constraint Satisfaction Problem
von: Zhuk, Dmitriy
Veröffentlicht: (2025)

Better Extension Variables in DQBF via Independence
von: Chew, Leroy, et al.
Veröffentlicht: (2025)

Hardness of monadic second-order formulae over succinct graphs
von: Gamard, Guilhem, et al.
Veröffentlicht: (2023)

Capturing the polynomial hierarchy by second-order revised Krom logic
von: Wang, Kexu, et al.
Veröffentlicht: (2022)

Simulation of Turing machines with analytic discrete ODEs: FPTIME and FPSPACE over the reals characterised with discrete ordinary differential equations
von: Blanc, Manon, et al.
Veröffentlicht: (2023)

Network Satisfaction Problems Solved by k-Consistency
von: Bodirsky, Manuel, et al.
Veröffentlicht: (2023)

Measuring robustness of dynamical systems. Relating time and space to length and precision
von: Blanc, Manon, et al.
Veröffentlicht: (2023)

On Probabilistic and Causal Reasoning with Summation Operators
von: Ibeling, Duligur, et al.
Veröffentlicht: (2024)

Measuring Decidability as Related to Busy Beaver Numbers
von: Tandi, Gurpreet, et al.
Veröffentlicht: (2026)

Quantum Polymorphisms and the Complexity of Quantum Constraint Satisfaction
von: Ciardo, Lorenzo, et al.
Veröffentlicht: (2025)

Three Fundamental Questions in Modern Infinite-Domain Constraint Satisfaction
von: Pinsker, Michael, et al.
Veröffentlicht: (2025)

Local consistency as a reduction between constraint satisfaction problems
von: Dalmau, Victor, et al.
Veröffentlicht: (2023)

When Darwin met Ianus: dichotomies of expressivity
von: Brunar, Johanna, et al.
Veröffentlicht: (2025)

Complexity classification of counting graph homomorphisms modulo a prime number
von: Bulatov, Andrei A., et al.
Veröffentlicht: (2021)

New Bounds for the Ideal Proof System in Positive Characteristic
von: Behera, Amik Raj, et al.
Veröffentlicht: (2025)

Kleene algebra with commutativity conditions is undecidable
von: de Amorim, Arthur Azevedo, et al.
Veröffentlicht: (2024)

A characterization of efficiently compilable constraint languages
von: Berkholz, Christoph, et al.
Veröffentlicht: (2023)

Multi-Structural Games and Beyond
von: Carmosino, Marco, et al.
Veröffentlicht: (2023)

On guarded extensions of MMSNP
von: Barsukov, Alexey, et al.
Veröffentlicht: (2023)

Logics with probabilistic team semantics and the Boolean negation
von: Hannula, Miika, et al.
Veröffentlicht: (2023)