Skip to main content

Research Repository

Advanced Search

Professor Andrei Krokhin's Outputs (70)

1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise (2025)
Journal Article
Ciardo, L., Kozik, M., Krokhin, A., Nakajima, T.-V., & Živný, S. (online). 1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise. ACM Transactions on Computational Logic, https://doi.org/10.1145/3719007

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.

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.

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.

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

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.

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.

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.

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.

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.

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.

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.