Andrei A. Krokhin

	2009
43		Ferdinand Börner, Andrei A. Bulatov, Hubie Chen, Peter Jeavons, Andrei A. Krokhin: The complexity of constraint satisfaction games and QCSP. Inf. Comput. 207(9): 923-944 (2009)
42		Peter Jonsson, Andrei A. Krokhin, Fredrik Kuivinen: Hard constraint satisfaction problems have hard gaps at location 1. Theor. Comput. Sci. 410(38-40): 3856-3874 (2009)
	2008
41		Andrei A. Bulatov, Andrei A. Krokhin, Benoit Larose: Dualities for Constraint Satisfaction Problems. Complexity of Constraints 2008: 93-124
40		Andrei A. Krokhin, Dániel Marx: On the Hardness of Losing Weight. ICALP (1) 2008: 662-673
39		Catarina Carvalho, Víctor Dalmau, Andrei A. Krokhin: Caterpillar Duality for Constraint Satisfaction Problems. LICS 2008: 307-316
38		Víctor Dalmau, Andrei A. Krokhin, Benoit Larose: Retractions onto series-parallel posets. Discrete Mathematics 308(11): 2104-2114 (2008)
37		Víctor Dalmau, Andrei A. Krokhin: Majority constraints have bounded pathwidth duality. Eur. J. Comb. 29(4): 821-837 (2008)
36		Vladimir G. Deineko, Peter Jonsson, Mikael Klasson, Andrei A. Krokhin: The approximability of MAX CSP with fixed-value constraints. J. ACM 55(4): (2008)
35		Peter Jonsson, Andrei A. Krokhin: Computational complexity of auditing finite attributes in statistical databases. J. Comput. Syst. Sci. 74(5): 898-909 (2008)
34		Andrei A. Krokhin, Benoit Larose: Maximizing Supermodular Functions on Product Lattices, with Application to Maximum Constraint Satisfaction. SIAM J. Discrete Math. 22(1): 312-328 (2008)
33		Nadia Creignou, Miki Hermann, Andrei A. Krokhin, Gernot Salzer: Complexity of Clausal Constraints Over Chains. Theory Comput. Syst. 42(2): 239-255 (2008)
	2007
32		Peter Jonsson, Andrei A. Krokhin, Fredrik Kuivinen: Ruling Out Polynomial-Time Approximation Schemes for Hard Constraint Satisfaction Problems. CSR 2007: 182-193
31		Peter Jonsson, Andrei A. Krokhin, Fredrik Kuivinen: Hard constraint satisfaction problems have hard gaps at location 1 CoRR abs/0712.1532: (2007)
30		Peter Jonsson, Andrei A. Krokhin: Maximum H-colourable subdigraphs and constraint optimization with arbitrary weights. J. Comput. Syst. Sci. 73(5): 691-702 (2007)
29		Víctor Dalmau, Andrei A. Krokhin, Benoit Larose: First-order Definable Retraction Problems for Posets and Reflexive Graphs. J. Log. Comput. 17(1): 31-51 (2007)
	2006
28		David A. Cohen, Martin C. Cooper, Peter Jeavons, Andrei A. Krokhin: The complexity of soft constraint satisfaction. Artif. Intell. 170(11): 983-1016 (2006)
27		Vladimir G. Deineko, Peter Jonsson, Mikael Klasson, Andrei A. Krokhin: The approximability of MAX CSP with fixed-value constraints CoRR abs/cs/0602075: (2006)
26		Andrei A. Krokhin, Ivo G. Rosenberg: A Monoidal Interval of Clones of Selfdual Functions. Journal of Automata, Languages and Combinatorics 11(2): 189-208 (2006)
25		Peter Jonsson, Mikael Klasson, Andrei A. Krokhin: The Approximability of Three-valued MAX CSP. SIAM J. Comput. 35(6): 1329-1349 (2006)
	2005
24		Andrei A. Krokhin, Benoit Larose: Maximum Constraint Satisfaction on Diamonds. CP 2005: 388-402
23		David A. Cohen, Martin C. Cooper, Peter Jeavons, Andrei A. Krokhin: Supermodular functions and the complexity of MAX CSP. Discrete Applied Mathematics 149(1-3): 53-72 (2005)
22		Andrei A. Bulatov, Peter Jeavons, Andrei A. Krokhin: Classifying the Complexity of Constraints Using Finite Algebras. SIAM J. Comput. 34(3): 720-742 (2005)
	2004
21		Víctor Dalmau, Andrei A. Krokhin, Benoit Larose: First-Order Definable Retraction Problems for Posets and Reflexive Graph. LICS 2004: 232-241
20		David A. Cohen, Martin C. Cooper, Peter Jeavons, Andrei A. Krokhin: Identifying Efficiently Solvable Cases of Max CSP. STACS 2004: 152-163
19		Peter Jonsson, Andrei A. Krokhin: Complexity classification in qualitative temporal constraint reasoning. Artif. Intell. 160(1-2): 35-51 (2004)
18		Peter Jonsson, Mikael Klasson, Andrei A. Krokhin: The approximability of three-valued MAX CSP CoRR abs/cs/0412042: (2004)
17		David A. Cohen, Martin C. Cooper, Peter Jeavons, Andrei A. Krokhin: A Maximal Tractable Class of Soft Constraints. J. Artif. Intell. Res. (JAIR) 22: 1-22 (2004)
16		Andrei A. Krokhin, Peter Jeavons, Peter Jonsson: Constraint Satisfaction Problems on Intervals and Length. SIAM J. Discrete Math. 17(3): 453-477 (2004)
15		Peter Jonsson, Andrei A. Krokhin: Recognizing frozen variables in constraint satisfaction problems. Theor. Comput. Sci. 329(1-3): 93-113 (2004)
	2003
14		David A. Cohen, Martin C. Cooper, Peter Jeavons, Andrei A. Krokhin: Soft Constraints: Complexity and Multimorphisms. CP 2003: 244-258
13		Ferdinand Börner, Andrei A. Bulatov, Peter Jeavons, Andrei A. Krokhin: Quantified Constraints: Algorithms and Complexity. CSL 2003: 58-70
12		David A. Cohen, Martin C. Cooper, Peter Jeavons, Andrei A. Krokhin: A Maximal Tractable Class of Soft Constraints. IJCAI 2003: 209-214
11		Andrei A. Krokhin, Andrei A. Bulatov, Peter Jeavons: Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey. ISMVL 2003: 343-
10		Andrei A. Krokhin, Benoit Larose: Solving Order Constraints in Logarithmic Space. STACS 2003: 379-390
9		Andrei A. Krokhin, Peter Jonsson: Recognizing Frozen Variables in Constraint Satisfaction Problems Electronic Colloquium on Computational Complexity (ECCC)(062): (2003)
8		Andrei A. Krokhin, Peter Jeavons, Peter Jonsson: Reasoning about temporal relations: The tractable subalgebras of Allen's interval algebra. J. ACM 50(5): 591-640 (2003)
	2002
7		Andrei A. Krokhin, Peter Jeavons, Peter Jonsson: The Complexity of Constraints on Intervals and Lengths. STACS 2002: 443-454
6		Andrei A. Krokhin, Peter Jonsson: Extending the Point Algebra into the Qualitative Algebra. TIME 2002: 28-35
	2001
5		Andrei A. Krokhin, Peter Jeavons, Peter Jonsson: A Complete Classification of Complexity in Allens Algebra in the Presence of a Non-Trivial Basic Relation. IJCAI 2001: 83-88
4		Andrei A. Bulatov, Andrei A. Krokhin, Peter Jeavons: The complexity of maximal constraint languages. STOC 2001: 667-674
3		Andrei A. Krokhin, Peter Jeavons, Peter Jonsson: The complexity of constraints on intervals and lengths Electronic Colloquium on Computational Complexity (ECCC)(077): (2001)
2		Andrei A. Krokhin: Congruences of Clone Lattices, II. Order 18(2): 151-159 (2001)
	2000
1		Andrei A. Bulatov, Andrei A. Krokhin, Peter Jeavons: Constraint Satisfaction Problems and Finite Algebras. ICALP 2000: 272-282

Coauthor Index

1	Ferdinand Börner	[13] [43]
2	Andrei A. Bulatov	[1] [4] [11] [13] [22] [41] [43]
3	Catarina Carvalho	[39]
4	Hubie Chen	[43]
5	David A. Cohen	[12] [14] [17] [20] [23] [28]
6	Martin C. Cooper	[12] [14] [17] [20] [23] [28]
7	Nadia Creignou	[33]
8	Víctor Dalmau	[21] [29] [37] [38] [39]
9	Vladimir G. Deineko	[27] [36]
10	Miki Hermann	[33]
11	Peter Jeavons (Peter G. Jeavons)	[1] [3] [4] [5] [7] [8] [11] [12] [13] [14] [16] [17] [20] [22] [23] [28] [43]
12	Peter Jonsson	[3] [5] [6] [7] [8] [9] [15] [16] [18] [19] [25] [27] [30] [31] [32] [35] [36] [42]
13	Mikael Klasson	[18] [25] [27] [36]
14	Fredrik Kuivinen	[31] [32] [42]
15	Benoit Larose	[10] [21] [24] [29] [34] [38] [41]
16	Dániel Marx	[40]
17	Ivo G. Rosenberg	[26]
18	Gernot Salzer	[33]

Colors in the list of coauthors