Edited Volume
Research Papers
- Functors on relational structures which admit both left and right adjoints
V. Dalmau, A. Krokhin and J. Opršal.
SIAM Journal on Discrete Mathematics, 38(3), 2041-2068, 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]