Andrei A. Krokhin

Publication Activity (10 Years)

Years Active: 2000-2024
Publications (10 Years): 31

Top Topics

Constraint Propagation

Tractable Subclasses

Constraint Satisfaction

Top Venues

SIAM J. Comput.

SIAM J. Discret. Math.

Electron. Colloquium Comput. Complex.

Publications

Víctor Dalmau, Andrei A. Krokhin, Jakub Oprsal
Functors on Relational Structures Which Admit Both Left and Right Adjoints. SIAM J. Discret. Math. 38 (3) (2024)
Lorenzo Ciardo, Marcin Kozik, Andrei A. Krokhin, Tamio-Vesa Nakajima, Stanislav Zivný
1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise. LICS (2024)
Víctor Dalmau, Andrei A. Krokhin, Jakub Oprsal
Functors on relational structures which admit both left and right adjoints. CoRR (2023)
Andrei A. Krokhin, Jakub Oprsal, Marcin Wrochna, Stanislav Zivný
Topology and Adjunction in Promise Constraint Satisfaction. SIAM J. Comput. 52 (1) (2023)
Lorenzo Ciardo, Marcin Kozik, Andrei A. Krokhin, Tamio-Vesa Nakajima, Stanislav Zivný
On the complexity of the approximate hypergraph homomorphism problem. CoRR (2023)
Andrei A. Krokhin, Jakub Oprsal
An Invitation to the Promise Constraint Satisfaction Problem. Electron. Colloquium Comput. Complex. (2022)
Andrei A. Krokhin, Jakub Oprsal
An invitation to the promise constraint satisfaction problem. CoRR (2022)
Andrei A. Krokhin, Jakub Oprsal
An invitation to the promise constraint satisfaction problem. ACM SIGLOG News 9 (3) (2022)
Libor Barto, Jakub Bulín, Andrei A. Krokhin, Jakub Oprsal
Algebraic Approach to Promise Constraint Satisfaction. J. ACM 68 (4) (2021)
Andrei A. Krokhin, Jakub Oprsal, Marcin Wrochna, Stanislav Zivný
Topology and adjunction in promise constraint satisfaction. Electron. Colloquium Comput. Complex. 27 (2020)
Andrei A. Krokhin, Jakub Oprsal, Marcin Wrochna, Stanislav Zivný
Topology and adjunction in promise constraint satisfaction. CoRR (2020)
Jakub Bulín, Andrei A. Krokhin, Jakub Oprsal
Algebraic approach to promise constraint satisfaction. STOC (2019)
Andrei A. Krokhin, Jakub Oprsal
The Complexity of 3-Colouring H-Colourable Graphs. FOCS (2019)
Andrei A. Krokhin, Jakub Oprsal
The complexity of 3-colouring H-colourable graphs. CoRR (2019)
Víctor Dalmau, Marcin Kozik, Andrei A. Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal
Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs. SIAM J. Comput. 48 (6) (2019)
Andrei A. Krokhin, Jakub Oprsal
The complexity of 3-colouring $H$-colourable graphs. Electron. Colloquium Comput. Complex. 26 (2019)
Víctor Dalmau, Andrei A. Krokhin, Rajsekar Manokaran
Towards a characterization of constant-factor approximable finite-valued CSPs. J. Comput. Syst. Sci. 97 (2018)
Jakub Bulín, Andrei A. Krokhin, Jakub Oprsal
Algebraic approach to promise constraint satisfaction. CoRR (2018)
Vladimir Kolmogorov, Andrei A. Krokhin, Michal Rolínek
The Complexity of General-Valued CSPs. SIAM J. Comput. 46 (3) (2017)
David A. Cohen, Martin C. Cooper, Peter G. Jeavons, Andrei A. Krokhin, Robert Powell, Stanislav Zivný
Binarisation for Valued Constraint Satisfaction Problems. SIAM J. Discret. Math. 31 (4) (2017)
Andrei A. Krokhin, Dániel Marx
On the hardness of losing weight. CoRR (2017)
Víctor Dalmau, Marcin Kozik, Andrei A. Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal
Robust algorithms with polynomial loss for near-unanimity CSPs. SODA (2017)
Víctor Dalmau, Andrei A. Krokhin, Rajsekar Manokaran
Towards a Characterization of Constant-Factor Approximable Finite-Valued CSPs. CoRR (2016)
Víctor Dalmau, Marcin Kozik, Andrei A. Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal
Robust algorithms with polynomial loss for near-unanimity CSPs. CoRR (2016)
Catarina Carvalho, Andrei A. Krokhin
On algebras with many symmetric operations. Int. J. Algebra Comput. 26 (5) (2016)
David A. Cohen, Martin C. Cooper, Peter G. Jeavons, Andrei A. Krokhin, Robert Powell, Stanislav Zivný
Binarisation for Valued Constraint Satisfaction Problems. CoRR (2016)
Andrei A. Bulatov, Venkatesan Guruswami, Andrei A. Krokhin, Dániel Marx
The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 15301). Dagstuhl Reports 5 (7) (2015)
Vladimir Kolmogorov, Andrei A. Krokhin, Michal Rolinek
The Complexity of General-Valued CSPs. FOCS (2015)
Robert Powell, Andrei A. Krokhin
A Reduction from Valued CSP to Min Cost Homomorphism Problem for Digraphs. CoRR (2015)
Vladimir Kolmogorov, Andrei A. Krokhin, Michal Rolinek
The Complexity of General-Valued CSPs. CoRR (2015)
Víctor Dalmau, Andrei A. Krokhin, Rajsekar Manokaran
Towards a Characterization of Constant-Factor Approximable Min CSPs. SODA (2015)
Peter Jeavons, Andrei A. Krokhin, Stanislav Zivný
The Complexity of Valued Constraint Satisfaction. Bull. EATCS 113 (2014)
Anna Huber, Andrei A. Krokhin, Robert Powell
Skew Bisubmodularity and Valued CSPs. SIAM J. Comput. 43 (3) (2014)
Anna Huber, Andrei A. Krokhin
Oracle Tractability of Skew Bisubmodular Functions. SIAM J. Discret. Math. 28 (4) (2014)
Anna Huber, Andrei A. Krokhin, Robert Powell
Skew Bisubmodularity and Valued CSPs. SODA (2013)
Anna Huber, Andrei A. Krokhin
Oracle Tractability of Skew Bisubmodular Functions. CoRR (2013)
Víctor Dalmau, Andrei A. Krokhin
Robust Satisfiability for CSPs: Hardness and Algorithmic Results. ACM Trans. Comput. Theory 5 (4) (2013)
László Egri, Andrei A. Krokhin, Benoît Larose, Pascal Tesson
The Complexity of the List Homomorphism Problem for Graphs. Theory Comput. Syst. 51 (2) (2012)
Johan Håstad, Andrei A. Krokhin, Dániel Marx
The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 12451). Dagstuhl Reports 2 (11) (2012)
Andrei A. Krokhin, Dániel Marx
On the hardness of losing weight. ACM Trans. Algorithms 8 (2) (2012)
Andrei A. Krokhin
The Complexity of Evaluating First-Order Sentences over a Fixed Structure. LICS (2011)
David A. Cohen, Martin C. Cooper, Peter Jeavons, Andrei A. Krokhin
A Maximal Tractable Class of Soft Constraints CoRR (2011)
Catarina Carvalho, Víctor Dalmau, Andrei A. Krokhin
Two new homomorphism dualities and lattice operations. J. Log. Comput. 21 (6) (2011)
László Egri, Andrei A. Krokhin, Benoît Larose, Pascal Tesson
The Complexity of the List Homomorphism Problem for Graphs. STACS (2010)
Tomás Feder, Pavol Hell, Peter Jonsson, Andrei A. Krokhin, Gustav Nordh
Retractions to Pseudoforests. SIAM J. Discret. Math. 24 (1) (2010)
Catarina Carvalho, Víctor Dalmau, Andrei A. Krokhin
CSP duality and trees of bounded pathwidth. Theor. Comput. Sci. 411 (34-36) (2010)
Andrei A. Krokhin
Tree Dualities for Constraint Satisfaction. CSL (2010)
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) (2009)
Andrei A. Bulatov, Martin Grohe, Phokion G. Kolaitis, Andrei A. Krokhin
09441 Abstracts Collection - The Constraint Satisfaction Problem: Complexity and Approximability. The Constraint Satisfaction Problem: Complexity and Approximability (2009)
Peter Jonsson, Andrei A. Krokhin, Fredrik Kuivinen
Hard constraint satisfaction problems have hard gaps at location 1. Theor. Comput. Sci. 410 (38-40) (2009)
Andrei A. Bulatov, Martin Grohe, Phokion G. Kolaitis, Andrei A. Krokhin
09441 Executive Summary - The Constraint Satisfaction Problem: Complexity and Approximability. The Constraint Satisfaction Problem: Complexity and Approximability (2009)
László Egri, Andrei A. Krokhin, Benoît Larose, Pascal Tesson
The complexity of the list homomorphism problem for graphs CoRR (2009)
Nadia Creignou, Miki Hermann, Andrei A. Krokhin, Gernot Salzer
Complexity of Clausal Constraints Over Chains. Theory Comput. Syst. 42 (2) (2008)
Andrei A. Bulatov, Andrei A. Krokhin, Benoît Larose
Dualities for Constraint Satisfaction Problems. Complexity of Constraints (2008)
Andrei A. Krokhin, Benoît Larose
Maximizing Supermodular Functions on Product Lattices, with Application to Maximum Constraint Satisfaction. SIAM J. Discret. Math. 22 (1) (2008)
Víctor Dalmau, Andrei A. Krokhin, Benoît Larose
Retractions onto series-parallel posets. Discret. Math. 308 (11) (2008)
Catarina Carvalho, Víctor Dalmau, Andrei A. Krokhin
Caterpillar Duality for Constraint Satisfaction Problems. LICS (2008)
Vladimir G. Deineko, Peter Jonsson, Mikael Klasson, Andrei A. Krokhin
The approximability of MAX CSP with fixed-value constraints. J. ACM 55 (4) (2008)
Andrei A. Krokhin, Dániel Marx
On the Hardness of Losing Weight. ICALP (1) (2008)
Víctor Dalmau, Andrei A. Krokhin
Majority constraints have bounded pathwidth duality. Eur. J. Comb. 29 (4) (2008)
Peter Jonsson, Andrei A. Krokhin
Computational complexity of auditing finite attributes in statistical databases. J. Comput. Syst. Sci. 74 (5) (2008)
Peter Jonsson, Andrei A. Krokhin, Fredrik Kuivinen
Hard constraint satisfaction problems have hard gaps at location 1 CoRR (2007)
Víctor Dalmau, Andrei A. Krokhin, Benoît Larose
First-order Definable Retraction Problems for Posets and Reflexive Graphs. J. Log. Comput. 17 (1) (2007)
Peter Jonsson, Andrei A. Krokhin
Maximum H-colourable subdigraphs and constraint optimization with arbitrary weights. J. Comput. Syst. Sci. 73 (5) (2007)
Peter Jonsson, Andrei A. Krokhin, Fredrik Kuivinen
Ruling Out Polynomial-Time Approximation Schemes for Hard Constraint Satisfaction Problems. CSR (2007)
Vladimir G. Deineko, Peter Jonsson, Mikael Klasson, Andrei A. Krokhin
The approximability of MAX CSP with fixed-value constraints CoRR (2006)
Andrei A. Krokhin, Ivo G. Rosenberg
A Monoidal Interval of Clones of Selfdual Functions. J. Autom. Lang. Comb. 11 (2) (2006)
Peter Jonsson, Mikael Klasson, Andrei A. Krokhin
The Approximability of Three-valued MAX CSP. SIAM J. Comput. 35 (6) (2006)
David A. Cohen, Martin C. Cooper, Peter Jeavons, Andrei A. Krokhin
The complexity of soft constraint satisfaction. Artif. Intell. 170 (11) (2006)
Andrei A. Krokhin, Benoît Larose
Maximum Constraint Satisfaction on Diamonds. CP (2005)
David A. Cohen, Martin C. Cooper, Peter Jeavons, Andrei A. Krokhin
Supermodular functions and the complexity of MAX CSP. Discret. Appl. Math. 149 (1-3) (2005)
Andrei A. Bulatov, Peter Jeavons, Andrei A. Krokhin
Classifying the Complexity of Constraints Using Finite Algebras. SIAM J. Comput. 34 (3) (2005)
David A. Cohen, Martin C. Cooper, Peter Jeavons, Andrei A. Krokhin
Identifying Efficiently Solvable Cases of Max CSP. STACS (2004)
David A. Cohen, Martin C. Cooper, Peter Jeavons, Andrei A. Krokhin
A Maximal Tractable Class of Soft Constraints. J. Artif. Intell. Res. 22 (2004)
Peter Jonsson, Andrei A. Krokhin
Recognizing frozen variables in constraint satisfaction problems. Theor. Comput. Sci. 329 (1-3) (2004)
Andrei A. Krokhin, Peter Jeavons, Peter Jonsson
Constraint Satisfaction Problems on Intervals and Length. SIAM J. Discret. Math. 17 (3) (2004)
Víctor Dalmau, Andrei A. Krokhin, Benoît Larose
First-Order Definable Retraction Problems for Posets and Reflexive Graph. LICS (2004)
Peter Jonsson, Mikael Klasson, Andrei A. Krokhin
The approximability of three-valued MAX CSP CoRR (2004)
Peter Jonsson, Andrei A. Krokhin
Complexity classification in qualitative temporal constraint reasoning. Artif. Intell. 160 (1-2) (2004)
Andrei A. Krokhin, Andrei A. Bulatov, Peter Jeavons
Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey. ISMVL (2003)
Andrei A. Krokhin, Benoît Larose
Solving Order Constraints in Logarithmic Space. STACS (2003)
David A. Cohen, Martin C. Cooper, Peter Jeavons, Andrei A. Krokhin
Soft Constraints: Complexity and Multimorphisms. CP (2003)
Andrei A. Krokhin, Peter Jeavons, Peter Jonsson
Reasoning about temporal relations: The tractable subalgebras of Allen's interval algebra. J. ACM 50 (5) (2003)
Ferdinand Börner, Andrei A. Bulatov, Peter Jeavons, Andrei A. Krokhin
Quantified Constraints: Algorithms and Complexity. CSL (2003)
David A. Cohen, Martin C. Cooper, Peter Jeavons, Andrei A. Krokhin
A Maximal Tractable Class of Soft Constraints. IJCAI (2003)
Andrei A. Krokhin, Peter Jonsson
Recognizing Frozen Variables in Constraint Satisfaction Problems Electron. Colloquium Comput. Complex. (062) (2003)
Andrei A. Krokhin, Peter Jeavons, Peter Jonsson
The Complexity of Constraints on Intervals and Lengths. STACS (2002)
Andrei A. Krokhin, Peter Jonsson
Extending the Point Algebra into the Qualitative Algebra. TIME (2002)
Andrei A. Krokhin, Peter Jeavons, Peter Jonsson
The complexity of constraints on intervals and lengths Electron. Colloquium Comput. Complex. (077) (2001)
Andrei A. Bulatov, Andrei A. Krokhin, Peter Jeavons
The complexity of maximal constraint languages. STOC (2001)
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)
Andrei A. Krokhin
Congruences of Clone Lattices, II. Order 18 (2) (2001)
Andrei A. Bulatov, Andrei A. Krokhin, Peter Jeavons
Constraint Satisfaction Problems and Finite Algebras. ICALP (2000)