Image de couverture de livre

A simplified proof of the CSP Dichotomy Conjecture and XY-symmetric operations

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteur principal:	Zhuk, Dmitriy
Format:	Preprint
Publié:	2024
Sujets:	Computational Complexity Logic in Computer Science Rings and Algebras
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

$Π_{2}^{P}$ vs PSpace Dichotomy for the Quantified Constraint Satisfaction Problem
par: Zhuk, Dmitriy
Publié: (2024)

An algebraic proof of the dichotomy for graph orientation problems with forbidden tournaments
par: Feller, Roman, et autres
Publié: (2024)

Unifying the Three Algebraic Approaches to the CSP via Minimal Taylor Algebras
par: Barto, Libor, et autres
Publié: (2021)

Singleton algorithms for the Constraint Satisfaction Problem
par: Zhuk, Dmitriy
Publié: (2025)

Network Satisfaction Problems Solved by k-Consistency
par: Bodirsky, Manuel, et autres
Publié: (2023)

The complete classification for quantified equality constraints
par: Zhuk, Dmitriy, et autres
Publié: (2021)

Symmetric Linear Arc Monadic Datalog and Gadget Reductions
par: Bodirsky, Manuel, et autres
Publié: (2024)

The Network Satisfaction Problem for Relation Algebras with at most 4 Atoms
par: Bodirsky, Manuel, et autres
Publié: (2025)

Toward a Uniform Algorithm and Uniform Reduction for Constraint Problems
par: Barto, Libor, et autres
Publié: (2026)

Graph Homomorphisms and Universal Algebra
par: Bodirsky, Manuel
Publié: (2026)

Modular Counting CSP: Reductions and Algorithms
par: Kazeminia, Amirhossein, et autres
Publié: (2025)

The CSP Dichotomy, the Axiom of Choice, and Cyclic Polymorphisms
par: Kátay, Tamás, et autres
Publié: (2023)

The Richness of CSP Non-redundancy
par: Brakensiek, Joshua, et autres
Publié: (2025)

Local structure of idempotent algebras I
par: Bulatov, Andrei A.
Publié: (2020)

When Darwin met Ianus: dichotomies of expressivity
par: Brunar, Johanna, et autres
Publié: (2025)

Undecidability and incompleteness in quantum information theory and operator algebras
par: Goldbring, Isaac
Publié: (2024)

Lower bounds for set-blocked clauses proofs
par: Yolcu, Emre
Publié: (2024)

Proof complexity of Mal'tsev CSP
par: Gaysin, Azza
Publié: (2025)

Formalizing Mason-Stothers Theorem and its Corollaries in Lean 4
par: Baek, Jineon, et autres
Publié: (2024)

The Equational Theories Project: Advancing Collaborative Mathematical Research at Scale
par: Bolan, Matthew, et autres
Publié: (2025)

Formalizing Gröbner Basis Theory in Lean
par: Guo, Junyu, et autres
Publié: (2026)

A Complexity Dichotomy for Semilinear Target Sets in Automata with One Counter
par: Shakiba, Yousef, et autres
Publié: (2025)

The Ideal Membership Problem and Abelian Groups
par: Bulatov, Andrei A., et autres
Publié: (2022)

On the lattice of multi-sorted relational clones on a two-element set
par: David, Vojtěch, et autres
Publié: (2025)

Functional variant of Polynomial Analogue of Gandy's Fixed Point Theorem
par: Nechesov, Andrey
Publié: (2024)

Feasibly Constructive Proof of Schwartz-Zippel Lemma and the Complexity of Finding Hitting Sets
par: Atserias, Albert, et autres
Publié: (2024)

Proof Complexity of Linear Logics
par: Tabatabai, Amirhossein Akbar, et autres
Publié: (2026)

An order out of nowhere: a new algorithm for infinite-domain CSPs
par: Mottet, Antoine, et autres
Publié: (2023)

The Proof Analysis Problem
par: Arteche, Noel, et autres
Publié: (2025)

Proof complexity of positive branching programs
par: Das, Anupam, et autres
Publié: (2021)

Parallelism and Adaptivity in Student-Teacher Witnessing
par: Ježil, Ondřej, et autres
Publié: (2026)

Effective Versions of Strong Measure Zero
par: Rayman, Matthew
Publié: (2025)

Meta-Mathematics of Computational Complexity Theory
par: Oliveira, Igor C.
Publié: (2025)

On the consistency of stronger lower bounds for NEXP
par: Thapen, Neil
Publié: (2025)

Notes on CSPs and Polymorphisms
par: Brady, Zarathustra
Publié: (2022)

On $NP \cap coNP$ proof complexity generators
par: Krajicek, Jan
Publié: (2025)

Formalizing a classification theorem for low-dimensional solvable Lie algebras in Lean
par: del Barco, Viviana, et autres
Publié: (2025)

New Perspectives on Semiring Applications to Dynamic Programming
par: Baril, Ambroise, et autres
Publié: (2025)

Complex to Rational Fast Matrix Multiplication
par: Moran, Yoav, et autres
Publié: (2026)

A SUBSET-SUM Characterisation of the A-Hierarchy
par: Gutleben, Jan, et autres
Publié: (2024)