Andrei A. Krokhin

2008
41	EE	Andrei A. Bulatov, Andrei A. Krokhin, Benoit Larose: Dualities for Constraint Satisfaction Problems. Complexity of Constraints 2008: 93-124
40	EE	Andrei A. Krokhin, Dániel Marx: On the Hardness of Losing Weight. ICALP (1) 2008: 662-673
39	EE	Catarina Carvalho, Víctor Dalmau, Andrei A. Krokhin: Caterpillar Duality for Constraint Satisfaction Problems. LICS 2008: 307-316
38	EE	Víctor Dalmau, Andrei A. Krokhin, Benoit Larose: Retractions onto series-parallel posets. Discrete Mathematics 308(11): 2104-2114 (2008)
37	EE	Víctor Dalmau, Andrei A. Krokhin: Majority constraints have bounded pathwidth duality. Eur. J. Comb. 29(4): 821-837 (2008)
36	EE	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	EE	Peter Jonsson, Andrei A. Krokhin: Computational complexity of auditing finite attributes in statistical databases. J. Comput. Syst. Sci. 74(5): 898-909 (2008)
34	EE	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	EE	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	EE	Peter Jonsson, Andrei A. Krokhin, Fredrik Kuivinen: Ruling Out Polynomial-Time Approximation Schemes for Hard Constraint Satisfaction Problems. CSR 2007: 182-193
31	EE	Peter Jonsson, Andrei A. Krokhin, Fredrik Kuivinen: Hard constraint satisfaction problems have hard gaps at location 1 CoRR abs/0712.1532: (2007)
30	EE	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	EE	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	EE	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	EE	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	EE	Peter Jonsson, Mikael Klasson, Andrei A. Krokhin: The Approximability of Three-valued MAX CSP. SIAM J. Comput. 35(6): 1329-1349 (2006)
2005
24	EE	Andrei A. Krokhin, Benoit Larose: Maximum Constraint Satisfaction on Diamonds. CP 2005: 388-402
23	EE	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	EE	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	EE	Víctor Dalmau, Andrei A. Krokhin, Benoit Larose: First-Order Definable Retraction Problems for Posets and Reflexive Graph. LICS 2004: 232-241
20	EE	David A. Cohen, Martin C. Cooper, Peter Jeavons, Andrei A. Krokhin: Identifying Efficiently Solvable Cases of Max CSP. STACS 2004: 152-163
19	EE	Peter Jonsson, Andrei A. Krokhin: Complexity classification in qualitative temporal constraint reasoning. Artif. Intell. 160(1-2): 35-51 (2004)
18	EE	Peter Jonsson, Mikael Klasson, Andrei A. Krokhin: The approximability of three-valued MAX CSP CoRR abs/cs/0412042: (2004)
17	EE	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	EE	Andrei A. Krokhin, Peter Jeavons, Peter Jonsson: Constraint Satisfaction Problems on Intervals and Length. SIAM J. Discrete Math. 17(3): 453-477 (2004)
15	EE	Peter Jonsson, Andrei A. Krokhin: Recognizing frozen variables in constraint satisfaction problems. Theor. Comput. Sci. 329(1-3): 93-113 (2004)
2003
14	EE	David A. Cohen, Martin C. Cooper, Peter Jeavons, Andrei A. Krokhin: Soft Constraints: Complexity and Multimorphisms. CP 2003: 244-258
13	EE	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	EE	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	EE	Andrei A. Krokhin, Benoit Larose: Solving Order Constraints in Logarithmic Space. STACS 2003: 379-390
9	EE	Andrei A. Krokhin, Peter Jonsson: Recognizing Frozen Variables in Constraint Satisfaction Problems Electronic Colloquium on Computational Complexity (ECCC)(062): (2003)
8	EE	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	EE	Andrei A. Krokhin, Peter Jeavons, Peter Jonsson: The Complexity of Constraints on Intervals and Lengths. STACS 2002: 443-454
6	EE	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	EE	Andrei A. Bulatov, Andrei A. Krokhin, Peter Jeavons: The complexity of maximal constraint languages. STOC 2001: 667-674
3	EE	Andrei A. Krokhin, Peter Jeavons, Peter Jonsson: The complexity of constraints on intervals and lengths Electronic Colloquium on Computational Complexity (ECCC)(077): (2001)
2	EE	Andrei A. Krokhin: Congruences of Clone Lattices, II. Order 18(2): 151-159 (2001)
2000
1	EE	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]
2	Andrei A. Bulatov	[1] [4] [11] [13] [22] [41]
3	Catarina Carvalho	[39]
4	David A. Cohen	[12] [14] [17] [20] [23] [28]
5	Martin C. Cooper	[12] [14] [17] [20] [23] [28]
6	Nadia Creignou	[33]
7	Víctor Dalmau	[21] [29] [37] [38] [39]
8	Vladimir G. Deineko	[27] [36]
9	Miki Hermann	[33]
10	Peter Jeavons (Peter G. Jeavons)	[1] [3] [4] [5] [7] [8] [11] [12] [13] [14] [16] [17] [20] [22] [23] [28]
11	Peter Jonsson	[3] [5] [6] [7] [8] [9] [15] [16] [18] [19] [25] [27] [30] [31] [32] [35] [36]
12	Mikael Klasson	[18] [25] [27] [36]
13	Fredrik Kuivinen	[31] [32]
14	Benoit Larose	[10] [21] [24] [29] [34] [38] [41]
15	Dániel Marx	[40]
16	Ivo G. Rosenberg	[26]
17	Gernot Salzer	[33]

Colors in the list of coauthors