Preprints
- Jakl, T., Hadek, M., Opršal, J. (2025).
A categorical perspective on constraint satisfaction: The wonderland of adjunctions.
arXiv:2503.10353.
Conference publications
- Avvakumov, S., Filakovský, M., Opršal, J., Tasinato, G., & Wagner, U. (2025).
Hardness of 4-colouring G-colourable graphs.
Accepted to STOC 2025.
arXiv:2504.07592.
- 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.
- 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.
- 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.
- 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.
- 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
- 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
- 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
- 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
- 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
- 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
- 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.
- 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.
arXiv:1811.00970,
doi:10.1145/3457606
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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