Jakub Opršal

I am currently 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.

Research Interests

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

In the current project, we study how certain high-dimensional symmetries and their abstract properties influence computational complexity of constraint satisfaction problems, and their various approximation variants.

Preprints

My preprints on arXiv.

  1. with Venkatesan Guruswami, Sai Sandeep, Revisiting Alphabet Reduction in Dinur's PCP, ECCC:TR19-092.
  2. 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.
  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.
  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 A. Carpi, G. Fici Š. Holub, M. 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 Alexandr Kazda, Matt Valeriote, Dmitriy Zhuk, Deciding the existence of minority terms, accepted to Canadian Mathematical Bulletin, doi:10.4153/S0008439519000651, arXiv:1901.00316.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. A relational description of higher commutators in Mal’cev algebras, Algebra Univers. (2016), 76: 367–383. doi:10.1007/s00012-016-0391-2.
  7. 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