Edited Volume

• The Constraint Satisfaction Problem: Complexity and Approximability
  Editors: A. Krokhin and S. Živný.
  Dagstuhl Follow-Ups series, Volume 7, 2017.

Research Papers

• Topology and adjunction in promise constraint satisfaction
  A. Krokhin, J. Opršal, M. Wrochna, and S. Živný.
  SIAM Journal on Computing, accepted for publication.
  Extended version of merged FOCS’19 and SODA’20 papers.
• Algebraic approach to promise constraint satisfaction
  L. Barto, J. Bulín, A. Krokhin, and J. Opršal.
  Journal of the ACM, 66(4), Article 28, 1-66, 2021.
  Conference version in STOC’19, 602-613, 2019. (More suitable for the first read).
• Robust algorithms with polynomial loss for near-unanimity CSPs
  V. Dalmau, M. Kozik, A. Krokhin, K. Makarychev, Y. Makarychev, and J. Opršal.
  SIAM Journal on Computing, 48(6), 1763-1795, 2019.
  Conference version in SODA’17, 340-357, 2017.
• Towards a characterization of constant-factor approximable Finite-Valued CSPs
  V. Dalmau, A. Krokhin, and R. Manokaran
  Journal of Computer and System Sciences, 97, 14-27, 2018.
  Conference version in SODA’15, 847-857, 2015.
• Binarisation for Valued Constraint Satisfaction Problems
  D. Cohen, M. Cooper, P. Jeavons, A. Krokhin, R. Powell, and S. Živný.
  SIAM Journal on Discrete Mathematics, 31(4), 2279–2300, 2017.
• Polymorphisms, and how to use them
  L. Barto, A. Krokhin and R. Willard.
  Survey. In: The Constraint Satisfaction Problem: Complexity and Approximability, 1-44, 2017.
• The complexity of valued CSPs
  A. Krokhin and S. Živný.
  Survey. In: The Constraint Satisfaction Problem: Complexity and Approximability, 233-266, 2017.
• The complexity of general-valued CSPs
  V. Kolmogorov, A. Krokhin, and M. Rolinek.
  SIAM Journal on Computing, 46(3), 1087-1110, 2017.
  Conference version in FOCS’15, 1246-1258, 2015.
• On algebras with many symmetric operations
  C. Carvalho and A. Krokhin.
  International Journal of Algebra and Computation, 26(5), 1019-1032, 2016.
• Characterizations of several Maltsev conditions
  M. Kozik, A. Krokhin, M. Valeriote, and R. Willard.
  Algebra Universalis, 73 (3-4), 205-224, 2015.
• The complexity of valued constraint satisfaction
  P. Jeavons, A. Krokhin, and S. Živný.
  Survey. Algorithmics Column of Bulletin of the EATCS, 113, 21-55, 2014. (Errata)
• Oracle tractability of skew bisubmodular functions
  A. Huber and A. Krokhin.
  SIAM Journal on Discrete Mathematics, 28 (4), 1828-1837, 2014.
• Skew bisubmodularity and valued CSPs
  A. Huber, A. Krokhin, and R. Powell.
  SIAM Journal on Computing, 43 (3), 1064–1084, 2014.
  Conference version in SODA’13, 1296-1305, 2013.
• Robust satisfiability for CSPs: hardness and algorithmic results
  V. Dalmau and A. Krokhin.
  ACM Transactions on Computation Theory, 5 (4), Article 15, 2013.
• The complexity of the list homomorphism problem for graphs
  L. Egri, A. Krokhin, B. Larose and P. Tesson.
  Theory of Computing Systems, 51 (2), 143-178, 2012.
  Conference version in STACS’10, LIPIcs 5, 335-346, 2010.
• On the hardness of losing weight
  A. Krokhin and D. Marx.
  ACM Transactions on Algorithms, 8 (2), Article No.19, 2012.
  Conference version in ICALP’08, LNCS 5125, 662-673, 2008.
• Two new homomorphism dualities and lattice operations
  C. Carvalho, V. Dalmau and A. Krokhin.
  Journal of Logic and Computation, 21 (6), 1065-1092, 2011.
  Conference version (of part of this paper) in LICS’08, 307-316, 2008.
• CSP duality and trees of bounded pathwidth
  C. Carvalho, V. Dalmau and A. Krokhin.
  Theoretical Computer Science, 411 (34-36), 3188-3208, 2010.
• Retractions to pseudoforests
  T. Feder, P. Hell, P. Jonsson, A. Krokhin and G. Nordh.
  SIAM Journal on Discrete Mathematics, 24 (1), 101-112, 2010.
• Hard constraint satisfaction problems have hard gaps at location 1
  P. Jonsson, A. Krokhin and F. Kuivinen.
  Theoretical Computer Science, 410 (38-40), 3856-3874, 2009.
  Conference version in CSR’07, LNCS 4649, 2007, 182-193.
• The complexity of constraint satisfaction games and QCSP
  F. Boerner, A. Bulatov, H. Chen, P. Jeavons and A. Krokhin.
  Information and Computation, 207 (9), 923-944, 2009.
  Conference version (of part of this paper) in CSL’03, LNCS 2803, 2003, 58-70.
• Dualities for constraint satisfaction problems
  A. Bulatov, A. Krokhin and B. Larose.
  Survey, In: Complexity of Constraints, LNCS 5250, 93-124, 2008. (Errata)
• The approximability of Max CSP with fixed-value constraints
  V. Deineko, P. Jonsson, M. Klasson and A. Krokhin
  Journal of the ACM, 55 (4), Article No.16, 2008.
  Conference version in Eurocomb’05, DMTCS Proceedings, volume AE, 51-56, 2005.
• Computational complexity of auditing discrete attributes in statistical databases
  P. Jonsson and A. Krokhin.
  Journal of Computer and System Sciences, 74 (5), 898-909, 2008.
• Majority constraints have bounded pathwidth duality
  V. Dalmau and A. Krokhin.
  European Journal of Combinatorics, 29 (4), 821-837, 2008.
• Maximizing supermodular functions on product lattices, with application to maximum constraint satisfaction
  A. Krokhin and B. Larose.
  SIAM Journal on Discrete Mathematics, 22 (1), 312-328, 2008.
  Conference version (of part of this paper) in CP’05, LNCS 3709, 2005, 388-402.
• Retractions onto series-parallel posets
  V. Dalmau, A. Krokhin and B. Larose.
  Discrete Mathematics, 308 (11), 2104-2114, 2008.
• Complexity of clausal constraints over chains
  N. Creignou, M. Hermann, A. Krokhin and G. Salzer.
  Theory of Computing Systems, 42 (2), 239-255, 2008.
• A note on supermodular sublattices in finite relatively complemented lattices
  A. Krokhin and B. Larose.
  Algebra Universalis, 59 (1-2), 2008, 237-241.
• Maximum H-colourable subdigraphs and constraint optimization with arbitrary weights
  P. Jonsson and A. Krokhin.
  Journal of Computer and System Sciences, 73 (5), 691-702, 2007.
• First-order definable retraction problems for posets and reflexive graphs
  V. Dalmau, A. Krokhin and B. Larose.
  Journal of Logic and Computation, 17(1), 31-51, 2007.
  Conference version in LICS’04, 2004, 232-241.
• The complexity of soft constraint satisfaction
  D. Cohen, M. Cooper, P.Jeavons and A. Krokhin.
  Artificial Intelligence Journal, 170 (11), 983-1016, 2006.
  Conference version (of part of this paper) in CP’03, LNCS 2833, 2003, 244–258.
• The approximability of three-valued Max CSP
  P. Jonsson, M. Klasson and A. Krokhin.
  SIAM Journal on Computing, 35 (6), 1329-1349, 2006.
• A monoidal interval of clones of selfdual functions
  A. Krokhin and I. G. Rosenberg.
  Journal of Automata, Languages, and Combinatorics, 11 (2), 2006, 189-208.
• Supermodular functions and the complexity of Max CSP
  D. Cohen, M. Cooper, P. Jeavons and A. Krokhin.
  Discrete Applied Mathematics, 149 (1-3), 53-72, 2005.
  Conference version in STACS’04, LNCS 2996, 2004, 152-163.
• The complexity of constraint satisfaction: An algebraic approach
  A. Krokhin, A. Bulatov and P. Jeavons.
  Survey, In: Structural Theory of Automata, Semigroups and Universal Algebra (Montreal, 2003),
  NATO Science Seiries II: Mathematics, Physics, Chemistry, volume 207, 181-213, 2005.
• Classifying the complexity of constraints using finite algebras
  A. Bulatov, P. Jeavons and A. Krokhin.
  SIAM Journal on Computing, 34 (3), 720-742, 2005.
  Conference version in ICALP’00, LNCS 1853, 2000, 272-282.
• Complexity classification in qualitative temporal constraint reasoning
  P. Jonsson and A. Krokhin.
  Artificial Intelligence Journal, 160 (1-2), 35-51, 2004.
  Conference version in TIME’02, 2002, 28-35.
• Recognizing frozen variables in constraint satisfaction problems
  P. Jonsson and A. Krokhin.
  Theoretical Computer Science, 160 (1-3), 93-113, 2004.
• A maximal tractable class of soft constraints
  D. Cohen, M. Cooper, P. Jeavons, A. Krokhin.
  Journal of Artificial Intelligence Research, 22, 2004, 1-22.
  Conference version in IJCAI’03 2003, 209-214.
• Constraint satisfaction problems on intervals and lengths
  A. Krokhin, P. Jeavons, and P. Jonsson.
  SIAM Journal on Discrete Mathematics, 17(3), 2004, 453-477.
  Conference version in STACS’02, LNCS 2285, 2002, 443-454.
• Reasoning about temporal relations: The tractable subalgebras of Allen’s interval algebra
  A. Krokhin, P. Jeavons, and P. Jonsson.
  Journal of the ACM, 50 (5), 2003, 591-640.
  Conference version in IJCAI’01, 2001, 83-88.
• Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey
  A. Krokhin, A. Bulatov, and P. Jeavons.
  in ISMVL’03, 2003, 343-351.
• Solving order constraints in logarithmic space
  A. Krokhin and B. Larose.
  in STACS’03, LNCS 2607, 2003, 379-390.
• Quantified constraints and surjective polymorphisms
  F. Boerner, A. Krokhin, A. Bulatov, P. Jeavons.
  Technical report PRG-RR-02-11, Oxford University, 2002, 25pp.
• A monoidal interval of isotone clones on a finite chain
  A. Krokhin and B. Larose.
  Acta Sci. Math. (Szeged), 68 (1-2), 2002, 37-62.
• The complexity of maximal constraint languages
  A. Bulatov, A. Krokhin, and P. Jeavons.
  in STOC’01, 2001, 667-674.
• On the structure of clone lattices, II
  A. Bulatov, A. Krokhin, K. Safin, A. Semigrodskikh, and E. Sukhanov.
  Multiple-Valued Logic, 7 (5-6), 2001, 379-389.
• Congruences of clone lattices, II
  A. Krokhin.
  Order, 18 (2), 2001, 151-159.
• On clones, transformation monoids and finite Boolean algebras
  A. Krokhin.
  Algebra Universalis, 46 (1-2), 2001, 231-236.
• On clones preserving a reflexive binary relation
  A. Krokhin and D. Schweigert.
  Acta Sci. Math. (Szeged), 67 (3-4), 2001, 461-473.
• Congruences of clone lattices, I
  A. Krokhin and A. Semigrodskikh.
  Contributions to General Algebra, 11, Verlag Johannes Heyn, Klagenfurt, 1999, 137-150.
• Maximal clones in monoidal intervals, I
  A. Krokhin.
  Sib. Mat. Zhournal, 40(3), 1999, 619-631.[Russian; engl.transl.: Siberian Math.J., 40(3), 1999, 528-538]
• On the structure of the lattice of closed classes of polynomials
  A. Krokhin, K. Safin, and E. Sukhanov.
  Diskretnaya Matematika, 9(2), 1997, 24-39.[Russian; engl.transl.: Discrete Mathematics and Applications, 7(2), 131-146]
• Boolean lattices as intervals in clone lattices
  A. Krokhin.
  Multiple-Valued Logic, 2(3), 1997, 263-271.
• On clones, transformation monoids, and associative rings
  A. Krokhin.
  Algebra Universalis, 37(4), 1997, 527-540.
• Monoidal and distributive intervals in clone lattices
  A. Krokhin.
  Algebra (Krasnoyarsk, 1993). Eds.: Yu. L. Ershov et al., de Gruyter Verlag, Berlin, 1996, 153-159.
• On the structure of clone lattices
  A. Bulatov, A. Krokhin, K. Safin, and E.Sukhanov.
  General Algebra and Discrete Mathematics, eds.: K. Denecke, O. Lueders, Heldermann Verlag, Berlin, 1995, 27-34.
• Monoid intervals in lattices of clones
  A. Krokhin.
  Algebra i Logika, 34(3), 1995, 282-310. [Russian; engl.transl.: Algebra and Logic, 34(3), 155-168]