Skip to main content

Research Repository

Advanced Search

Outputs (69)

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 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.

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.