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–2022), Durham University (2018–2021), TU Dresden (2016–2018), 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

MFCS 2025 Programme Committee

Warsaw, Poland

Dagstuhl 25211: The Constraint Satisfaction Problem: Complexity and Approximability

18–23 May 2025

107th Workshop on general Algebra AAA107

Bern, Switzerland, 20–23 June 2025

recent & selected papers

Meyer, S., & Opršal, J. (2024).

A topological proof of the Hell–Nešetřil dichotomy

Accepted to SODA 2025!

arXiv:2409.12627

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

Preprints

1. Meyer, S., & Opršal, J. (2024). A topological proof of the Hell–Nešetřil dichotomy. arXiv:2409.12627

Conference publications

1. 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.
2. 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.
3. 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.
4. 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
5. 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
6. 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
7. 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
8. 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
9. 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