| 2026 | ICALP | Approximating 1-In-3 SAT by Linearly Ordered Hypergraph 3-Colouring Is NP-Hard. | Andrei A. Krokhin, Danny Vagnozzi |
| 2024 | LICS | 1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise. | Lorenzo Ciardo, Marcin Kozik, Andrei A. Krokhin, Tamio-Vesa Nakajima, Stanislav Zivn |
| 2019 | FOCS | The Complexity of 3-Colouring H-Colourable Graphs. | Andrei A. Krokhin, Jakub Oprsal |
| 2019 | STOC | Algebraic approach to promise constraint satisfaction. | Jakub Buln, Andrei A. Krokhin, Jakub Oprsal |
| 2017 | SODA | Robust algorithms with polynomial loss for near-unanimity CSPs. | Vctor Dalmau, Marcin Kozik, Andrei A. Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal |
| 2015 | FOCS | The Complexity of General-Valued CSPs. | Vladimir Kolmogorov, Andrei A. Krokhin, Michal Rolnek |
| 2015 | SODA | Towards a Characterization of Constant-Factor Approximable Min CSPs. | Vctor Dalmau, Andrei A. Krokhin, Rajsekar Manokaran |
| 2013 | SODA | Skew Bisubmodularity and Valued CSPs. | Anna Huber, Andrei A. Krokhin, Robert Powell |
| 2011 | LICS | The Complexity of Evaluating First-Order Sentences over a Fixed Structure. | Andrei A. Krokhin |
| 2010 | CSL | Tree Dualities for Constraint Satisfaction. | Andrei A. Krokhin |
| 2010 | STACS | The Complexity of the List Homomorphism Problem for Graphs. | Lszl Egri, Andrei A. Krokhin, Benot Larose, Pascal Tesson |
| 2008 | ICALP | On the Hardness of Losing Weight. | Andrei A. Krokhin, Dniel Marx |
| 2008 | LICS | Caterpillar Duality for Constraint Satisfaction Problems. | Catarina Carvalho, Vctor Dalmau, Andrei A. Krokhin |
| 2007 | CSR | Ruling Out Polynomial-Time Approximation Schemes for Hard Constraint Satisfaction Problems. | Peter Jonsson, Andrei A. Krokhin, Fredrik Kuivinen |
| 2005 | CP | Maximum Constraint Satisfaction on Diamonds. | Andrei A. Krokhin, Benot Larose |
| 2004 | LICS | First-Order Definable Retraction Problems for Posets and Reflexive Graph. | Vctor Dalmau, Andrei A. Krokhin, Benot Larose |
| 2004 | STACS | Identifying Efficiently Solvable Cases of Max CSP. | David A. Cohen, Martin C. Cooper, Peter Jeavons, Andrei A. Krokhin |
| 2003 | CP | Soft Constraints: Complexity and Multimorphisms. | David A. Cohen, Martin C. Cooper, Peter Jeavons, Andrei A. Krokhin |
| 2003 | CSL | Quantified Constraints: Algorithms and Complexity. | Ferdinand Brner, Andrei A. Bulatov, Peter Jeavons, Andrei A. Krokhin |
| 2003 | IJCAI | A Maximal Tractable Class of Soft Constraints. | David A. Cohen, Martin C. Cooper, Peter Jeavons, Andrei A. Krokhin |
| 2003 | STACS | Solving Order Constraints in Logarithmic Space. | Andrei A. Krokhin, Benot Larose |
| 2002 | STACS | The Complexity of Constraints on Intervals and Lengths. | Andrei A. Krokhin, Peter Jeavons, Peter Jonsson |
| 2002 | TIME | Extending the Point Algebra into the Qualitative Algebra. | Andrei A. Krokhin, Peter Jonsson |
| 2001 | IJCAI | A Complete Classification of Complexity in Allens Algebra in the Presence of a Non-Trivial Basic Relation. | Andrei A. Krokhin, Peter Jeavons, Peter Jonsson |
| 2001 | STOC | The complexity of maximal constraint languages. | Andrei A. Bulatov, Andrei A. Krokhin, Peter Jeavons |
| 2000 | ICALP | Constraint Satisfaction Problems and Finite Algebras. | Andrei A. Bulatov, Andrei A. Krokhin, Peter Jeavons |