Skip to main content

Research Repository

Advanced Search

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.