Edited Volume

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

Research Papers

• 1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise
  L. Ciardo, M. Kozik, A. Krokhin, T.-V. Nakajima, and S. Živný.
  LICS’24, accepted. 2024. ArXiv 2302.03456.

• Functors on relational structures which admit both left and right adjoints
  V. Dalmau, A. Krokhin and J. Opršal.
  SIAM Journal on Discrete Mathematics, accepted. 2024.
• Topology and adjunction in promise constraint satisfaction
  A. Krokhin, J. Opršal, M. Wrochna, and S. Živný.
  SIAM Journal on Computing, 52(1), 38-79, 2023.
  Extended version of merged FOCS’19 and SODA’20 papers.
• An invitation to the Promise Constraint Satisfaction Problem
  A. Krokhin and J. Opršal.
  ACM SIGLOG News, 9(3), 2022, 30-59.
• 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. Erratum
• 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.
• 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]