My work lies at the interface of mathematics and computer science. I study constraint satisfaction problems and their approximation and promise variants using universal algebra, homotopy theory, combinatorics, and logic.

I was a post-doc at ISTA (2022–23) in Austria, Oxford (2021–2022) and Durham University (2018–2021) in the UK, at TU Dresden (2016–2018) in Germany, and at Jagiellonian University (2016) in Poland. I had a chance to work on two ERC grants: Standa Živný’s Starting Grant ‘PowAlgDO’ and Manuel Bodirsky’s Consolidator Grant ‘CSP-Infinity’.

I received my PhD at Charles University in Prague on 29 Feb 2016. My advisor was Libor Barto.

upcoming

22–28 Sep 2024

CSP World Congress, Colfosco, Italy.

30 Mar–4 Apr 2025

Dagstuhl 25141: Categories for Automata and Language Theory, Dagstuhl, Germany.

18–23 May 2025

Dagstuhl 25211: The Constraint Satisfaction Problem: Complexity and Approximability, Dagstuhl, Germany.

recent & selected papers

Dalmau, V., & Opršal, J. (2024).

Local consistency as a reduction between constraint satisfaction problems

LICS 2024, 29:1–15.

arXiv:2301.05084, doi:10.1145/​3661814.​3662068.

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

STACS 2024, 34:1–19.

arXiv:2312.12981, doi:10.4230/​LIPIcs.STACS.​2024.34.

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

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. 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