Constraint Satisfaction Problems and Finite Algebras. - Andrei A. Bulatov; Andrei A. Krokhin; Peter Jeavons 001 (ICALP, 2000)

A Complete Classification of Complexity in Allens Algebra in the Presence of a Non-Trivial Basic Relation. - Andrei A. Krokhin; Peter Jeavons 001; Peter Jonsson (IJCAI, 2001)

The complexity of maximal constraint languages. - Andrei A. Bulatov; Andrei A. Krokhin; Peter Jeavons 001 (STOC, 2001)

The complexity of constraints on intervals and lengths - Andrei A. Krokhin; Peter Jeavons 001; Peter Jonsson (Electron. Colloquium Comput. Complex., 2001)

Congruences of Clone Lattices, II. - Andrei A. Krokhin (Order, 2001)

Extending the Point Algebra into the Qualitative Algebra. - Andrei A. Krokhin; Peter Jonsson (TIME, 2002)

Soft Constraints: Complexity and Multimorphisms. - David A. Cohen; Martin C. Cooper; Peter Jeavons 001; Andrei A. Krokhin (CP, 2003)

Quantified Constraints: Algorithms and Complexity. - Ferdinand Börner; Andrei A. Bulatov; Peter Jeavons 001; Andrei A. Krokhin (CSL, 2003)

Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey. - Andrei A. Krokhin; Andrei A. Bulatov; Peter Jeavons 001 (ISMVL, 2003)

Solving Order Constraints in Logarithmic Space. - Andrei A. Krokhin; Benoît Larose (STACS, 2003)

Reasoning about temporal relations: The tractable subalgebras of Allen's interval algebra. - Andrei A. Krokhin; Peter Jeavons 001; Peter Jonsson (J. ACM, 2003)

First-Order Definable Retraction Problems for Posets and Reflexive Graph. - Víctor Dalmau; Andrei A. Krokhin; Benoît Larose (LICS, 2004)

Identifying Efficiently Solvable Cases of Max CSP. - David A. Cohen; Martin C. Cooper; Peter Jeavons 001; Andrei A. Krokhin (STACS, 2004)

Complexity classification in qualitative temporal constraint reasoning. - Peter Jonsson; Andrei A. Krokhin (Artif. Intell., 2004)

A Maximal Tractable Class of Soft Constraints. - David A. Cohen; Martin C. Cooper; Peter Jeavons 001; Andrei A. Krokhin (J. Artif. Intell. Res., 2004)

Constraint Satisfaction Problems on Intervals and Length. - Andrei A. Krokhin; Peter Jeavons 001; Peter Jonsson (SIAM J. Discret. Math., 2004)

Recognizing frozen variables in constraint satisfaction problems. - Peter Jonsson; Andrei A. Krokhin (Theor. Comput. Sci., 2004)

Maximum Constraint Satisfaction on Diamonds. - Andrei A. Krokhin; Benoît Larose (CP, 2005)

Supermodular functions and the complexity of MAX CSP. - David A. Cohen; Martin C. Cooper; Peter Jeavons 001; Andrei A. Krokhin (Discret. Appl. Math., 2005)

Classifying the Complexity of Constraints Using Finite Algebras. - Andrei A. Bulatov; Peter Jeavons 001; Andrei A. Krokhin (SIAM J. Comput., 2005)

The complexity of soft constraint satisfaction. - David A. Cohen; Martin C. Cooper; Peter Jeavons 001; Andrei A. Krokhin (Artif. Intell., 2006)

A Monoidal Interval of Clones of Selfdual Functions. - Andrei A. Krokhin; Ivo G. Rosenberg (J. Autom. Lang. Comb., 2006)

The Approximability of Three-valued MAX CSP. - Peter Jonsson; Mikael Klasson; Andrei A. Krokhin (SIAM J. Comput., 2006)

Ruling Out Polynomial-Time Approximation Schemes for Hard Constraint Satisfaction Problems. - Peter Jonsson; Andrei A. Krokhin; Fredrik Kuivinen (CSR, 2007)

Maximum H-colourable subdigraphs and constraint optimization with arbitrary weights. - Peter Jonsson; Andrei A. Krokhin (J. Comput. Syst. Sci., 2007)

First-order Definable Retraction Problems for Posets and Reflexive Graphs. - Víctor Dalmau; Andrei A. Krokhin; Benoît Larose (J. Log. Comput., 2007)

Dualities for Constraint Satisfaction Problems. - Andrei A. Bulatov; Andrei A. Krokhin; Benoît Larose (Complexity of Constraints, 2008)

Caterpillar Duality for Constraint Satisfaction Problems. - Catarina Carvalho; Víctor Dalmau; Andrei A. Krokhin (LICS, 2008)

Retractions onto series-parallel posets. - Víctor Dalmau; Andrei A. Krokhin; Benoît Larose (Discret. Math., 2008)

Majority constraints have bounded pathwidth duality. - Víctor Dalmau; Andrei A. Krokhin (Eur. J. Comb., 2008)

The approximability of MAX CSP with fixed-value constraints. - Vladimir G. Deineko; Peter Jonsson; Mikael Klasson; Andrei A. Krokhin (J. ACM, 2008)

Computational complexity of auditing finite attributes in statistical databases. - Peter Jonsson; Andrei A. Krokhin (J. Comput. Syst. Sci., 2008)

Complexity of Clausal Constraints Over Chains. - Nadia Creignou; Miki Hermann; Andrei A. Krokhin; Gernot Salzer (Theory Comput. Syst., 2008)

Maximizing Supermodular Functions on Product Lattices, with Application to Maximum Constraint Satisfaction. - Andrei A. Krokhin; Benoît Larose (SIAM J. Discret. Math., 2008)

09441 Abstracts Collection - The Constraint Satisfaction Problem: Complexity and Approximability. - Andrei A. Bulatov; Martin Grohe; Phokion G. Kolaitis; Andrei A. Krokhin (The Constraint Satisfaction Problem: Complexity and Approximability, 2009)

09441 Executive Summary - The Constraint Satisfaction Problem: Complexity and Approximability. - Andrei A. Bulatov; Martin Grohe; Phokion G. Kolaitis; Andrei A. Krokhin (The Constraint Satisfaction Problem: Complexity and Approximability, 2009)

The complexity of constraint satisfaction games and QCSP. - Ferdinand Börner; Andrei A. Bulatov; Hubie Chen; Peter Jeavons 001; Andrei A. Krokhin (Inf. Comput., 2009)

Hard constraint satisfaction problems have hard gaps at location 1. - Peter Jonsson; Andrei A. Krokhin; Fredrik Kuivinen (Theor. Comput. Sci., 2009)

Tree Dualities for Constraint Satisfaction. - Andrei A. Krokhin (CSL, 2010)

Retractions to Pseudoforests. - Tomás Feder; Pavol Hell; Peter Jonsson; Andrei A. Krokhin; Gustav Nordh (SIAM J. Discret. Math., 2010)

CSP duality and trees of bounded pathwidth. - Catarina Carvalho; Víctor Dalmau; Andrei A. Krokhin (Theor. Comput. Sci., 2010)

The Complexity of Evaluating First-Order Sentences over a Fixed Structure. - Andrei A. Krokhin (LICS, 2011)

Two new homomorphism dualities and lattice operations. - Catarina Carvalho; Víctor Dalmau; Andrei A. Krokhin (J. Log. Comput., 2011)

The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 12451). - Johan Håstad; Andrei A. Krokhin; Dániel Marx (Dagstuhl Reports, 2012)

The Complexity of the List Homomorphism Problem for Graphs. - László Egri; Andrei A. Krokhin; Benoît Larose; Pascal Tesson (Theory Comput. Syst., 2012)

On the hardness of losing weight. - Andrei A. Krokhin; Dániel Marx (ACM Trans. Algorithms, 2012)

Robust Satisfiability for CSPs: Hardness and Algorithmic Results. - Víctor Dalmau; Andrei A. Krokhin (ACM Trans. Comput. Theory, 2013)

The Complexity of Valued Constraint Satisfaction. - Peter Jeavons 001; Andrei A. Krokhin; Stanislav Zivný (Bull. EATCS, 2014)

Skew Bisubmodularity and Valued CSPs. - Anna Huber; Andrei A. Krokhin; Robert Powell (SIAM J. Comput., 2014)

Oracle Tractability of Skew Bisubmodular Functions. - Anna Huber; Andrei A. Krokhin (SIAM J. Discret. Math., 2014)

Towards a Characterization of Constant-Factor Approximable Min CSPs. - Víctor Dalmau; Andrei A. Krokhin; Rajsekar Manokaran (SODA, 2015)

A Reduction from Valued CSP to Min Cost Homomorphism Problem for Digraphs. - Robert Powell; Andrei A. Krokhin (CoRR, 2015)

The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 15301). - Andrei A. Bulatov; Venkatesan Guruswami; Andrei A. Krokhin; Dániel Marx (Dagstuhl Reports, 2015)

On algebras with many symmetric operations. - Catarina Carvalho; Andrei A. Krokhin (Int. J. Algebra Comput., 2016)

Polymorphisms, and How to Use Them. - Libor Barto; Andrei A. Krokhin; Ross Willard (The Constraint Satisfaction Problem, 2017)

The Complexity of Valued CSPs. - Andrei A. Krokhin; Stanislav Zivný (The Constraint Satisfaction Problem, 2017)

The Complexity of General-Valued CSPs. - Vladimir Kolmogorov; Andrei A. Krokhin; Michal Rolínek (SIAM J. Comput., 2017)

Binarisation for Valued Constraint Satisfaction Problems. - David A. Cohen; Martin C. Cooper; Peter G. Jeavons; Andrei A. Krokhin; Robert Powell; Stanislav Zivný (SIAM J. Discret. Math., 2017)

Towards a characterization of constant-factor approximable finite-valued CSPs. - Víctor Dalmau; Andrei A. Krokhin; Rajsekar Manokaran (J. Comput. Syst. Sci., 2018)

The Complexity of 3-Colouring H-Colourable Graphs. - Andrei A. Krokhin; Jakub Oprsal (FOCS, 2019)

Algebraic approach to promise constraint satisfaction. - Jakub Bulín; Andrei A. Krokhin; Jakub Oprsal (STOC, 2019)

The complexity of 3-colouring H-colourable graphs. - Andrei A. Krokhin; Jakub Oprsal (Electron. Colloquium Comput. Complex., 2019)

Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs. - Víctor Dalmau; Marcin Kozik; Andrei A. Krokhin; Konstantin Makarychev; Yury Makarychev; Jakub Oprsal (SIAM J. Comput., 2019)

Algebraic Approach to Promise Constraint Satisfaction. - Libor Barto; Jakub Bulín; Andrei A. Krokhin; Jakub Oprsal (J. ACM, 2021)

An Invitation to the Promise Constraint Satisfaction Problem. - Andrei A. Krokhin; Jakub Oprsal (Electron. Colloquium Comput. Complex., 2022)

On the complexity of the approximate hypergraph homomorphism problem. - Lorenzo Ciardo; Marcin Kozik; Andrei A. Krokhin; Tamio-Vesa Nakajima; Stanislav Zivný (CoRR, 2023)

Topology and Adjunction in Promise Constraint Satisfaction. - Andrei A. Krokhin; Jakub Oprsal; Marcin Wrochna; Stanislav Zivný (SIAM J. Comput., 2023)

Manuel Bodirsky. Complexity of Infinite-Domain Constraint Satisfaction. Lecture Notes in Logic, vol. 52. Cambridge University Press, 2021. - Andrei A. Krokhin (Bull. Symb. Log., 2024)

Functors on Relational Structures Which Admit Both Left and Right Adjoints. - Víctor Dalmau; Andrei A. Krokhin; Jakub Oprsal (SIAM J. Discret. Math., 2024)

1-in-3 vs. Not-All-Equal: Dichotomy of a Broken Promise. - Lorenzo Ciardo; Marcin Kozik; Andrei A. Krokhin; Tamio-Vesa Nakajima; Stanislav Zivný (ACM Trans. Comput. Log., 2025)