Outputs (3)

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