about
My work lies at the interface of mathematics and computer science.
I study the computational complexity of constraint satisfaction problems and their approximation and promise variants using universal algebra, homotopy theory, category theory, and logic.
I was a post-doc at ISTA (2022–23), Oxford (2021–22), Durham University (2018–21), TU Dresden (2016–18), and Jagiellonian University (2016).
I received my PhD at Charles University in Prague on 29 Feb 2016. My advisor was Libor Barto.
upcoming
- British Colloquium for Theoretical Computer Science 2025
- Glasgow, Scotland, 14–16 April 2025
- Dagstuhl 25211: The Constraint Satisfaction Problem
- 18–23 May 2025
- Finite and Algorithmic Model Theory 2025
- Les Houches, France, 25–30 May 2025
- 107th Workshop on general Algebra AAA107
- Bern, Switzerland, 20–23 June 2025
selected papers
Meyer, S., & Opršal, J. (2025).
A topological proof of the Hell–Nešetřil dichotomy
SODA 2025, pp. 4507–4519.
doi:10.1137/1.9781611978322.154,
arXiv:2409.12627v2.
Dalmau, V., & Opršal, J. (2024).
Local consistency as a reduction between constraint satisfaction problems
LICS 2024, 29:1–15.
doi:10.1145/3661814.3662068,
arXiv:2301.05084v3.
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.
doi:10.1137/20M1378223,
arXiv:2003.11351.
Barto, L., Bulín, J., Krokhin, A., & Opršal, J. (2021).
Algebraic approach to promise constraint satisfaction.
J. ACM, 68(4), 28:1–66.
doi:10.1145/3457606
other
supervision
I am continuously looking for PhD students; see an advertisement here!
program committees
organising workshops, conferences, & seminars
- Birmingham CSP Meeting, Birmingham, UK, 7–8 May 2024.
- CSP World Congress 2022, Molveno, Italy, 22–24 Sep 2022.
- 98th Workshop on General Algebra, Dresden, Germany, 21–23 Jun 2019.
- CSP seminar, online, 2020–2022.
coding
- pcsptools — Tools for checking identities in polymorphism minions. Mostly.
- thead — Produces LaTeX headers from yaml metadata for sumbmission to various CS conferences and journals (LIPIcs, ACM, etc.)
- tmarko — Hack of marko markdown parser for LaTeX output
links