Skip to main content

Research Repository

Advanced Search

Professor Andrei Krokhin's Outputs (69)

Topology and adjunction in promise constraint satisfaction (2023)
Journal Article
Krokhin, A., Opršal, J., Wrochna, M., & Živný, S. (2023). Topology and adjunction in promise constraint satisfaction. SIAM Journal on Computing, 52(1), 38-79. https://doi.org/10.1137/20m1378223

The approximate graph colouring problem, whose complexity is unresolved in most cases, concerns finding a c-colouring of a graph that is promised to be k-colourable, where c≥k. This problem naturally generalises to promise graph homomorphism problems... Read More about Topology and adjunction in promise constraint satisfaction.

Algebraic Approach to Promise Constraint Satisfaction (2021)
Journal Article
Barto, L., Bulín, J., Krokhin, A., & Opršal, J. (2021). Algebraic Approach to Promise Constraint Satisfaction. Journal of the ACM, 68(4), 1-66. https://doi.org/10.1145/3457606

The complexity and approximability of the constraint satisfaction problem (CSP) has been actively studied over the past 20 years. A new version of the CSP, the promise CSP (PCSP), has recently been proposed, motivated by open questions about the appr... Read More about Algebraic Approach to Promise Constraint Satisfaction.

Robust algorithms with polynomial loss for near-unanimity CSPs (2019)
Journal Article
Dalmau, V., Kozik, M., Krokhin, A., Makarychev, K., Makarychev, Y., & Oprsal, J. (2019). Robust algorithms with polynomial loss for near-unanimity CSPs. SIAM Journal on Computing, 48(6), 1763-1795. https://doi.org/10.1137/18m1163932

An instance of the Constraint Satisfaction Problem (CSP) is given by a family of constraints on overlapping sets of variables, and the goal is to assign values from a xed domain to the variables so that all constraints are satised. In the optimizatio... Read More about Robust algorithms with polynomial loss for near-unanimity CSPs.

Towards a characterization of constant-factor approximable Finite-Valued CSPs (2018)
Journal Article
Dalmau, V., Krokhin, A., & Manokaran, R. (2018). Towards a characterization of constant-factor approximable Finite-Valued CSPs. Journal of Computer and System Sciences, 97, 14-27. https://doi.org/10.1016/j.jcss.2018.03.003

We study the approximability of (Finite-)Valued Constraint Satisfaction Problems (VCSPs) with a fixed finite constraint language Γ consisting of finitary functions on a fixed finite domain. Ene et al. have shown that, under a mild technical condition... Read More about Towards a characterization of constant-factor approximable Finite-Valued CSPs.

Binarisation for Valued Constraint Satisfaction Problems (2017)
Journal Article
Cohen, D., Cooper, M., Jeavons, P., Krokhin, A., Powell, R., & Zivny, S. (2017). Binarisation for Valued Constraint Satisfaction Problems. SIAM Journal on Discrete Mathematics, 31(4), 2279-2300. https://doi.org/10.1137/16m1088107

We study methods for transforming valued constraint satisfaction problems (VCSPs) to binary VCSPs. First, we show that the standard dual encoding preserves many aspects of the algebraic properties that capture the computational complexity of VCSPs. S... Read More about Binarisation for Valued Constraint Satisfaction Problems.

The complexity of general-valued CSPs (2017)
Journal Article
Kolmogorov, V., Krokhin, A., & Rolínek, M. (2017). The complexity of general-valued CSPs. SIAM Journal on Computing, 46(3), 1087-1110. https://doi.org/10.1137/16m1091836

An instance of the valued constraint satisfaction problem (VCSP) is given by a finite set of variables, a finite domain of labels, and a sum of functions, each function depending on a subset of the variables. Each function can take finite values spec... Read More about The complexity of general-valued CSPs.

Polymorphisms, and how to use them (2017)
Book Chapter
Barto, L., Krokhin, A., & Willard, R. (2017). Polymorphisms, and how to use them. In A. Krokhin, & S. Živný (Eds.), The constraint satisfaction problem : complexity and approximability (1-44). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/dfu.vol7.15301.1

This article describes the algebraic approach to Constraint Satisfaction Problem that led to many developments in both CSP and universal algebra. No prior knowledge of universal algebra is assumed.

The complexity of Valued CSPs (2017)
Book Chapter
Krokhin, A., & Živný, S. (2017). The complexity of Valued CSPs. In A. Krokhin, & S. Živný (Eds.), The constraint satisfaction problem : complexity and approximability (233-266). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/dfu.vol7.15301.9

We survey recent results on the broad family of problems that can be cast as valued constraint satisfaction problems (VCSPs). We discuss general methods for analysing the complexity of such problems, give examples of tractable cases, and identify gen... Read More about The complexity of Valued CSPs.

On algebras with many symmetric operations (2016)
Journal Article
Carvalho, C., & Krokhin, A. (2016). On algebras with many symmetric operations. International Journal of Algebra and Computation, 26(05), 1019-1032. https://doi.org/10.1142/s0218196716500429

An n-ary operation f is called symmetric if, for all permutations π of {1, . . . , n}, it satisfies the identity f(x1, x2, . . . , xn) = f(xπ(1), xπ(2), . . . , xπ(n) ). We show that, for each finite algebra A, either it has symmetric term operations... Read More about On algebras with many symmetric operations.

Characterizations of several Maltsev conditions (2015)
Journal Article
Kozik, M., Krokhin, A., Valeriote, M., & Willard, R. (2015). Characterizations of several Maltsev conditions. Algebra Universalis, 73(3), 205-224. https://doi.org/10.1007/s00012-015-0327-2

ame congruence theory identifies six Maltsev conditions associated with locally finite varieties omitting certain types of local behaviour. Extending a result of Siggers, we show that of these six Maltsev conditions only two of them are equivalent to... Read More about Characterizations of several Maltsev conditions.

Towards a Characterization of Constant-Factor Approximable Min CSPs (2014)
Book Chapter
Dalmau, V., Krokhin, A., & Manokaran, R. (2015). Towards a Characterization of Constant-Factor Approximable Min CSPs. In P. Indyk (Ed.), Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms : San Diego, California, USA, January 4-6, 2015 (847-857). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611973730.58

We study the approximability of Minimum Constraint Satisfaction Problems (Min CSPs) with a fixed finite constraint language Γ on an arbitrary finite domain. The goal in such a problem is to minimize the number of unsatisfied constraints in a given in... Read More about Towards a Characterization of Constant-Factor Approximable Min CSPs.

Oracle Tractability of Skew Bisubmodular Functions (2014)
Journal Article
Huber, A., & Krokhin, A. (2014). Oracle Tractability of Skew Bisubmodular Functions. SIAM Journal on Discrete Mathematics, 28(4), 1828-1837. https://doi.org/10.1137/130936038

In this paper we consider skew bisubmodular functions as recently introduced by the authors and Powell. We construct a convex extension of a skew bisubmodular function which we call Lovász extension in correspondence to the submodular case. We use th... Read More about Oracle Tractability of Skew Bisubmodular Functions.

The Complexity of Valued Constraint Satisfaction (2014)
Journal Article
Jeavons, P., Krokhin, A., & Živný, S. (2014). The Complexity of Valued Constraint Satisfaction. Bulletin of the European Association for Theoretical Computer Science, 113, 21-55

We survey recent results on the broad family of problems that can be cast as valued constraint satisfaction problems. We discuss general methods for analysing the complexity of such problems, give examples of tractable cases, and identify general fea... Read More about The Complexity of Valued Constraint Satisfaction.

Skew Bisubmodularity and Valued CSPs (2014)
Journal Article
Huber, A., Krokhin, A., & Powell, R. (2014). Skew Bisubmodularity and Valued CSPs. SIAM Journal on Computing, 43(3), 1064-1084. https://doi.org/10.1137/120893549

An instance of the (finite-)valued constraint satisfaction problem (VCSP) is given by a finite set of variables, a finite domain of values, and a sum of (rational-valued) functions, with each function depending on a subset of the variables. The goal... Read More about Skew Bisubmodularity and Valued CSPs.

Robust Satisfiability for CSPs: Hardness and Algorithmic Results (2013)
Journal Article
Dalmau, V., & Krokhin, A. (2013). Robust Satisfiability for CSPs: Hardness and Algorithmic Results. ACM Transactions on Computation Theory, 5(4), Article 15. https://doi.org/10.1145/2540090

An algorithm for a constraint satisfaction problem is called robust if it outputs an assignment satisfying at least a (1 − f(ε))-fraction of constraints for each (1 − ε)-satisfiable instance (i.e., such that at most a ε-fraction of constraints needs... Read More about Robust Satisfiability for CSPs: Hardness and Algorithmic Results.

CSP duality and trees of bounded pathwidth. (2010)
Journal Article
Carvalho, C., Dalmau, V., & Krokhin, A. (2010). CSP duality and trees of bounded pathwidth. Theoretical Computer Science, 411(34-36), 3188-3208. https://doi.org/10.1016/j.tcs.2010.05.016

We study non-uniform constraint satisfaction problems definable in monadic Datalog stratified by the use of non-linearity. We show how such problems can be described in terms of homomorphism dualities involving trees of bounded pathwidth and in algeb... Read More about CSP duality and trees of bounded pathwidth..

Hard constraint satisfaction problems have hard gaps at location 1 (2009)
Journal Article
Jonsson, P., Krokhin, A., & Kuivinen, F. (2009). Hard constraint satisfaction problems have hard gaps at location 1. Theoretical Computer Science, 410(38-40), 3856-3874. https://doi.org/10.1016/j.tcs.2009.05.022

An instance of the maximum constraint satisfaction problem (Max CSP) is a finite collection of constraints on a set of variables, and the goal is to assign values to the variables that maximises the number of satisfied constraints. Max CSP captures m... Read More about Hard constraint satisfaction problems have hard gaps at location 1.

The complexity of constraint satisfaction games and QCSP (2009)
Journal Article
Boerner, F., Bulatov, A., Chen, H., Jeavons, P., & Krokhin, A. (2009). The complexity of constraint satisfaction games and QCSP. Information and Computation, 207(9), 923-944. https://doi.org/10.1016/j.ic.2009.05.003

We study the complexity of two-person constraint satisfaction games. An instance of such a game is given by a collection of constraints on overlapping sets of variables, and the two players alternately make moves assigning values from a finite domain... Read More about The complexity of constraint satisfaction games and QCSP.

The approximability of MAX CSP with fixed-value constraints (2008)
Journal Article
Deineko, V., Jonsson, P., Klasson, M., & Krokhin, A. (2008). The approximability of MAX CSP with fixed-value constraints. Journal of the ACM, 55(4), Article 16. https://doi.org/10.1145/1391289.1391290

In the maximum constraint satisfaction problem (MAX CSP), one is given a finite collection of (possibly weighted) constraints on overlapping sets of variables, and the goal is to assign values from a given finite domain to the variables so as to maxi... Read More about The approximability of MAX CSP with fixed-value constraints.

Computational complexity of auditing finite attributes in statistical databases (2008)
Journal Article
Jonsson, P., & Krokhin, A. (2008). Computational complexity of auditing finite attributes in statistical databases. Journal of Computer and System Sciences, 74(5), 898-909. https://doi.org/10.1016/j.jcss.2008.02.002

We study the computational complexity of auditing finite attributes in databases allowing statistical queries. Given a database that supports statistical queries, the auditing problem is to check whether an attribute can be completely determined or n... Read More about Computational complexity of auditing finite attributes in statistical databases.

Retractions onto series-parallel posets (2008)
Journal Article
Dalmau, V., Krokhin, A., & Larose, B. (2008). Retractions onto series-parallel posets. Discrete Mathematics, 308(11), 2104-2114. https://doi.org/10.1016/j.disc.2006.08.010

The poset retraction problem for a poset P is whether a given poset Q containing P as a subposet admits a retraction onto P, that is, whether there is a homomorphism from Q onto P which fixes every element of P. We study this problem for finite serie... Read More about Retractions onto series-parallel posets.

Majority constraints have bounded pathwidth duality (2008)
Journal Article
Dalmau, V., & Krokhin, A. (2008). Majority constraints have bounded pathwidth duality. European Journal of Combinatorics, 29(4), 821-837. https://doi.org/10.1016/j.ejc.2007.11.020

We study certain constraint satisfaction problems which are the problems of deciding whether there exists a homomorphism from a given relational structure to a fixed structure with a majority polymorphism. We show that such a problem is equivalent to... Read More about Majority constraints have bounded pathwidth duality.

Maximizing supermodular functions on product lattices, with application to maximum constraint satisfaction (2008)
Journal Article
Krokhin, A., & Larose, B. (2008). Maximizing supermodular functions on product lattices, with application to maximum constraint satisfaction. SIAM Journal on Discrete Mathematics, 22(1), 312-328. https://doi.org/10.1137/060669565

Recently, a strong link has been discovered between supermodularity on lattices and tractability of optimization problems known as maximum constraint satisfaction problems. This paper strengthens this link. We study the problem of maximizing a superm... Read More about Maximizing supermodular functions on product lattices, with application to maximum constraint satisfaction.

Complexity of clausal constraints over chains (2008)
Journal Article
Creignou, N., Hermann, M., Krokhin, A., & Salzer, G. (2008). Complexity of clausal constraints over chains. Theory of Computing Systems, 42(2), 239-255. https://doi.org/10.1007/s00224-007-9003-z

We investigate the complexity of the satisfiability problem of constraints over finite totally ordered domains. In our context, a clausal constraint is a disjunction of inequalities of the form x≥d and x≤d. We classify the complexity of constraints b... Read More about Complexity of clausal constraints over chains.

Dualities for constraint satisfaction problems (2008)
Book Chapter
Bulatov, A., Krokhin, A., & Larose, B. (2008). Dualities for constraint satisfaction problems. In N. Creignou, P. Kolaitis, & H. Vollmer (Eds.), Complexity of constraints : an overview of current research themes (93-124). Springer Verlag. https://doi.org/10.1007/978-3-540-92800-3_5

In a nutshell, a duality for a constraint satisfaction problem equates the existence of one homomorphism to the non-existence of other homomorphisms. In this survey paper, we give an overview of logical, combinatorial, and algebraic aspects of the fo... Read More about Dualities for constraint satisfaction problems.

Maximum H-colourable subdigraphs and constraint optimization with arbitrary weights (2007)
Journal Article
Jonsson, P., & Krokhin, A. (2007). Maximum H-colourable subdigraphs and constraint optimization with arbitrary weights. Journal of Computer and System Sciences, 73(5), 691-702. https://doi.org/10.1016/j.jcss.2007.02.001

In the maximum constraint satisfaction problem (Max CSP), one is given a finite collection of positive-weight constraints on overlapping sets of variables, and the goal is to assign values from a given domain to the variables so that the total weight... Read More about Maximum H-colourable subdigraphs and constraint optimization with arbitrary weights.

First-order definable retraction problems for posets and reflexive graphs (2007)
Journal Article
Dalmau, V., Krokhin, A., & Larose, B. (2007). First-order definable retraction problems for posets and reflexive graphs. Journal of Logic and Computation, 17(1), 31-51. https://doi.org/10.1093/logcom/exl014

A retraction from a structure P to its substructure Q is a homomorphism from P onto Q that is the identity on Q. We present an algebraic condition which completely characterzies all posets and all reflexive graphs Q such that the class of all posets... Read More about First-order definable retraction problems for posets and reflexive graphs.

The complexity of soft constraint satisfaction (2006)
Journal Article
Cohen, D., Cooper, M., Jeavons, P., & Krokhin, A. (2006). The complexity of soft constraint satisfaction. Artificial Intelligence, 170(11), 983-1016. https://doi.org/10.1016/j.artint.2006.04.002

Over the past few years there has been considerable progress in methods to systematically analyse the complexity of constraint satisfaction problems with specified constraint types. One very powerful theoretical development in this area links the com... Read More about The complexity of soft constraint satisfaction.

Supermodular functions and the complexity of MAX CSP (2005)
Journal Article
Cohen, D., Cooper, M., Jeavons, P., & Krokhin, A. (2005). Supermodular functions and the complexity of MAX CSP. Discrete Applied Mathematics, 149(1-3), 53-72. https://doi.org/10.1016/j.dam.2005.03.003

In this paper we study the complexity of the maximum constraint satisfaction problem (MAX CSP) over an arbitrary finite domain. An instance of MAX CSP consists of a set of variables and a collection of constraints which are applied to certain specifi... Read More about Supermodular functions and the complexity of MAX CSP.

Classifying the complexity of constraints using finite algebras (2005)
Journal Article
Bulatov, A., Jeavons, P., & Krokhin, A. (2005). Classifying the complexity of constraints using finite algebras. SIAM Journal on Computing, 34(3), 720-742. https://doi.org/10.1137/s0097539700376676

Many natural combinatorial problems can be expressed as constraint satisfaction problems. This class of problems is known to be NP-complete in general, but certain restrictions on the form of the constraints can ensure tractability. Here we show that... Read More about Classifying the complexity of constraints using finite algebras.

The complexity of constraint satisfaction: an algebraic approach (2005)
Book Chapter
Krokhin, A., Bulatov, A., & Jeavons, P. (2005). The complexity of constraint satisfaction: an algebraic approach. In V. B. Kudryavtsev, & I. G. Rosenberg (Eds.), Structural theory of automata, semigroups, and universal algebra (181-213). Springer Netherlands. https://doi.org/10.1007/1-4020-3817-8_8

Many computational problems arising in artificial intelligence, computer science and elsewhere can be represented as constraint satisfaction and optimization problems. In this survey paper we discuss an algebraic approach that has proved to be very s... Read More about The complexity of constraint satisfaction: an algebraic approach.

Recognizing frozen variables in constraint satisfaction problems (2004)
Journal Article
Jonsson, P., & Krokhin, A. (2004). Recognizing frozen variables in constraint satisfaction problems. Theoretical Computer Science, 329(1-3), 93-113. https://doi.org/10.1016/j.tcs.2004.08.006

In constraint satisfaction problems over finite domains, some variables can be frozen, that is, they take the same value in all possible solutions. We study the complexity of the problem of recognizing frozen variables with restricted sets of constra... Read More about Recognizing frozen variables in constraint satisfaction problems.

Complexity classification in qualitative temporal constraint reasoning (2004)
Journal Article
Jonsson, P., & Krokhin, A. (2004). Complexity classification in qualitative temporal constraint reasoning. Artificial Intelligence, 160(1-2), 35-51. https://doi.org/10.1016/j.artint.2004.05.010

We study the computational complexity of the qualitative algebra which is a temporal constraint formalism that combines the point algebra, the point-interval algebra and Allen's interval algebra. We identify all tractable fragments and show that ever... Read More about Complexity classification in qualitative temporal constraint reasoning.

A maximal tractable class of soft constraints (2004)
Journal Article
Cohen, D., Cooper, M., Jeavons, P., & Krokhin, A. (2004). A maximal tractable class of soft constraints. Journal of Artificial Intelligence Research, 22, 1-22. https://doi.org/10.1613/jair.1400

Many researchers in artificial intelligence are beginning to explore the use of soft constraints to express a set of (possibly conflicting) problem requirements. A soft constraint is a function defined on a collection of variables which associates so... Read More about A maximal tractable class of soft constraints.

Constraint satisfaction problems on intervals and lengths (2004)
Journal Article
Krokhin, A., Jeavons, P., & Jonsson, P. (2004). Constraint satisfaction problems on intervals and lengths. SIAM Journal on Discrete Mathematics, 17(3), 453-477. https://doi.org/10.1137/s0895480102410201

We study interval-valued constraint satisfaction problems (CSPs), in which the aim is to find an assignment of intervals to a given set of variables subject to constraints on the relative positions of intervals. Many well-known problems such as INTER... Read More about Constraint satisfaction problems on intervals and lengths.

Reasoning about temporal relations : the maximal tractable subalgebras of Allen's interval algebra (2003)
Journal Article
Krokhin, A., Jeavons, P., & Jonsson, P. (2003). Reasoning about temporal relations : the maximal tractable subalgebras of Allen's interval algebra. Journal of the ACM, 50(5), 591-640. https://doi.org/10.1145/876638.876639

Allen's interval algebra is one of the best established formalisms for temporal reasoning. This article provides the final step in the classification of complexity for satisfiability problems over constraints expressed in this algebra. When the const... Read More about Reasoning about temporal relations : the maximal tractable subalgebras of Allen's interval algebra.

A monoidal interval of isotone clones on a finite chain (2002)
Journal Article
Krokhin, A., & Larose, B. (2002). A monoidal interval of isotone clones on a finite chain. Acta scientiarum mathematicarum, 68(1-2), 37-62

Let k denote a k-element chain, k3. Let M denote the clone generated by all unary isotone operations on k and let Pol denote the clone of all isotone operations on k. We investigate the interval of clones [MPol]. Among other results, we describe comp... Read More about A monoidal interval of isotone clones on a finite chain.

Identifying efficiently solvable cases of Max CSP
Presentation / Conference Contribution
Cohen, D., Cooper, M., Jeavons, P., & Krokhin, A. (2004, December). Identifying efficiently solvable cases of Max CSP. Presented at 21st International Symposium on Theoretical Aspects of Computer Science

On the structure of clone lattices, II
Presentation / Conference Contribution
Bulatov, A., Krokhin, A., Safin, K., Semigrodskikh, A., & Sukhanov, E. (2001, December). On the structure of clone lattices, II

Extending the Point Algebra into the Qualitative Algebra
Presentation / Conference Contribution
Krokhin, A., & Jonsson, P. (2002, December). Extending the Point Algebra into the Qualitative Algebra. Presented at Proceedings of 9th International Workshop on Temporal Representation and Reasoning ({TIME'02})

Soft constraints: complexity and multimorphisms
Presentation / Conference Contribution
Cohen, D., Cooper, M., Jeavons, P., & Krokhin, A. (2003, December). Soft constraints: complexity and multimorphisms. Presented at Proceedings of 9th International Conference on Principle and Practice of Constraint Programming {(CP'03)

The complexity of constraints on intervals and lengths
Presentation / Conference Contribution
Krokhin, A., Jeavons, P., & Jonsson, P. (2002, December). The complexity of constraints on intervals and lengths. Presented at Proceedings of the 19th International Symposium on Theoretical Aspects of Computer Science {(STACS'02)

Quantified constraints: Algorithms and complexity
Presentation / Conference Contribution
Boerner, F., Bulatov, A., Jeavons, P., & Krokhin, A. (2003, December). Quantified constraints: Algorithms and complexity. Presented at 17th International Workshop on Computer Science Logic

First-Order Definable Retraction Problems for Posets and Reflexive Graphs
Presentation / Conference Contribution
Dalmau, V., Krokhin, A., & Larose, B. (2023, July). First-Order Definable Retraction Problems for Posets and Reflexive Graphs. Presented at 19th Annual IEEE Symposium on Logic in Computer Science (LICS'04), Turku, Finland

A retraction from a structure P to its substructure Q is a homomorphism from P onto Q that is the identity on Q. We present an algebraic condition which completely characterises all posets and all reflexive graphs Q with the following property: the c... Read More about First-Order Definable Retraction Problems for Posets and Reflexive Graphs.

Maximum constraint satisfaction on diamonds
Presentation / Conference Contribution
Krokhin, A., & Larose, B. (2005, December). Maximum constraint satisfaction on diamonds. Presented at 11th International Conference on Principles and Practice of Constraint Programming {(CP'05)

1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise
Presentation / Conference Contribution
Ciardo, L., Kozik, M., Krokhin, A., Nakajima, T.-V., & Živný, S. (2024, July). 1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise. Presented at LICS '24: 39th Annual ACM/IEEE Symposium on Logic in Computer Science, Tallinn Estonia

The 1-in-3 and Not-All-Eqal satisfiability problems for Boolean CNF formulas are two well-known NP-hard problems. In contrast, the promise 1-in-3 vs. Not-All-Eqal problem can be solved in polynomial time. In the present work, we investigate this cons... Read More about 1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise.

A tractable class of soft constraints.
Presentation / Conference Contribution
Cohen, D., Cooper, M., Jeavons, P., & Krokhin, A. (2003, December). A tractable class of soft constraints. Presented at 18th International Joint Conference on Artificial Intelligence {(IJCAI'03)

Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey
Presentation / Conference Contribution
Krokhin, A., Bulatov, A., & Jeavons, P. (2003, May). Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey. Presented at 33rd International Symposium on Multiple-Valued Logic (ISMVL'03)

Many computational problems arising in artificial intelligence, computer science and elsewhere can be represented as constraint satisfaction and optimization problems. In this short survey we discuss an approach that is related to the algebraic compo... Read More about Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey.

Solving order constraints in logarithmic space
Presentation / Conference Contribution
Krokhin, A., & Larose, B. (2003, January). Solving order constraints in logarithmic space. Presented at Proceedings of the 20th International Symposium on Theoretical Aspects of Computer Science {(STACS'03) Berlin, Berlin

We combine methods of order theory, finite model theory, and universal algebra to study, within the constraint satisfaction framework, the complexity of some well-known combinatorial problems connected with a finite poset. We identify some conditions... Read More about Solving order constraints in logarithmic space.

The complexity of maximal constraint languages
Presentation / Conference Contribution
Bulatov, A., Krokhin, A., & Jeavons, P. (2001, December). The complexity of maximal constraint languages. Presented at 33rd ACM Symposium on the Theory of Computing(STOC), Crete, Greece

Many combinatorial search problems can be expressed as “constraint satisfaction problems” using an appropriate “constraint language”, that is, a set of relations over some fixed finite set of values. It is well-known that there is a trade-off between... Read More about The complexity of maximal constraint languages.

Caterpillar duality for constraint satisfaction problems
Presentation / Conference Contribution
Carvalho, C., Dalmau, V., & Krokhin, A. (2008, June). Caterpillar duality for constraint satisfaction problems. Presented at 23rd Annual IEEE Symposium on Logic in Computer Science (LICS) 2008, Pittsburgh, Pennsylvania

The study of constraint satisfaction problems definable in various fragments of Datalog has recently gained considerable importance. We consider constraint satisfaction problems that are definable in the smallest natural recursive fragment of Datalog... Read More about Caterpillar duality for constraint satisfaction problems.

The complexity of the list homomorphism problem for graphs.
Presentation / Conference Contribution
Egri, L., Krokhin, A., Larose, B., & Tesson, P. (2010, December). The complexity of the list homomorphism problem for graphs. Presented at Symposium on Theoretical Aspects of Computer Science., Nancy, France

The Complexity of General-Valued CSPs
Presentation / Conference Contribution
Kolmogorov, V., Krokhin, A., & Rolinek, M. (2015, December). The Complexity of General-Valued CSPs. Presented at 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), Berkeley

An instance of the Valued Constraint Satisfaction Problem (VCSP) is given by a finite set of variables, a finite domain of labels, and a sum of functions, each function depending on a subset of the variables. Each function can take finite values spec... Read More about The Complexity of General-Valued CSPs.

Robust algorithms with polynomial loss for near-unanimity CSPs
Presentation / Conference Contribution
Dalmau, V., Kozik, M., Krokhin, A., Makarychev, K., Makarychev, Y., & Oprsal, J. (2017, January). Robust algorithms with polynomial loss for near-unanimity CSPs. Presented at Symposium on Discrete Algorithms, Barcelona

An instance of the Constraint Satisfaction Problem (CSP) is given by a family of constraints on overlapping sets of variables, and the goal is to assign values from a fixed domain to the variables so that all constraints are satisfied. In the optimiz... Read More about Robust algorithms with polynomial loss for near-unanimity CSPs.

The complexity of 3-colouring H-colourable graphs
Presentation / Conference Contribution
Krokhin, A., & Oprsal, J. (2019, November). The complexity of 3-colouring H-colourable graphs. Presented at Foundations of Computer Science (FOCS), Baltimore, USA

Algebraic approach to promise constraint satisfaction
Presentation / Conference Contribution
Bulin, J., Krokhin, A., & Oprsal, J. (2019, June). Algebraic approach to promise constraint satisfaction. Presented at ACM Symposium on Theory of Computing (STOC), Phoenix, USA

The complexity and approximability of the constraint satisfaction problem (CSP) has been actively studied over the last 20 years. A new version of the CSP, the promise CSP (PCSP) has recently been proposed, motivated by open questions about the appro... Read More about Algebraic approach to promise constraint satisfaction.