Research Papers

Constraint Satisfaction Problems

• Skew bisubmodularity and valued CSPs
  
A. Huber, A. Krokhin, and R. Powell.
Submitted for journal publication.
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, accepted, 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.

• 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.

• 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 survey paper)
  
A. Krokhin, A. Bulatov and P. Jeavons.
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.

• The complexity of maximal constraint languages
  
A. Bulatov, A. Krokhin, and P. Jeavons.
in STOC'01, 2001, 667-674.

Universal Algebra, Clone Theory, Lattice Theory

• A note on supermodular sublattices in finite relatively complemented lattices
  
A. Krokhin and B. Larose.
Algebra Universalis, 59 (1-2), 2008, 237-241.

• 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.

• 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.

• 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]