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.

I support TCS4F.

upcoming travels

Symmetry in Efficient Computation with Local Constraints

Simons Institute, Berkeley, US, March–April 2027

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

organising workshops, conferences, & seminars

• Durham Symposium 117, Durham, UK, 13–17 April 2026.
• 42nd British Colloquium for Theoretical Computer Science, Birmingham, UK, 30 March–1 April 2026.
• 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.

program committees

• LICS 2027, ICALP 2026 (Track A), MFCS 2025

Conference publications

1. Jakl, T., Hadek, M., Opršal, J. (2026). A categorical perspective on constraint satisfaction: The wonderland of adjunctions. 41st Annual Symposium on Logic in Computer Science, LICS 2026, (pp. 54:1-54:27). Lisbon, Portugal: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. arXiv:2503.10353. doi:10.4230/LIPIcs.LICS.2026.54
2. Avvakumov, S., Filakovský, M., Opršal, J., Tasinato, G., & Wagner, U. (2025). Hardness of 4-colouring G-colourable graphs. Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, (pp. 72–83). Prague, Czechia: ACM. arXiv:2504.07592, doi:10.1145/​3717823.3718154. (pdf)
3. 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.
4. 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. (pdf)
5. 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). Paestum, Italy: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. arXiv:2302.06366, doi:10.4230/​LIPIcs.ICDT.​2024.10.
6. 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). Clermont-Ferrand, France: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. arXiv:2312.12981, doi:10.4230/​LIPIcs.STACS.​2024.34.
7. 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
8. 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
9. 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 (pdf)
10. 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
11. 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
12. 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. Filakovský, M., Nakajima, T.-V., Opršal, J., Tasinato, G., & Wagner, U. (2026). Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs. ACM Trans. Comput. Theory, 18(2), 10:1–37. doi:10.1145/​3779121. (pdf)
2. 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.
3. 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
4. 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 (pdf)
5. 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
6. 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
7. 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
8. 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
9. 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
10. 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
11. 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
12. 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

2026

• Hierarchies and reductions, CSP World Congress 2026, Livigno, Italy, 13–19 September 2026.
• Homotopy theory in complexity of the graph homomorphism problem (invited talk), MFCS 2026, Paris, France, 24–28 August 2026.
• Tutorial on an algebraic approach to constraint satisfaction, Semantics and compositionality for expressiveness and complexity (ESSLLI 2026 Workshop), Prague, Czechia, 10–14 August 2026.

2025

• A gentle introduction to the categorical approach to CSP, MFO Oberwolfach 2551: Homogeneous Structures, Germany, 14–19 December 2025.
• Homotopy theory in the complexity of homomorphism problems, TopOx Seminar, Oxford, UK, 27 November 2025.
• A topological proof of the H-colouring dichotomy, Liverpool Discrete Mathematics Colloquium, Liverpool, UK, 2–3 September 2025.
• A categorical perspective on constraint satisfaction, Category Theory 2025, Brno, 14–19 July 2025. (slides) (paper)
• Homotopy and the complexity of homomorphism problems, Logic Colloquium 2025 (special session on Logic in Computer Science), Wien, Austria, 7–11 July 2025.
• A topological approach to CSPs and some algebraic consequences (invited talk), AAA107, Bern, Switzerland, 20–22 June 2025.
• A topological proof of the H-colouring dichotomy, Finite and Algorithmic Model Theory 2025, Les Houches, France, 25–30 May 2025.
• An introduction to homomorphism complexes, Dagstuhl Serminar 25211: The Constraint Satisfaction Problem, Germany, 18–23 May 2025.
• Homotopy and complexity of graph colouring (invited talk), BCTCS 2025, Glasgow, Scotland, 14 Apr 2025.
• How are we secretely using category theory while proving hardness of satisfying constraints, Dagstuhl Seminar 25141: Categories for Automata and Language Theory, 3 Apr 2025. (paper)

2024

• Local consistency as a reduction between constraint satisfaction problems, LICS 2024, Tallinn, Estonia, 11 Jul 2024.
• NP-hardness of promise colouring graphs via homotopy, TACL 2024, Barcelona, Spain, 2 Jul 2024.

2023

• NP-hardness of colouring certain graphs with 3 colours via homotopy Midlands Graduate School Christmas Seminar, Birmingham, UK, 14 Dec 2023.
• An invitation to promise constraint satisfaction, Resources and Co-resources, Cambridge, UK, 18 Jul 2023. (slides)

2022

• Topological characterisation of varieties with meet-semidistributive congruences, Panglobal Algebra and Logic Seminar (PALS), online, 15 Nov 2022. (abstract & video) (notes)
• Datalog reductions between constraint satisfaction problems, Structure Meets Power 2022 (ICALP 2022 Workshop), Paris, France, 4 Jul 2022.
• An introduction to promise CSP, free structures, and minions (invited tutorial), Dagstuhl Seminar 22201: The Constraint Satisfaction Problem, 16 May 2022.

2021

• Algebraic topology and constraint satisfaction, AAA 101, online, 4–6 June, 2021.
• Promises, constraint satisfaction, and problems: Beyond universal algebra (invited tutorial), AAA 100, online, 6–7 Feb, 2021.

until 2020

• The future of promises, CSP World Congress 2020, Völs am Schlern, Italy, 21 Sep, 2020.
• The complexity of 3-colouring H-colourable graphs, FOCS 2019, Baltimore, US, 12 Nov, 2019. (video on yt)
• Promise constraint satisfaction (invited talk), SSAOS, Špindlerův mlýn, Czech Republic, 4 Sep, 2018.
• Blockers of linear Mal’cev conditions (invited talk), First Algebra Week, Siena, Italy, 20 Jun, 2018.
• An algebraic view on promise constraint satisfaction and hardness of coloring a d-colorable graph with 2d − 1 colors, Dagstuhl Seminar 18231: The Constraint Satisfaction Problem, 5 Jun 2018.