Skip to main content

Research Repository

Advanced Search

Professor Andrei Krokhin's Outputs (21)

1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise (2024)
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 LLICS '24: 39th Annual ACM/IEEE Symposium on Logic in Computer Science, Tallinn, Estonia

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

The complexity of 3-colouring H-colourable graphs (2020)
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 (2019)
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.

Robust algorithms with polynomial loss for near-unanimity CSPs (2017)
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 General-Valued CSPs (2015)
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.

The complexity of the list homomorphism problem for graphs. (2010)
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

Caterpillar duality for constraint satisfaction problems (2008)
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.

Maximum constraint satisfaction on diamonds (2005)
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)

Identifying efficiently solvable cases of Max CSP (2004)
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

First-Order Definable Retraction Problems for Posets and Reflexive Graphs (2004)
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.

A tractable class of soft constraints. (2003)
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)

Soft constraints: complexity and multimorphisms (2003)
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)

Quantified constraints: Algorithms and complexity (2003)
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

Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey (2003)
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 (2003)
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.

Extending the Point Algebra into the Qualitative Algebra (2002)
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})

The complexity of constraints on intervals and lengths (2002)
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)

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