Jakub Opršal

I am a post-doc at the Department of Computer Science of Durham University. Working on the project of Andrei Krokhin on The Complexity of Promise Constraint Satisfaction.

You can contact me by email at jakub.oprsal (at) durham.ac.uk.

[arXiv] [scholar] [dblp] [ORCiD]

Research Interests

My research is focused on the study of identities and equational theories in universal algebra, and applications thereof to computational complexity, constraint satisfaction, and its approximation.

In the current project, we develop new mathematical tools for promise constraint satisfaction, and in particular for approximate graph colouring. We aim to provide a general theory of reductions between these problems.

Upcoming

Until further notice — Socially distant (you know why).

Publications

Preprints

  1. with Andrei Krokhin, Marcin Wrochna, Standa Živný, Topology and adjunction in promise constraint satisfaction, arXiv:2003.11351.
  2. with Venkatesan Guruswami, Sai Sandeep, Revisiting Alphabet Reduction in Dinur’s PCP, ECCC:TR19-092.
  3. with Libor Barto, Jakub Bulín, Andrei Krokhin, Algebraic approach to promise constraint satisfaction, arXiv:1811.00970v3.

Conference papers

  1. with Andrei Krokhin, The complexity of 3-colouring H-colourable graphs, IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS 2019), doi:10.1109/FOCS.2019.00076. arXiv:1904.03214.
  2. with Manuel Bodirsky, Antoine Mottet, Miroslav Olšák, Michael Pinsker, Ross Willard, Topology is relevant (in the infinite-domain dichotomy conjecture for constraint satisfaction problems), In 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2019), doi:10.1109/LICS.2019.8785883. arXiv:1901.04237.
  3. with Jakub Bulín, Andrei Krokhin, Algebraic approach to promise constraint satisfaction, In Proceedings of the 51st Annual ACM Symp. on the Theory of Computing (STOC 2019), doi:10.1145/3313276.3316300.
  4. with Víctor Dalmau, Marcin Kozik, Andrei Krokhin, Konstantin Makarychev, Yury Makarychev, Robust algorithms with polynomial loss for near-unanimity CSPs, Proceeding on 28th ACM-SIAM Symp. on Discrete Algorithms, doi:10.1137/1.9781611974782.22.
  5. with Arthuro Carpi, Gabriele Fici, Štěpán Holub, Marinella Sciortino, Universal Lyndon Words, MFCS 2014, LNCS, Vol. 8634, 2014, pp 135–146, doi:10.1007/978-3-662-44522-8_12.

Journal Papers

  1. with Manuel Bodirsky, Antoine Mottet, Miroslav Olšák, Michael Pinsker, Ross Willard, ω-categorical structures avoiding height 1 identities, accepted to Transactions of the AMS, 2020.
  2. with Alexandr Kazda, Matt Valeriote, Dmitriy Zhuk, Deciding the existence of minority terms, Canadian Mathematical Bulletin, doi:10.4153/S0008439519000651, arXiv:1901.00316.
  3. with Víctor Dalmau, Marcin Kozik, Andrei Krokhin, Konstantin Makarychev, Yury Makarychev, Robust algorithms with polynomial loss for near-unanimity CSPs, SIAM J. Comput. 48(6) (2019), pp. 1763–1795, doi:10.1137/18M1163932. arXiv:1607.04787.
  4. with Erhard Aichinger, Nebojša Mudrinski, Complexity of term representations of finitary functions, Int. J. of Algebra and Computation. Vol. 28, No. 06, pp. 1101–1118 (2018) doi:10.1142/S0218196718500480.
  5. with Libor Barto, Michael Pinsker, The wonderland of reflections, Isr. J. Math. (2018) 223: pp 363–398. doi:10.1007/s11856-017-1621-9. http://rdcu.be/zYj8.
  6. Taylors modularity conjecture and related problems for idempotent varieties, Order 35(2018) no. 3: pp 433–460. doi:10.1007/s11083-017-9441-4. http://rdcu.be/yAo1.
  7. A relational description of higher commutators in Mal’cev algebras, Algebra Univers. (2016), 76: 367–383. doi:10.1007/s00012-016-0391-2.
  8. with D. Donovan, T. Griggs T. McCourt, D. Stanovský, Distributive and Anti-distributive Mendelsohn Triple Systems, Canadian Mathematical Bulletin 59(2016), no. 1, 36–49. doi:10.4153/CMB-2015-053-2.

Conference talks

∎