DOI10.1145/3402029zbMath1491.68128arXiv1704.01914OpenAlexW3081785465WikidataQ123197481 ScholiaQ123197481MaRDI QIDQ5133982
Dmitriy N. Zhuk
Publication date: 11 November 2020
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1704.01914
On a stronger reconstruction notion for monoids and clones ⋮
On regularity of Max-CSPs and Min-CSPs ⋮
CLAP: A New Algorithm for Promise CSPs ⋮
Topology and Adjunction in Promise Constraint Satisfaction ⋮
Universal Horn Sentences and the Joint Embedding Property ⋮
Homogeneous structures: model theory meets universal algebra. Abstracts from the workshop held January 3--9, 2021 (online meeting) ⋮
Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity ⋮
The lattice and semigroup structure of multipermutations ⋮
When Symmetries Are Not Enough: A Hierarchy of Hard Constraint Satisfaction Problems ⋮
Correspondence homomorphisms to reflexive graphs ⋮
Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy ⋮
Complexity of correspondence \(H\)-colourings ⋮
The 2-colouring problem for $(m,n)$-mixed graphs with switching is polynomial ⋮
Unnamed Item ⋮
The smallest hard trees ⋮
The algebraic structure of the densification and the sparsification tasks for CSPs ⋮
\((\mathbb{Z},\mathrm{succ},U)\), \((\mathbb{Z},E,U)\), and their CSP's ⋮
Constraint satisfaction problem: what makes the problem easy ⋮
Mixing is hard for triangle-free reflexive graphs ⋮
On guarded extensions of MMSNP ⋮
Solving infinite-domain CSPs using the patchwork property ⋮
The complexity of the matroid homomorphism problem ⋮
Recolouring homomorphisms to triangle-free reflexive graphs ⋮
Computing a partition function of a generalized pattern-based energy over a semiring ⋮
Unnamed Item ⋮
General lower bounds and improved algorithms for infinite-domain CSPs ⋮
Proof Complexity Meets Algebra ⋮
Unnamed Item ⋮
Unnamed Item ⋮
Unnamed Item ⋮
Unnamed Item ⋮
The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems ⋮
Acyclic orders, partition schemes and CSPs: unified hardness proofs and improved algorithms ⋮
Sandwiches for promise constraint satisfaction ⋮
Constraint satisfaction problems over semilattice block Mal'tsev algebras ⋮
Unnamed Item ⋮
Galois connections for patterns: an algebra of labelled graphs ⋮
The number of clones determined by disjunctions of unary relations ⋮
Time Complexity of Constraint Satisfaction via Universal Algebra ⋮
Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices ⋮
A Dichotomy for First-Order Reducts of Unary Structures ⋮
Beyond PCSP (\textbf{1-in-3}, \textbf{NAE}) ⋮
Unnamed Item ⋮
Computational Short Cuts in Infinite Domain Constraint Satisfaction ⋮
The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom ⋮
The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side ⋮
The Complexity of Quantified Constraints: Collapsibility, Switchability, and the Algebraic Formulation
This page was built for publication: A Proof of the CSP Dichotomy Conjecture
