Andrei A. Krokhin

According to our database, Andrei A. Krokhin authored at least 69 papers between 2000 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

Functors on Relational Structures Which Admit Both Left and Right Adjoints.

Víctor Dalmau, Andrei A. Krokhin, Jakub Oprsal

SIAM J. Discret. Math., 2024

1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise.

Lorenzo Ciardo, Marcin Kozik, Andrei A. Krokhin, Tamio-Vesa Nakajima, Stanislav Zivný

Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science, 2024

2023

Topology and Adjunction in Promise Constraint Satisfaction.

Andrei A. Krokhin, Jakub Oprsal, Marcin Wrochna, Stanislav Zivný

SIAM J. Comput., February, 2023

On the complexity of the approximate hypergraph homomorphism problem.

Lorenzo Ciardo, Marcin Kozik, Andrei A. Krokhin, Tamio-Vesa Nakajima, Stanislav Zivný

CoRR, 2023

2022

An Invitation to the Promise Constraint Satisfaction Problem.

Andrei A. Krokhin, Jakub Oprsal

Electron. Colloquium Comput. Complex., 2022

2021

Algebraic Approach to Promise Constraint Satisfaction.

Libor Barto, Jakub Bulín, Andrei A. Krokhin, Jakub Oprsal

J. ACM, 2021

2019

Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs.

Víctor Dalmau, Marcin Kozik, Andrei A. Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal

SIAM J. Comput., 2019

The complexity of 3-colouring <i>H</i>-colourable graphs.

Andrei A. Krokhin, Jakub Oprsal

Electron. Colloquium Comput. Complex., 2019

Algebraic approach to promise constraint satisfaction.

Jakub Bulín, Andrei A. Krokhin, Jakub Oprsal

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

The Complexity of 3-Colouring H-Colourable Graphs.

Andrei A. Krokhin, Jakub Oprsal

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018

Towards a characterization of constant-factor approximable finite-valued CSPs.

Víctor Dalmau, Andrei A. Krokhin, Rajsekar Manokaran

J. Comput. Syst. Sci., 2018

2017

Binarisation for Valued Constraint Satisfaction Problems.

David A. Cohen, Martin C. Cooper, Peter G. Jeavons, Andrei A. Krokhin, Robert Powell, Stanislav Zivný

SIAM J. Discret. Math., 2017

The Complexity of General-Valued CSPs.

Vladimir Kolmogorov, Andrei A. Krokhin, Michal Rolínek

SIAM J. Comput., 2017

The Complexity of Valued CSPs.

Andrei A. Krokhin, Stanislav Zivný

Proceedings of the Constraint Satisfaction Problem: Complexity and Approximability, 2017

Polymorphisms, and How to Use Them.

Libor Barto, Andrei A. Krokhin, Ross Willard

Proceedings of the Constraint Satisfaction Problem: Complexity and Approximability, 2017

2016

On algebras with many symmetric operations.

Catarina Carvalho, Andrei A. Krokhin

Int. J. Algebra Comput., 2016

2015

The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 15301).

Andrei A. Bulatov, Venkatesan Guruswami, Andrei A. Krokhin, Dániel Marx

Dagstuhl Reports, 2015

A Reduction from Valued CSP to Min Cost Homomorphism Problem for Digraphs.

Robert Powell, Andrei A. Krokhin

CoRR, 2015

Towards a Characterization of Constant-Factor Approximable Min CSPs.

Víctor Dalmau, Andrei A. Krokhin, Rajsekar Manokaran

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

2014

Oracle Tractability of Skew Bisubmodular Functions.

Anna Huber, Andrei A. Krokhin

SIAM J. Discret. Math., 2014

Skew Bisubmodularity and Valued CSPs.

Anna Huber, Andrei A. Krokhin, Robert Powell

SIAM J. Comput., 2014

The Complexity of Valued Constraint Satisfaction.

Peter Jeavons, Andrei A. Krokhin, Stanislav Zivný

Bull. EATCS, 2014

2013

Robust Satisfiability for CSPs: Hardness and Algorithmic Results.

Víctor Dalmau, Andrei A. Krokhin

ACM Trans. Comput. Theory, 2013

2012

On the hardness of losing weight.

Andrei A. Krokhin, Dániel Marx

ACM Trans. Algorithms, 2012

The Complexity of the List Homomorphism Problem for Graphs.

László Egri, Andrei A. Krokhin, Benoît Larose, Pascal Tesson

Theory Comput. Syst., 2012

The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 12451).

Johan Håstad, Andrei A. Krokhin, Dániel Marx

Dagstuhl Reports, 2012

2011

Two new homomorphism dualities and lattice operations.

Catarina Carvalho, Víctor Dalmau, Andrei A. Krokhin

J. Log. Comput., 2011

The Complexity of Evaluating First-Order Sentences over a Fixed Structure.

Andrei A. Krokhin

Proceedings of the 26th Annual IEEE Symposium on Logic in Computer Science, 2011

2010

CSP duality and trees of bounded pathwidth.

Catarina Carvalho, Víctor Dalmau, Andrei A. Krokhin

Theor. Comput. Sci., 2010

Retractions to Pseudoforests.

Tomás Feder, Pavol Hell, Peter Jonsson, Andrei A. Krokhin, Gustav Nordh

SIAM J. Discret. Math., 2010

Tree Dualities for Constraint Satisfaction.

Andrei A. Krokhin

Proceedings of the Computer Science Logic, 24th International Workshop, 2010

2009

Hard constraint satisfaction problems have hard gaps at location 1.

Peter Jonsson, Andrei A. Krokhin, Fredrik Kuivinen

Theor. Comput. Sci., 2009

The complexity of constraint satisfaction games and QCSP.

Ferdinand Börner, Andrei A. Bulatov, Hubie Chen, Peter Jeavons, Andrei A. Krokhin

Inf. Comput., 2009

09441 Executive Summary - The Constraint Satisfaction Problem: Complexity and Approximability.

Andrei A. Bulatov, Martin Grohe, Phokion G. Kolaitis, Andrei A. Krokhin

Proceedings of the Constraint Satisfaction Problem: Complexity and Approximability, 25.10., 2009

09441 Abstracts Collection - The Constraint Satisfaction Problem: Complexity and Approximability.

Andrei A. Bulatov, Martin Grohe, Phokion G. Kolaitis, Andrei A. Krokhin

Proceedings of the Constraint Satisfaction Problem: Complexity and Approximability, 25.10., 2009

2008

Maximizing Supermodular Functions on Product Lattices, with Application to Maximum Constraint Satisfaction.

Andrei A. Krokhin, Benoît Larose

SIAM J. Discret. Math., 2008

Complexity of Clausal Constraints Over Chains.

Nadia Creignou, Miki Hermann, Andrei A. Krokhin, Gernot Salzer

Theory Comput. Syst., 2008

Computational complexity of auditing finite attributes in statistical databases.

Peter Jonsson, Andrei A. Krokhin

J. Comput. Syst. Sci., 2008

The approximability of MAX CSP with fixed-value constraints.

Vladimir G. Deineko, Peter Jonsson, Mikael Klasson, Andrei A. Krokhin

J. ACM, 2008

Majority constraints have bounded pathwidth duality.

Víctor Dalmau, Andrei A. Krokhin

Eur. J. Comb., 2008

Retractions onto series-parallel posets.

Víctor Dalmau, Andrei A. Krokhin, Benoît Larose

Discret. Math., 2008

Caterpillar Duality for Constraint Satisfaction Problems.

Catarina Carvalho, Víctor Dalmau, Andrei A. Krokhin

Proceedings of the Twenty-Third Annual IEEE Symposium on Logic in Computer Science, 2008

Dualities for Constraint Satisfaction Problems.

Andrei A. Bulatov, Andrei A. Krokhin, Benoît Larose

Proceedings of the Complexity of Constraints, 2008

2007

First-order Definable Retraction Problems for Posets and Reflexive Graphs.

Víctor Dalmau, Andrei A. Krokhin, Benoît Larose

J. Log. Comput., 2007

Maximum H-colourable subdigraphs and constraint optimization with arbitrary weights.

Peter Jonsson, Andrei A. Krokhin

J. Comput. Syst. Sci., 2007

Ruling Out Polynomial-Time Approximation Schemes for Hard Constraint Satisfaction Problems.

Peter Jonsson, Andrei A. Krokhin, Fredrik Kuivinen

Proceedings of the Computer Science, 2007

2006

The Approximability of Three-valued MAX CSP.

Peter Jonsson, Mikael Klasson, Andrei A. Krokhin

SIAM J. Comput., 2006

A Monoidal Interval of Clones of Selfdual Functions.

Andrei A. Krokhin, Ivo G. Rosenberg

J. Autom. Lang. Comb., 2006

The complexity of soft constraint satisfaction.

David A. Cohen, Martin C. Cooper, Peter Jeavons, Andrei A. Krokhin

Artif. Intell., 2006

2005

Classifying the Complexity of Constraints Using Finite Algebras.

Andrei A. Bulatov, Peter Jeavons, Andrei A. Krokhin

SIAM J. Comput., 2005

Supermodular functions and the complexity of MAX CSP.

David A. Cohen, Martin C. Cooper, Peter Jeavons, Andrei A. Krokhin

Discret. Appl. Math., 2005

Maximum Constraint Satisfaction on Diamonds.

Andrei A. Krokhin, Benoît Larose

Proceedings of the Principles and Practice of Constraint Programming, 2005

2004

Recognizing frozen variables in constraint satisfaction problems.

Peter Jonsson, Andrei A. Krokhin

Theor. Comput. Sci., 2004

Constraint Satisfaction Problems on Intervals and Length.

Andrei A. Krokhin, Peter Jeavons, Peter Jonsson

SIAM J. Discret. Math., 2004

A Maximal Tractable Class of Soft Constraints.

David A. Cohen, Martin C. Cooper, Peter Jeavons, Andrei A. Krokhin

J. Artif. Intell. Res., 2004

Complexity classification in qualitative temporal constraint reasoning.

Peter Jonsson, Andrei A. Krokhin

Artif. Intell., 2004

Identifying Efficiently Solvable Cases of Max CSP.

David A. Cohen, Martin C. Cooper, Peter Jeavons, Andrei A. Krokhin

Proceedings of the STACS 2004, 2004

First-Order Definable Retraction Problems for Posets and Reflexive Graph.

Víctor Dalmau, Andrei A. Krokhin, Benoît Larose

Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS 2004), 2004

2003

Reasoning about temporal relations: The tractable subalgebras of Allen's interval algebra.

Andrei A. Krokhin, Peter Jeavons, Peter Jonsson

J. ACM, 2003

Solving Order Constraints in Logarithmic Space.

Andrei A. Krokhin, Benoît Larose

Proceedings of the STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27, 2003

Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey.

Andrei A. Krokhin, Andrei A. Bulatov, Peter Jeavons

Proceedings of the 33rd IEEE International Symposium on Multiple-Valued Logic (ISMVL 2003), 2003

Quantified Constraints: Algorithms and Complexity.

Ferdinand Börner, Andrei A. Bulatov, Peter Jeavons, Andrei A. Krokhin

Proceedings of the Computer Science Logic, 17th International Workshop, 2003

Soft Constraints: Complexity and Multimorphisms.

David A. Cohen, Martin C. Cooper, Peter Jeavons, Andrei A. Krokhin

Proceedings of the Principles and Practice of Constraint Programming, 2003

2002

Extending the Point Algebra into the Qualitative Algebra.

Andrei A. Krokhin, Peter Jonsson

Proceedings of the 9th International Symposium on Temporal Representation and Reasoning, 2002

2001

Congruences of Clone Lattices, II.

Andrei A. Krokhin

Order, 2001

The complexity of constraints on intervals and lengths

Andrei A. Krokhin, Peter Jeavons, Peter Jonsson

Electron. Colloquium Comput. Complex., 2001

The complexity of maximal constraint languages.

Andrei A. Bulatov, Andrei A. Krokhin, Peter Jeavons

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

A Complete Classification of Complexity in Allens Algebra in the Presence of a Non-Trivial Basic Relation.

Andrei A. Krokhin, Peter Jeavons, Peter Jonsson

Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, 2001

2000

Constraint Satisfaction Problems and Finite Algebras.

Andrei A. Bulatov, Andrei A. Krokhin, Peter Jeavons

Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000