Skip to main content

Research Repository

Advanced Search

Professor Andrei Krokhin's Outputs (21)

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)

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.

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)

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.

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

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)

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)

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})

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

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

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.

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