Buchumschlag

An algebraic proof of the dichotomy for graph orientation problems with forbidden tournaments

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Feller, Roman, Pinsker, Michael
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Combinatorics Computational Complexity Logic in Computer Science Rings and Algebras
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

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

A simplified proof of the CSP Dichotomy Conjecture and XY-symmetric operations
von: Zhuk, Dmitriy
Veröffentlicht: (2024)

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

Symmetric Linear Arc Monadic Datalog and Gadget Reductions
von: Bodirsky, Manuel, et al.
Veröffentlicht: (2024)

The Network Satisfaction Problem for Relation Algebras with at most 4 Atoms
von: Bodirsky, Manuel, et al.
Veröffentlicht: (2025)

An order out of nowhere: a new algorithm for infinite-domain CSPs
von: Mottet, Antoine, et al.
Veröffentlicht: (2023)

Graph Homomorphisms and Universal Algebra
von: Bodirsky, Manuel
Veröffentlicht: (2026)

Local structure of idempotent algebras I
von: Bulatov, Andrei A.
Veröffentlicht: (2020)

Separating complexity classes of LCL problems on grids
von: Berlow, Katalin, et al.
Veröffentlicht: (2025)

Permutation clones that preserve relations
von: Boykett, Tim
Veröffentlicht: (2024)

Decidability of Interpretability
von: Feller, Roman, et al.
Veröffentlicht: (2026)

Undecidability and incompleteness in quantum information theory and operator algebras
von: Goldbring, Isaac
Veröffentlicht: (2024)

An Algorithmic Meta Theorem for Homomorphism Indistinguishability
von: Seppelt, Tim
Veröffentlicht: (2024)

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

Logical Equivalences, Homomorphism Indistinguishability, and Forbidden Minors
von: Seppelt, Tim
Veröffentlicht: (2023)

The Richness of CSP Non-redundancy
von: Brakensiek, Joshua, et al.
Veröffentlicht: (2025)

A Classification of Long-Refinement Graphs for Colour Refinement
von: Kiefer, Sandra, et al.
Veröffentlicht: (2025)

Undecidability of Polynomial Inequalities in Subset Densities and Additive Energies
von: Li, Yaqiao
Veröffentlicht: (2025)

Lower bounds for set-blocked clauses proofs
von: Yolcu, Emre
Veröffentlicht: (2024)

On the structure of approximate rings
von: Krupiński, Krzysztof, et al.
Veröffentlicht: (2026)

Formalizing Mason-Stothers Theorem and its Corollaries in Lean 4
von: Baek, Jineon, et al.
Veröffentlicht: (2024)

The Equational Theories Project: Advancing Collaborative Mathematical Research at Scale
von: Bolan, Matthew, et al.
Veröffentlicht: (2025)

Formalizing a classification theorem for low-dimensional solvable Lie algebras in Lean
von: del Barco, Viviana, et al.
Veröffentlicht: (2025)

Formalizing Gröbner Basis Theory in Lean
von: Guo, Junyu, et al.
Veröffentlicht: (2026)

A topological proof of the Hell-Nešetřil dichotomy
von: Meyer, Sebastian, et al.
Veröffentlicht: (2024)

Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability
von: Roberson, David E., et al.
Veröffentlicht: (2023)

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

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

Relational correspondences for L-fuzzy rough approximations defined on De Morgan Heyting algebras
von: Järvinen, Jouni, et al.
Veröffentlicht: (2023)

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

Isotropy and completeness indices of multilinear maps
von: Chen, Qiyuan, et al.
Veröffentlicht: (2025)

A base change framework for tensor functions
von: Chen, Qiyuan
Veröffentlicht: (2026)

Learning Read-Once Determinants and the Principal Minor Assignment Problem
von: Aravind, Abhiram, et al.
Veröffentlicht: (2026)

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

The Ideal Membership Problem and Abelian Groups
von: Bulatov, Andrei A., et al.
Veröffentlicht: (2022)

Finding hardness reductions automatically using SAT solvers
von: Bergold, Helena, et al.
Veröffentlicht: (2024)

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

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)

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