×

zbMATH — the first resource for mathematics

Krokhin, Andrei A.

Compute Distance To:
Author ID: krokhin.andrei-a Recent zbMATH articles by "Krokhin, Andrei A."
Published as: Krokhin, Andrei; Krokhin, A. A.; Krokhin, Andrei A.; Krokhin, A.
Documents Indexed: 72 Publications since 1995, including 1 Book

Publications by Year

Citations contained in zbMATH Open

51 Publications have been cited 494 times in 265 Documents Cited by Year
Classifying the complexity of constraints using finite algebras. Zbl 1071.08002
Bulatov, Andrei; Jeavons, Peter; Krokhin, Andrei
144
2005
Constraint satisfaction problems and finite algebras. Zbl 0973.68181
Bulatov, Andrei A.; Krokhin, Andrei A.; Jeavons, Peter
26
2000
The complexity of soft constraint satisfaction. Zbl 1131.68520
Cohen, David A.; Cooper, Martin C.; Jeavons, Peter G.; Krokhin, Andrei A.
26
2006
Dualities for constraint satisfaction problems. Zbl 1171.68494
Bulatov, Andrei A.; Krokhin, Andrei; Larose, Benoit
23
2008
Reasoning about temporal relations, the tractable subalgebras of Allen’s interval algebra. Zbl 1325.68220
Krokhin, Andrei; Jeavons, Peter; Jonsson, Peter
20
2003
Characterizations of several Maltsev conditions. Zbl 1319.08002
Kozik, Marcin; Krokhin, Andrei; Valeriote, Matt; Willard, Ross
18
2015
A maximal tractable class of soft constraints. Zbl 1080.68658
Cohen, David; Cooper, Martin; Jeavons, Peter; Krokhin, Andrei
15
2004
The approximability of three-valued MAX CSP. Zbl 1101.68042
Jonsson, Peter; Klasson, Mikael; Krokhin, Andrei
14
2006
The complexity of maximal constraint languages. Zbl 1323.68294
Bulatov, Andrei; Krokhin, Andrei; Jeavons, Peter
13
2001
The complexity of constraint satisfaction games and QCSP. Zbl 1188.68269
Börner, F.; Bulatov, A.; Chen, H.; Jeavons, P.; Krokhin, A.
12
2009
The complexity of constraint satisfaction: an algebraic approach. Zbl 1087.68107
Krokhin, Andrei; Bulatov, Andrei; Jeavons, Peter
12
2005
Skew bisubmodularity and valued CSPs. Zbl 1360.68512
Huber, Anna; Krokhin, Andrei; Powell, Robert
12
2014
Quantified constraints: Algorithms and complexity. Zbl 1116.03314
Börner, Ferdinand; Bulatov, Andrei; Jeavons, Peter; Krokhin, Andrei
10
2003
Retractions to pseudoforests. Zbl 1215.05063
Feder, Tomás; Hell, Pavol; Jonsson, Peter; Krokhin, Andrei; Nordh, Gustav
9
2010
Constraint satisfaction problems on intervals and lengths. Zbl 1101.68043
Krokhin, Andrei; Jeavons, Peter; Jonsson, Peter
9
2004
Supermodular functions and the complexity of MAX CSP. Zbl 1146.68378
Cohen, David; Cooper, Martin; Jeavons, Peter; Krokhin, Andrei
9
2005
Robust satisfiability for CSPs: hardness and algorithmic results. Zbl 1322.68099
Dalmau, Víctor; Krokhin, Andrei
9
2013
The approximability of MAX CSP with fixed-value constraints. Zbl 1325.68105
Deineko, Vladimir; Jonsson, Peter; Klasson, Mikael; Krokhin, Andrei
9
2008
Majority constraints have bounded pathwidth duality. Zbl 1138.68052
Dalmau, Víctor; Krokhin, Andrei
8
2008
The complexity of general-valued CSPs. Zbl 1371.68117
Kolmogorov, Vladimir; Krokhin, Andrei; Rolínek, Michal
8
2017
On the hardness of losing weight. Zbl 1153.68382
Krokhin, Andrei; Marx, Dániel
7
2008
Algebraic approach to promise constraint satisfaction. Zbl 1433.68271
Bulín, Jakub; Krokhin, Andrei; Opršal, Jakub
7
2019
Maximizing supermodular functions on product lattices, with application to maximum constraint satisfaction. Zbl 1167.90017
Krokhin, Andrei; Larose, Benoit
6
2008
Complexity of clausal constraints over chains. Zbl 1141.68034
Creignou, Nadia; Hermann, Miki; Krokhin, Andrei; Salzer, Gernot
5
2008
Towards a characterization of constant-factor approximable min CSPs. Zbl 1371.90116
Dalmau, Víctor; Krokhin, Andrei; Manokaran, Rajsekar
5
2015
First-order definable retraction problems for posets and reflexive graphs. Zbl 1129.03017
Dalmau, Víctor; Krokhin, Andrei; Larose, Benoit
5
2007
Hard constraint satisfaction problems have hard gaps at location 1. Zbl 1176.90498
Jonsson, Peter; Krokhin, Andrei; Kuivinen, Fredrik
4
2009
On the structure of the lattice of closed classes of polynomials. Zbl 0885.03023
Krokhin, A. A.; Safin, K. L.; Sukhanov, E. V.
4
1997
On the hardness of losing weight. Zbl 1295.68123
Krokhin, Andrei; Marx, Dániel
4
2012
The complexity of the list homomorphism problem for graphs. Zbl 1322.68100
Egri, László; Krokhin, Andrei; Larose, Benoit; Tesson, Pascal
4
2012
Maximum constraint satisfaction on diamonds. Zbl 1153.68469
Krokhin, Andrei; Larose, Benoit
3
2005
Two new homomorphism dualities and lattice operations. Zbl 1231.68121
Carvalho, Catarina; Dalmau, Víctor; Krokhin, Andrei
3
2011
Ruling out polynomial-time approximation schemes for hard constraint satisfaction problems. Zbl 1188.68153
Jonsson, Peter; Krokhin, Andrei; Kuivinen, Fredrik
3
2007
Soft constraints: complexity and multimorphisms. Zbl 1273.68342
Cohen, David A.; Cooper, Martin; Jeavons, Peter; Krokhin, Andrei
2
2003
Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights. Zbl 1115.68143
Jonsson, Peter; Krokhin, Andrei
2
2007
Supermodularity on chains and complexity of maximum constraint satisfaction. Zbl 1192.68352
Deineko, Vladimir; Jonsson, Peter; Klasson, Mikael; Krokhin, Andrei
2
2005
CSP duality and trees of bounded pathwidth. Zbl 1196.68167
Carvalho, Catarina; Dalmau, Víctor; Krokhin, Andrei
2
2010
Monoid intervals in lattices of clones. Zbl 0848.08002
Krokhin, A. A.
2
1995
On clones, transformation monoids, and associative rings. Zbl 0903.08002
Krokhin, A. A.
2
1997
Recognizing frozen variables in constraint satisfaction problems. Zbl 1086.68056
Jonsson, Peter; Krokhin, Andrei
2
2004
A monoideal of isotone clones on a finite chain. Zbl 1006.08002
Krokhin, Andrei; Larose, Benoit
2
2002
Oracle tractability of skew bisubmodular functions. Zbl 1309.68095
Huber, Anna; Krokhin, Andrei
2
2014
The complexity of the list homomorphism problem for graphs. Zbl 1230.68106
Egri, László; Krokhin, Andrei; Larose, Benoit; Tesson, Pascal
2
2010
Tree dualities for constraint satisfaction. Zbl 1287.68156
Krokhin, Andrei
1
2010
The complexity of valued constraint satisfaction. Zbl 1409.68141
Jeavons, Peter; Krokhin, Andrei; Živný, Stanislav
1
2014
Boolean lattices as intervals in clone lattices. Zbl 0881.08001
Krokhin, A. A.
1
1997
On the structure of clone lattices. Zbl 0824.08004
Bulatov, A.; Krokhin, A.; Safin, K.; Sukhanov, E.
1
1995
Solving order constraints in logarithmic space. Zbl 1035.68111
Krokhin, Andrei; Larose, Benoit
1
2003
Robust algorithms with polynomial loss for near-unanimity CSPs. Zbl 1410.68162
Dalmau, Víctor; Kozik, Marcin; Krokhin, Andrei; Makarychev, Konstantin; Makarychev, Yury; Opršal, Jakub
1
2017
On algebras with many symmetric operations. Zbl 1352.08002
Carvalho, Catarina; Krokhin, Andrei
1
2016
Retractions onto series-parallel posets. Zbl 1141.06001
Dalmau, Víctor; Krokhin, Andrei; Larose, Benoit
1
2008
Algebraic approach to promise constraint satisfaction. Zbl 1433.68271
Bulín, Jakub; Krokhin, Andrei; Opršal, Jakub
7
2019
The complexity of general-valued CSPs. Zbl 1371.68117
Kolmogorov, Vladimir; Krokhin, Andrei; Rolínek, Michal
8
2017
Robust algorithms with polynomial loss for near-unanimity CSPs. Zbl 1410.68162
Dalmau, Víctor; Kozik, Marcin; Krokhin, Andrei; Makarychev, Konstantin; Makarychev, Yury; Opršal, Jakub
1
2017
On algebras with many symmetric operations. Zbl 1352.08002
Carvalho, Catarina; Krokhin, Andrei
1
2016
Characterizations of several Maltsev conditions. Zbl 1319.08002
Kozik, Marcin; Krokhin, Andrei; Valeriote, Matt; Willard, Ross
18
2015
Towards a characterization of constant-factor approximable min CSPs. Zbl 1371.90116
Dalmau, Víctor; Krokhin, Andrei; Manokaran, Rajsekar
5
2015
Skew bisubmodularity and valued CSPs. Zbl 1360.68512
Huber, Anna; Krokhin, Andrei; Powell, Robert
12
2014
Oracle tractability of skew bisubmodular functions. Zbl 1309.68095
Huber, Anna; Krokhin, Andrei
2
2014
The complexity of valued constraint satisfaction. Zbl 1409.68141
Jeavons, Peter; Krokhin, Andrei; Živný, Stanislav
1
2014
Robust satisfiability for CSPs: hardness and algorithmic results. Zbl 1322.68099
Dalmau, Víctor; Krokhin, Andrei
9
2013
On the hardness of losing weight. Zbl 1295.68123
Krokhin, Andrei; Marx, Dániel
4
2012
The complexity of the list homomorphism problem for graphs. Zbl 1322.68100
Egri, László; Krokhin, Andrei; Larose, Benoit; Tesson, Pascal
4
2012
Two new homomorphism dualities and lattice operations. Zbl 1231.68121
Carvalho, Catarina; Dalmau, Víctor; Krokhin, Andrei
3
2011
Retractions to pseudoforests. Zbl 1215.05063
Feder, Tomás; Hell, Pavol; Jonsson, Peter; Krokhin, Andrei; Nordh, Gustav
9
2010
CSP duality and trees of bounded pathwidth. Zbl 1196.68167
Carvalho, Catarina; Dalmau, Víctor; Krokhin, Andrei
2
2010
The complexity of the list homomorphism problem for graphs. Zbl 1230.68106
Egri, László; Krokhin, Andrei; Larose, Benoit; Tesson, Pascal
2
2010
Tree dualities for constraint satisfaction. Zbl 1287.68156
Krokhin, Andrei
1
2010
The complexity of constraint satisfaction games and QCSP. Zbl 1188.68269
Börner, F.; Bulatov, A.; Chen, H.; Jeavons, P.; Krokhin, A.
12
2009
Hard constraint satisfaction problems have hard gaps at location 1. Zbl 1176.90498
Jonsson, Peter; Krokhin, Andrei; Kuivinen, Fredrik
4
2009
Dualities for constraint satisfaction problems. Zbl 1171.68494
Bulatov, Andrei A.; Krokhin, Andrei; Larose, Benoit
23
2008
The approximability of MAX CSP with fixed-value constraints. Zbl 1325.68105
Deineko, Vladimir; Jonsson, Peter; Klasson, Mikael; Krokhin, Andrei
9
2008
Majority constraints have bounded pathwidth duality. Zbl 1138.68052
Dalmau, Víctor; Krokhin, Andrei
8
2008
On the hardness of losing weight. Zbl 1153.68382
Krokhin, Andrei; Marx, Dániel
7
2008
Maximizing supermodular functions on product lattices, with application to maximum constraint satisfaction. Zbl 1167.90017
Krokhin, Andrei; Larose, Benoit
6
2008
Complexity of clausal constraints over chains. Zbl 1141.68034
Creignou, Nadia; Hermann, Miki; Krokhin, Andrei; Salzer, Gernot
5
2008
Retractions onto series-parallel posets. Zbl 1141.06001
Dalmau, Víctor; Krokhin, Andrei; Larose, Benoit
1
2008
First-order definable retraction problems for posets and reflexive graphs. Zbl 1129.03017
Dalmau, Víctor; Krokhin, Andrei; Larose, Benoit
5
2007
Ruling out polynomial-time approximation schemes for hard constraint satisfaction problems. Zbl 1188.68153
Jonsson, Peter; Krokhin, Andrei; Kuivinen, Fredrik
3
2007
Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights. Zbl 1115.68143
Jonsson, Peter; Krokhin, Andrei
2
2007
The complexity of soft constraint satisfaction. Zbl 1131.68520
Cohen, David A.; Cooper, Martin C.; Jeavons, Peter G.; Krokhin, Andrei A.
26
2006
The approximability of three-valued MAX CSP. Zbl 1101.68042
Jonsson, Peter; Klasson, Mikael; Krokhin, Andrei
14
2006
Classifying the complexity of constraints using finite algebras. Zbl 1071.08002
Bulatov, Andrei; Jeavons, Peter; Krokhin, Andrei
144
2005
The complexity of constraint satisfaction: an algebraic approach. Zbl 1087.68107
Krokhin, Andrei; Bulatov, Andrei; Jeavons, Peter
12
2005
Supermodular functions and the complexity of MAX CSP. Zbl 1146.68378
Cohen, David; Cooper, Martin; Jeavons, Peter; Krokhin, Andrei
9
2005
Maximum constraint satisfaction on diamonds. Zbl 1153.68469
Krokhin, Andrei; Larose, Benoit
3
2005
Supermodularity on chains and complexity of maximum constraint satisfaction. Zbl 1192.68352
Deineko, Vladimir; Jonsson, Peter; Klasson, Mikael; Krokhin, Andrei
2
2005
A maximal tractable class of soft constraints. Zbl 1080.68658
Cohen, David; Cooper, Martin; Jeavons, Peter; Krokhin, Andrei
15
2004
Constraint satisfaction problems on intervals and lengths. Zbl 1101.68043
Krokhin, Andrei; Jeavons, Peter; Jonsson, Peter
9
2004
Recognizing frozen variables in constraint satisfaction problems. Zbl 1086.68056
Jonsson, Peter; Krokhin, Andrei
2
2004
Reasoning about temporal relations, the tractable subalgebras of Allen’s interval algebra. Zbl 1325.68220
Krokhin, Andrei; Jeavons, Peter; Jonsson, Peter
20
2003
Quantified constraints: Algorithms and complexity. Zbl 1116.03314
Börner, Ferdinand; Bulatov, Andrei; Jeavons, Peter; Krokhin, Andrei
10
2003
Soft constraints: complexity and multimorphisms. Zbl 1273.68342
Cohen, David A.; Cooper, Martin; Jeavons, Peter; Krokhin, Andrei
2
2003
Solving order constraints in logarithmic space. Zbl 1035.68111
Krokhin, Andrei; Larose, Benoit
1
2003
A monoideal of isotone clones on a finite chain. Zbl 1006.08002
Krokhin, Andrei; Larose, Benoit
2
2002
The complexity of maximal constraint languages. Zbl 1323.68294
Bulatov, Andrei; Krokhin, Andrei; Jeavons, Peter
13
2001
Constraint satisfaction problems and finite algebras. Zbl 0973.68181
Bulatov, Andrei A.; Krokhin, Andrei A.; Jeavons, Peter
26
2000
On the structure of the lattice of closed classes of polynomials. Zbl 0885.03023
Krokhin, A. A.; Safin, K. L.; Sukhanov, E. V.
4
1997
On clones, transformation monoids, and associative rings. Zbl 0903.08002
Krokhin, A. A.
2
1997
Boolean lattices as intervals in clone lattices. Zbl 0881.08001
Krokhin, A. A.
1
1997
Monoid intervals in lattices of clones. Zbl 0848.08002
Krokhin, A. A.
2
1995
On the structure of clone lattices. Zbl 0824.08004
Bulatov, A.; Krokhin, A.; Safin, K.; Sukhanov, E.
1
1995
all top 5

Cited by 280 Authors

22 Živný, Stanislav
19 Jonsson, Peter A.
18 Krokhin, Andrei A.
17 Bodirsky, Manuel
16 Martin, Barnaby D.
15 Bulatov, Andrei A.
14 Chen, Hubie
13 Cooper, Martin C.
12 Jeavons, Peter G.
11 Cohen, David A.
11 Dalmau, Víctor
10 Barto, Libor
9 Larose, Benoit
9 Pinsker, Michael
8 Thapper, Johan
7 Hell, Pavol
7 Kozik, Marcin
7 Valeriote, Matthew A.
6 Marx, Dániel
5 Bova, Simone
5 Gutin, Gregory Z.
5 Marković, Petar
5 McKenzie, Ralph N.
5 Paulusma, Daniël
5 Siggers, Mark H.
4 Creignou, Nadia
4 Golovach, Petr A.
4 Guruswami, Venkatesan
4 Lagerkvist, Victor
4 Mottet, Antoine
4 Nešetřil, Jaroslav
4 Niven, Todd
4 Nordh, Gustav
4 Pongrácz, András
4 Rafiey, Arash
4 Selezneva, Svetlana Nikolaevna
4 Szeider, Stefan
4 Willard, Ross
4 Yeo, Anders
3 Bulín, Jakub
3 Carvalho, Catarina A.
3 Egri, László
3 Fulla, Peter
3 Jackson, Marcel G.
3 Kára, Jan
3 Kazda, Alexandr
3 Kolmogorov, Vladimir
3 Li, Sanjiang
3 Liu, Weiming
3 Madelaine, Florent R.
3 Meshchaninov, Dmitry G.
3 Opršal, Jakub
3 Rautenbach, Dieter
3 Schäfer, Philipp Matthias
3 Tardif, Claude
3 Vargas, Edith Mireya
3 Wires, Alexander
3 Wrona, Michał
3 Zádori, László
3 Zhuk, Dmitriy N.
2 Atserias, Albert
2 Behrisch, Mike
2 Börner, Ferdinand
2 Carbonnel, Clément
2 Fernandes dos Santos, Vinícius
2 Fomin, Fedor V.
2 Freese, Ralph S.
2 Fujishige, Satoru
2 Glaßer, Christian
2 Goldberg, Leslie Ann
2 Grohe, Martin
2 Guo, Jiong
2 Ham, Lucy
2 Kim, V. I.
2 Kozhukhov, Igor’ Borisovich
2 Kuivinen, Fredrik
2 Lutz, Carsten
2 Mamino, Marcello
2 Maróti, Miklós
2 Naanaa, Wady
2 Nataraj, Paluri S. V.
2 Nightingale, Peter W.
2 Olšák, Miroslav
2 Patil, Mukesh D.
2 Schlotter, Ildikó
2 Song, Jian
2 Stronkowski, Michał Marek
2 Szwarcfiter, Jayme Luiz
2 Tanigawa, Shin-ichi
2 Tesson, Pascal
2 Villanger, Yngve
2 Vollmer, Heribert
2 Yoshida, Yuichi
2 Zanuttini, Bruno
1 Austrin, Per
1 Bauland, Michael
1 Bergman, Clifford
1 Berman, Joel D.
1 Bistarelli, Stefano
1 Böhler, Elmar
...and 180 more Authors
all top 5

Cited in 56 Serials

23 Algebra Universalis
21 Theoretical Computer Science
18 Artificial Intelligence
15 Journal of Computer and System Sciences
11 European Journal of Combinatorics
10 SIAM Journal on Computing
10 Theory of Computing Systems
9 SIAM Journal on Discrete Mathematics
8 Discrete Applied Mathematics
8 International Journal of Algebra and Computation
8 Constraints
6 Algorithmica
6 Information and Computation
5 Discrete Mathematics
5 Logical Methods in Computer Science
4 Transactions of the American Mathematical Society
4 Discrete Mathematics and Applications
4 Discrete Optimization
3 Information Processing Letters
3 Semigroup Forum
3 Order
3 Annals of Mathematics and Artificial Intelligence
2 Computers & Mathematics with Applications
2 Journal of Combinatorial Theory. Series B
2 Moscow University Computational Mathematics and Cybernetics
2 Mathematical Programming. Series A. Series B
2 Journal of Mathematical Sciences (New York)
2 Journal of the ACM
2 ACM Transactions on Computational Logic
1 Acta Informatica
1 Israel Journal of Mathematics
1 Advances in Mathematics
1 Bulletin of the London Mathematical Society
1 Commentationes Mathematicae Universitatis Carolinae
1 Demonstratio Mathematica
1 Journal of Algebra
1 Proceedings of the American Mathematical Society
1 Siberian Mathematical Journal
1 Combinatorica
1 Computers & Operations Research
1 Mathematical and Computer Modelling
1 JETAI. Journal of Experimental & Theoretical Artificial Intelligence
1 International Journal of Foundations of Computer Science
1 Computational Complexity
1 Journal of Computer and Systems Sciences International
1 The Bulletin of Symbolic Logic
1 Nonlinear Dynamics
1 Journal of Combinatorial Optimization
1 Theory and Practice of Logic Programming
1 Journal of Machine Learning Research (JMLR)
1 Journal of Multiple-Valued Logic and Soft Computing
1 Journal of Discrete Algorithms
1 Journal of Control Theory and Applications
1 Chebyshevskiĭ Sbornik
1 Diskretnyĭ Analiz i Issledovanie Operatsiĭ
1 Computer Science Review

Citations by Year