publications

(all.bib)

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.

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.¹¹⁴⁵⁄_3559736.3559740

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.¹¹⁴⁵⁄_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

Talks

(Invited talks are bold.)

• 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, 4 Jul 2022. (slides)
• An introduction to promise CSP, free structures, and minions, Dagstuhl Seminar 22201, 16 May 2022.
• Algebraic topology and constraint satisfaction, AAA 101, 4–6 June, 2021. (slides)
• Promises, constraint satisfaction, and problems: Beyond universal algebra, AAA 100, 6–7 Feb, 2021. (slides/part i) (part ii)
• The future of promises, CSP World Congress 2020, Völs am Schlern, IT, 21 Sep, 2020.
• Revisiting Alphabet Reduction in Dinur’s PCP, APPROX 2020 (online). (video on yt)
• The complexity of 3-colouring H-colourable graphs, FOCS 2019, Baltimore, US, 12 Nov, 2019. (video on yt) (slides)
• Some very weak height 1 identities, AAA 97, Wien, Austria, 2 Mar, 2019. (slides)
• Promise constraint satisfaction, SSAOS, Špindlerův mlýn, Czech Republic, 4 Sep, 2018. (slides)
• Blockers of linear Mal’cev conditions, 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, Schloß Dagstuhl, 5 Jun, 2018. (slides)