A. Krokhin

Most-cited papers

A Maximal Tractable Class of Soft Constraints
David A. Cohen, Martin C. Cooper, P. Jeavons, A. Krokhin
2003International Joint Conference on Artificial Intelligence793 citations Open access
Semantic Scholar
Classifying the Complexity of Constraints Using Finite Algebras
A. Bulatov, P. Jeavons, A. Krokhin
2005SIAM journal on computing (Print)613 citations Open access
Semantic Scholar
Algebraic approach to promise constraint satisfaction
L. Barto, Jakub Bulín, A. Krokhin, Jakub Opršal
2018Symposium on the Theory of Computing175 citations Open access
Semantic Scholar
Polymorphisms, and How to Use Them
L. Barto, A. Krokhin, R. Willard
2017The Constraint Satisfaction Problem172 citations
Semantic Scholar
Citation for Published Item: Use Policy Reasoning about Temporal Relations: the Tractable Subalgebras of Allen's Interval Algebra
A. Krokhin, P. Jeavons, A. Krokhin, P. Jeavons +1 more
146 citations
Semantic Scholar
The complexity of soft constraint satisfaction
David A. Cohen, Martin C. Cooper, P. Jeavons, A. Krokhin
2006Artificial Intelligence144 citations Open access
Semantic Scholar
Constraint Satisfaction Problems and Finite Algebras
A. Bulatov, A. Krokhin, P. Jeavons
2000International Colloquium on Automata, Languages and Programming142 citations
Semantic Scholar
The Complexity of General-Valued CSPs
Vladimir Kolmogorov, A. Krokhin, Michal Rolinek
2015IEEE Annual Symposium on Foundations of Computer Science89 citations Open access
Semantic Scholar
Characterizations of several Maltsev conditions
M. Kozik, A. Krokhin, M. Valeriote, R. Willard
201582 citations Open access
Semantic Scholar
The complexity of maximal constraint languages
A. Bulatov, A. Krokhin, P. Jeavons
2001Symposium on the Theory of Computing81 citations Open access
Semantic Scholar
Dualities for Constraint Satisfaction Problems
A. Bulatov, A. Krokhin, B. Larose
2008Complexity of Constraints75 citations Open access
Semantic Scholar
Quantified Constraints: Algorithms and Complexity
F. Börner, A. Bulatov, P. Jeavons, A. Krokhin
2003Annual Conference for Computer Science Logic75 citations
Semantic Scholar
The complexity of constraint satisfaction games and QCSP
F. Börner, A. Bulatov, Hubie Chen, P. Jeavons +1 more
2009Information and Computation59 citations Open access
Semantic Scholar
The complexity of constraint satisfaction : an algebraic approach.
A. Krokhin, A. Bulatov, P. Jeavons
200555 citations Open access
Semantic Scholar
Topology and adjunction in promise constraint satisfaction
A. Krokhin, Jakub Opršal, Marcin Wrochna, Stanislav Živný
2020Electron. Colloquium Comput. Complex.51 citations Open access
Semantic Scholar
The Approximability of Three-valued MAX CSP
Peter Jonsson, Mikael Klasson, A. Krokhin
2004SIAM journal on computing (Print)51 citations Open access
Semantic Scholar
Skew Bisubmodularity and Valued CSPs
A. Huber, A. Krokhin, Robert Powell
2013SIAM journal on computing (Print)50 citations Open access
Semantic Scholar
Robust Satisfiability for CSPs: Hardness and Algorithmic Results
V. Dalmau, A. Krokhin
2013TOCT46 citations Open access
Semantic Scholar
The approximability of MAX CSP with fixed-value constraints
V. Deineko, Peter Jonsson, Mikael Klasson, A. Krokhin
2006JACM41 citations Open access
Semantic Scholar
The Complexity of Valued Constraint Satisfaction
P. Jeavons, A. Krokhin, Stanislav Živný
2014Bull. EATCS40 citations
Semantic Scholar
Majority constraints have bounded pathwidth duality
V. Dalmau, A. Krokhin
2008European journal of combinatorics (Print)38 citations Open access
Semantic Scholar
Supermodular functions and the complexity of MAX CSP
David A. Cohen, Martin C. Cooper, P. Jeavons, A. Krokhin
2005Discrete Applied Mathematics37 citations Open access
Semantic Scholar
Maximizing Supermodular Functions on Product Lattices, with Application to Maximum Constraint Satisfaction
A. Krokhin, B. Larose
2008SIAM Journal on Discrete Mathematics36 citations Open access
Semantic Scholar
Retractions to Pseudoforests
T. Feder, P. Hell, Peter Jonsson, A. Krokhin +1 more
2010SIAM Journal on Discrete Mathematics31 citations Open access
Semantic Scholar
An invitation to the promise constraint satisfaction problem
A. Krokhin, Jakub Opršal
2022ACM SIGLOG News30 citations Open access
Semantic Scholar
The Constraint Satisfaction Problem: Complexity and Approximability
A. Fraser, A. Krokhin
2017The Constraint Satisfaction Problem29 citations
Semantic Scholar
Constraint Satisfaction Problems on Intervals and Length
A. Krokhin, P. Jeavons, Peter Jonsson
2004SIAM Journal on Discrete Mathematics29 citations Open access
Semantic Scholar
The Complexity of the List Homomorphism Problem for Graphs
László Egri, A. Krokhin, B. Larose, Pascal Tesson
2009Theory of Computing Systems26 citations
Semantic Scholar
The Complexity of 3-Colouring H-Colourable Graphs
A. Krokhin, Jakub Opršal
2019IEEE Annual Symposium on Foundations of Computer Science23 citations Open access
Semantic Scholar
The Complexity of Valued CSPs ∗
A. Krokhin, Stanislav Živný
201723 citations
Semantic Scholar
On the hardness of losing weight
A. Krokhin, Dániel Marx
2008TALG23 citations
Semantic Scholar
Soft Constraints: Complexity and Multimorphisms
David A. Cohen, Martin C. Cooper, P. Jeavons, A. Krokhin
2003International Conference on Principles and Practice of Constraint Programming20 citations Open access
Semantic Scholar
Hard constraint satisfaction problems have hard gaps at location 1
Peter Jonsson, A. Krokhin, Fredrik Kuivinen
2007Theoretical Computer Science19 citations Open access
Semantic Scholar
Complexity classification in qualitative temporal constraint reasoning
Peter Jonsson, A. Krokhin
2004Artificial Intelligence19 citations Open access
Semantic Scholar
Recognizing frozen variables in constraint satisfaction problems
Peter Jonsson, A. Krokhin
2004Theoretical Computer Science18 citations Open access
Semantic Scholar
Citation for Published Item: Use Policy First-order Definable Retraction Problems for Posets and Reflexive Graphs *
V. Dalmau, Krokhin, A. Larose, V. Dalmau +2 more
18 citations
Semantic Scholar
Robust algorithms with polynomial loss for near-unanimity CSPs
V. Dalmau, M. Kozik, A. Krokhin, K. Makarychev +2 more
2016ACM-SIAM Symposium on Discrete Algorithms17 citations Open access
Semantic Scholar
CSP duality and trees of bounded pathwidth
C. Carvalho, V. Dalmau, A. Krokhin
2010Theoretical Computer Science16 citations Open access
Semantic Scholar
Towards a Characterization of Constant-Factor Approximable Finite-Valued CSPs
V. Dalmau, A. Krokhin, Rajsekar Manokaran
2016Journal of computer and system sciences (Print)15 citations Open access
Semantic Scholar
Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey
A. Krokhin, A. Bulatov, P. Jeavons
200333rd International Symposium on Multiple-Valued Logic, 2003. Proceedings.14 citations Open access
Semantic Scholar
On the structure of the lattice of closed classes of polynomials
A. Krokhin, K. Safin, E. Sukhanov
199714 citations
Semantic Scholar
Monoid intervals in lattices of clones
A. Krokhin
199514 citations
Semantic Scholar
Maximum H-colourable subdigraphs and constraint optimization with arbitrary weights
Peter Jonsson, A. Krokhin
2007Journal of computer and system sciences (Print)13 citations Open access
Semantic Scholar
A Complete Classification of Complexity in Allens Algebra in the Presence of a Non-Trivial Basic Relation
A. Krokhin, P. Jeavons, Peter Jonsson
2001International Joint Conference on Artificial Intelligence13 citations
Semantic Scholar
Complexity of Clausal Constraints Over Chains
N. Creignou, M. Hermann, A. Krokhin, G. Salzer
2008Theory of Computing Systems12 citations Open access
Semantic Scholar
Maximum Constraint Satisfaction on Diamonds
A. Krokhin, B. Larose
2005International Conference on Principles and Practice of Constraint Programming12 citations Open access
Semantic Scholar
Two new homomorphism dualities and lattice operations
C. Carvalho, V. Dalmau, A. Krokhin
2011Journal of Logic and Computation11 citations Open access
Semantic Scholar
Citation for Published Item: Use Policy Caterpillar Duality for Constraint Satisfaction Problems
C. Carvalho, V. Dalmau, Krokhin, C. Carvalho +2 more
11 citations
Semantic Scholar
On algebras with many symmetric operations
C. Carvalho, A. Krokhin
2014International journal of algebra and computation10 citations Open access
Semantic Scholar
Oracle Tractability of Skew Bisubmodular Functions
A. Huber, A. Krokhin
2013SIAM Journal on Discrete Mathematics10 citations Open access
Semantic Scholar