All Outputs (7)

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.

ω-categorical structures avoiding height 1 identities (2020)
Journal Article
Bodirsky, M., Mottet, A., Olšák, M., Opršal, J., Pinsker, M., & Willard, R. (2021). ω-categorical structures avoiding height 1 identities. Transactions of the American Mathematical Society, 374(1), 327-350. https://doi.org/10.1090/tran/8179

The algebraic dichotomy conjecture for Constraint Satisfaction Problems (CSPs) of reducts of (infinite) finitely bounded homogeneous structures states that such CSPs are polynomial-time tractable if the model-complete core of the template has a pseud... Read More about ω-categorical structures avoiding height 1 identities.

Revisiting Alphabet Reduction in Dinur’s PCP (2020)
Presentation / Conference Contribution
Guruswami, V., Opršal, J., Sandeep, S., Byrka, J., & Meka, R. (2020, December). Revisiting Alphabet Reduction in Dinur’s PCP. Presented at Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

Dinur’s celebrated proof of the PCP theorem alternates two main steps in several iterations: gap amplification to increase the soundness gap by a large constant factor (at the expense of much larger alphabet size), and a composition step that brings... Read More about Revisiting Alphabet Reduction in Dinur’s PCP.

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

Deciding the Existence of Minority Terms (2019)
Journal Article
Kazda, A., Opršal, J., Valeriote, M., & Zhuk, D. (2020). Deciding the Existence of Minority Terms. Canadian Mathematical Bulletin, 63(3), 577-591. https://doi.org/10.4153/s0008439519000651

This paper investigates the computational complexity of deciding if a given finite idempotent algebra has a ternary term operation m that satisfies the minority equations m(y,x,x)≈m(x,y,x)≈m(x,x,y)≈y . We show that a common polynomial-time approach t... Read More about Deciding the Existence of Minority Terms.

Topology is relevant (in a dichotomy conjecture for infinite-domain constraint satisfaction problems) (2019)
Presentation / Conference Contribution
Bodirsky, M., Mottet, A., Olsak, M., Oprsal, J., Pinsker, M., & Willard, R. (2019, June). Topology is relevant (in a dichotomy conjecture for infinite-domain constraint satisfaction problems). Presented at 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), Vancouver, Canada

The algebraic dichotomy conjecture for Constraint Satisfaction Problems (CSPs) of reducts of (innite) nitely bounded homogeneous structures states that such CSPs are polynomial-time tractable when the modelcomplete core of the template has a pseudo-S... Read More about Topology is relevant (in a dichotomy conjecture for infinite-domain constraint satisfaction problems).

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.