Andrei A. Krokhin

Orcid: 0000-0003-4373-8227

Affiliations:
  • Durham University, UK


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

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Functors on Relational Structures Which Admit Both Left and Right Adjoints.
SIAM J. Discret. Math., 2024

1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise.
Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science, 2024

2023
Topology and Adjunction in Promise Constraint Satisfaction.
SIAM J. Comput., February, 2023

On the complexity of the approximate hypergraph homomorphism problem.
CoRR, 2023

2022
An Invitation to the Promise Constraint Satisfaction Problem.
Electron. Colloquium Comput. Complex., 2022

2021
Algebraic Approach to Promise Constraint Satisfaction.
J. ACM, 2021

2019
Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs.
SIAM J. Comput., 2019

The complexity of 3-colouring <i>H</i>-colourable graphs.
Electron. Colloquium Comput. Complex., 2019

Algebraic approach to promise constraint satisfaction.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

The Complexity of 3-Colouring H-Colourable Graphs.
Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018
Towards a characterization of constant-factor approximable finite-valued CSPs.
J. Comput. Syst. Sci., 2018

2017
Binarisation for Valued Constraint Satisfaction Problems.
SIAM J. Discret. Math., 2017

The Complexity of General-Valued CSPs.
SIAM J. Comput., 2017

The Complexity of Valued CSPs.
Proceedings of the Constraint Satisfaction Problem: Complexity and Approximability, 2017

Polymorphisms, and How to Use Them.
Proceedings of the Constraint Satisfaction Problem: Complexity and Approximability, 2017

2016
On algebras with many symmetric operations.
Int. J. Algebra Comput., 2016

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

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

Towards a Characterization of Constant-Factor Approximable Min CSPs.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

2014
Oracle Tractability of Skew Bisubmodular Functions.
SIAM J. Discret. Math., 2014

Skew Bisubmodularity and Valued CSPs.
SIAM J. Comput., 2014

The Complexity of Valued Constraint Satisfaction.
Bull. EATCS, 2014

2013
Robust Satisfiability for CSPs: Hardness and Algorithmic Results.
ACM Trans. Comput. Theory, 2013

2012
On the hardness of losing weight.
ACM Trans. Algorithms, 2012

The Complexity of the List Homomorphism Problem for Graphs.
Theory Comput. Syst., 2012

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

2011
Two new homomorphism dualities and lattice operations.
J. Log. Comput., 2011

The Complexity of Evaluating First-Order Sentences over a Fixed Structure.
Proceedings of the 26th Annual IEEE Symposium on Logic in Computer Science, 2011

2010
CSP duality and trees of bounded pathwidth.
Theor. Comput. Sci., 2010

Retractions to Pseudoforests.
SIAM J. Discret. Math., 2010

Tree Dualities for Constraint Satisfaction.
Proceedings of the Computer Science Logic, 24th International Workshop, 2010

2009
Hard constraint satisfaction problems have hard gaps at location 1.
Theor. Comput. Sci., 2009

The complexity of constraint satisfaction games and QCSP.
Inf. Comput., 2009

09441 Executive Summary - The Constraint Satisfaction Problem: Complexity and Approximability.
Proceedings of the Constraint Satisfaction Problem: Complexity and Approximability, 25.10., 2009

09441 Abstracts Collection - The Constraint Satisfaction Problem: Complexity and Approximability.
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.
SIAM J. Discret. Math., 2008

Complexity of Clausal Constraints Over Chains.
Theory Comput. Syst., 2008

Computational complexity of auditing finite attributes in statistical databases.
J. Comput. Syst. Sci., 2008

The approximability of MAX CSP with fixed-value constraints.
J. ACM, 2008

Majority constraints have bounded pathwidth duality.
Eur. J. Comb., 2008

Retractions onto series-parallel posets.
Discret. Math., 2008

Caterpillar Duality for Constraint Satisfaction Problems.
Proceedings of the Twenty-Third Annual IEEE Symposium on Logic in Computer Science, 2008

Dualities for Constraint Satisfaction Problems.
Proceedings of the Complexity of Constraints, 2008

2007
First-order Definable Retraction Problems for Posets and Reflexive Graphs.
J. Log. Comput., 2007

Maximum H-colourable subdigraphs and constraint optimization with arbitrary weights.
J. Comput. Syst. Sci., 2007

Ruling Out Polynomial-Time Approximation Schemes for Hard Constraint Satisfaction Problems.
Proceedings of the Computer Science, 2007

2006
The Approximability of Three-valued MAX CSP.
SIAM J. Comput., 2006

A Monoidal Interval of Clones of Selfdual Functions.
J. Autom. Lang. Comb., 2006

The complexity of soft constraint satisfaction.
Artif. Intell., 2006

2005
Classifying the Complexity of Constraints Using Finite Algebras.
SIAM J. Comput., 2005

Supermodular functions and the complexity of MAX CSP.
Discret. Appl. Math., 2005

Maximum Constraint Satisfaction on Diamonds.
Proceedings of the Principles and Practice of Constraint Programming, 2005

2004
Recognizing frozen variables in constraint satisfaction problems.
Theor. Comput. Sci., 2004

Constraint Satisfaction Problems on Intervals and Length.
SIAM J. Discret. Math., 2004

A Maximal Tractable Class of Soft Constraints.
J. Artif. Intell. Res., 2004

Complexity classification in qualitative temporal constraint reasoning.
Artif. Intell., 2004

Identifying Efficiently Solvable Cases of Max CSP.
Proceedings of the STACS 2004, 2004

First-Order Definable Retraction Problems for Posets and Reflexive Graph.
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.
J. ACM, 2003

Solving Order Constraints in Logarithmic Space.
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.
Proceedings of the 33rd IEEE International Symposium on Multiple-Valued Logic (ISMVL 2003), 2003

Quantified Constraints: Algorithms and Complexity.
Proceedings of the Computer Science Logic, 17th International Workshop, 2003

Soft Constraints: Complexity and Multimorphisms.
Proceedings of the Principles and Practice of Constraint Programming, 2003

2002
Extending the Point Algebra into the Qualitative Algebra.
Proceedings of the 9th International Symposium on Temporal Representation and Reasoning, 2002

2001
Congruences of Clone Lattices, II.
Order, 2001

The complexity of constraints on intervals and lengths
Electron. Colloquium Comput. Complex., 2001

The complexity of maximal constraint languages.
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.
Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, 2001

2000
Constraint Satisfaction Problems and Finite Algebras.
Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000


  Loading...