jakub opršal

Assistant Professor @ University of Birmingham

j.oprsal -at- bham.ac.uk

news

14 Dec 2023 talk @ Midlands Graduate School Christmas Seminar, Birmingham, UK.

1 Dec 2023 Funding available for PhD studentship(s) in Birmingham! If you’d like to work with me on a theory of complexity of (promise) CSPs, please get in touch.

18 Jul 2023 talk An invitation to promise constraint satisfaction @ Resources and Co-resources workshop, Cambridge, UK. (slides)

latest blog posts

Yoneda Lemma in promise CSP (3 Jul 2023)

The promised open problems (3 Jan 2021)

selected papers

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

Local consistency as a reduction between constraint satisfaction problems

Preprint. arXiv:2301.05084.

Krokhin, A., & Opršal, J. (2019).

The complexity of 3-colouring H-colourable graphs.

60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019 (pp. 1227–1239). arXiv:1904.03214, doi:10.1109/FOCS.2019.00076

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

about

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 an IST-Bridge Fellow at ISTA with a project ‘Topology and the complexity of approximate graph colouring’ supported by MSCA (2022–2023). Before that I went through a few post positions at 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.

publications

Preprints

  1. ten Cate, B., Dalmau, V., & Opršal, J. (2023). Right-Adjoints for Datalog Programs, and Homomorphism Dualities over Restricted Classes. arXiv:2302.06366.
  2. Dalmau, V., Krokhin, A., & Opršal, J. (2023). Functors on relational structures which admit both left and right adjoints. arXiv:2302.13657.
  3. Dalmau, V., & Opršal, J. (2023). Local consistency as a reduction between constraint satisfaction problems. arXiv:2301.05084.

Conference publications

  1. 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
  2. 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). 34th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2019 (pp. 1–12). Vancouver, BC, Canada: IEEE. arXiv:1901.04237, doi:10.1109/LICS.2019.8785883
  3. Bulín, J., Krokhin, A., & Opršal, J. (2019). Algebraic approach to promise constraint satisfaction. Proceedings of the 51st Annual ACM SIGACT Symposium on the Theory of Computing (STOC ’19). New York, NY, USA: ACM. doi:10.1145/3313276.3316300
  4. Krokhin, A., & Opršal, J. (2019). The complexity of 3-colouring H-colourable graphs. 60th IEEE Annual 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
  5. Dalmau, V., Kozik, M., Krokhin, A., Makarychev, K., Makarychev, Y., & Opršal, J. (2017). Robust algorithms with polynomial loss for near-unanimity CSPs. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 (pp. 340–357). Barcelona, Spain: SIAM. doi:10.1137/1.9781611974782.22
  6. Carpi, A., Fici, G., Holub, Š., Opršal, J., & Sciortino, M. (2014). Universal Lyndon words. Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014 (pp. 135–146). Budapest, Hungary: Springer. doi:10.1007/978-3-662-44522-8_12

Journal papers

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

(all.bib)

talks

2023

2022

2021

2020

until 2019

organisation of conferences, workshops, and seminars