All Outputs (4)

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

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.