jakub opršal

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

Dagstuhl 25141: Categories for Automata and Language Theory

30 Mar–4 Apr 2025

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

Conference publications

1. Avvakumov, S., Filakovský, M., Opršal, J., Tasinato, G., & Wagner, U. (2025). Hardness of 4-colouring G-colourable graphs. Accepted to STOC 2025.
2. Meyer, S., & Opršal, J. (2025). A topological proof of the Hell–Nešetřil dichotomy. Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, (pp. 4507–4519). New Orleans, LA, USA: SIAM. arXiv:2409.12627v2, doi:10.1137/​1.9781611978322.154.
3. Dalmau, V., & Opršal, J. (2024). Local consistency as a reduction between constraint satisfaction problems. Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2024, (pp. 29:1–29:15). Tallinn, Estonia: ACM. arXiv:2301.05084, doi:10.1145/​3661814.​3662068.
4. ten Cate, B., Dalmau, V., & Opršal, J. (2024). Right-Adjoints for Datalog Programs. International Conference on Database Theory, ICDT 2024, (pp. 10:1–10:20). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. arXiv:2302.06366, doi:10.4230/​LIPIcs.ICDT.​2024.10.
5. Filakovský, M., Nakajima, T.-V., Opršal, J., Tasinato, G., & Wagner, U. (2024). Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs. Symposium on Theoretical Aspects of Computer Science, STACS 2024, (pp. 34:1–34:19). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. arXiv:2312.12981, doi:10.4230/​LIPIcs.STACS.​2024.34.
6. Guruswami, V., Opršal, J., & Sandeep, S. (2020). Revisiting alphabet reduction in Dinur’s PCP. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2020 (pp. 34:1–34:14). Virtual Conference: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/​LIPIcs.​APPROX/RANDOM.​2020.34
7. Bodirsky, M., Mottet, A., Olšák, M., Opršal, J., Pinsker, M., & Willard, R. (2019). Topology is relevant (in a dichotomy conjecture for infinite-domain constraint satisfaction problems). Symposium on Logic in Computer Science, LICS 2019 (pp. 1–12). Vancouver, BC, Canada: IEEE. arXiv:1901.04237, doi:10.1109/​LICS.2019.​8785883
8. Bulín, J., Krokhin, A., & Opršal, J. (2019). Algebraic approach to promise constraint satisfaction. Symposium on the Theory of Computing, STOC 2019. New York, NY, USA: ACM. doi:10.1145/​3313276.3316300
9. Krokhin, A., & Opršal, J. (2019). The complexity of 3-colouring H-colourable graphs. Symposium on Foundations of Computer Science, FOCS 2019 (pp. 1227–1239). Baltimore, Maryland, USA: IEEE Computer Society. arXiv:1904.03214, doi:10.1109/​FOCS.2019.00076
10. Dalmau, V., Kozik, M., Krokhin, A., Makarychev, K., Makarychev, Y., & Opršal, J. (2017). Robust algorithms with polynomial loss for near-unanimity CSPs. Symposium on Discrete Algorithms, SODA 2017 (pp. 340–357). Barcelona, Spain: SIAM. arXiv:1607.04787 doi:10.1137/​1.9781611974782.22
11. Carpi, A., Fici, G., Holub, Š., Opršal, J., & Sciortino, M. (2014). Universal Lyndon words. Mathematical Foundations of Computer Science, MFCS 2014 (pp. 135–146). Budapest, Hungary: Springer. arXiv:1406.5895 doi:10.1007/​978-3-662-44522-8_12

Journal papers

1. Dalmau, V., Krokhin, A., & Opršal, J. (2024). Functors on relational structures which admit both left and right adjoints. SIAM Journal on Discrete Mathematics, 38(3), 2041–2068. arXiv:2302.13657. doi:10.1137/​23M1555223.
2. 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. arXiv:2003.11351, doi:10.1137/​20M1378223
3. Barto, L., Bulín, J., Krokhin, A., & Opršal, J. (2021). Algebraic approach to promise constraint satisfaction. J. ACM, 68(4), 28:1–66. arXiv:1811.00970, doi:10.1145/​3457606
4. Bodirsky, M., Mottet, A., Olšák, M., Opršal, J., Pinsker, M., & Willard, R. (2020). ω-categorical structures avoiding height 1 identities. Trans. Amer. Math. Soc., 374(1), 327–350. arXiv:2006.12254, doi:10.1090/​tran/8179
5. Kazda, A., Opršal, J., Valeriote, M., & Zhuk, D. (2020). Deciding the existence of minority terms. Canadian Mathematical Bulletin, 63(3), 577–591. arXiv:1901.00316, doi:10.4153/​S0008439519000651
6. Dalmau, V., Kozik, M., Krokhin, A., Makarychev, K., Makarychev, Y., & Opršal, J. (2019). Robust algorithms with polynomial loss for near-unanimity CSPs. SIAM J. Comput., 48(6), 1763–1795. arXiv:1607.04787, doi:10.1137/​18M1163932
7. Aichinger, E., Mudrinski, N., & Opršal, J. (2018). Complexity of term representations of finitary functions. Int. J. Algebra Comput., 28(6), 1101–1118. arXiv:1709.01759, doi:10.1142/​S0218196718500480
8. Barto, L., Opršal, J., & Pinsker, M. (2018). The wonderland of reflections. Israel Journal of Mathematics, 223(1), 363–398. arXiv:1510.04521, doi:10.1007/​s11856-017-1621-9
9. Opršal, J. (2018). Taylor’s modularity conjecture and related problems for idempotent varieties. Order, 35(3), 433–460. arXiv:1602.08639, doi:10.1007/​s11083-017-9441-4
10. Donovan, D. M., Griggs, T. S., McCourt, T. A., Opršal, J., & Stanovský, D. (2016). Distributive and anti-distributive Mendelsohn triple systems. Canadian Mathematical Bulletin, 59(1), 36–49. arXiv:1411.5194, doi:10.4153/CMB-2015-053-2
11. Opršal, J. (2016). A relational description of higher commutators in Mal’cev varieties. Algebra universalis, 76(3), 367–383. arXiv:1412.5776, doi:10.1007/s00012-016-0391-2

Surveys

1. Krokhin, A., & Opršal, J. (2022). An invitation to the promise constraint satisfaction problem. ACM SIGLOG News, 9(3), 30–59. arXiv:2208.13538, doi:10.1145/​3559736.3559740