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 and AHM; statement on how I use AI in my research.

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

students

Pankaj Kumar (2026–), Juan Martín Fajardo (2026–)

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.