publications

(all.bib)

Surveys

  1. with Andrei Krokhin, Invitation to the Promise Constraint Satisfaction Problem, SIGLOG News 9(3), July 2022, 30–59, doi:10.1145⁄3559736.3559740. arXiv:2208.13538 (bib)

Conference papers

  1. with Venkatesan Guruswami, Sai Sandeep, Revisiting Alphabet Reduction in Dinur’s PCP, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020), 34:1–34:14, doi:10.4230/LIPIcs.APPROX/RANDOM.2020.34. (bib)
  2. 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. (bib)
  3. 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. (bib)
  4. 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. (bib)
  5. 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. (bib)
  6. 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. arXiv:1406.5895 (bib)

Journal Papers

  1. with Andrei Krokhin, Marcin Wrochna, Standa Živný, Topology and adjunction in promise constraint satisfaction, arXiv:2003.11351. (accepted to SICOMP) (bib)
  2. with Libor Barto, Jakub Bulín, Andrei Krokhin, Algebraic approach to promise constraint satisfaction, J. ACM 68, 4, Article 28 (July 2021), 66 pages. doi:10.1145/3457606. (bib)
  3. with Manuel Bodirsky, Antoine Mottet, Miroslav Olšák, Michael Pinsker, Ross Willard, ω-categorical structures avoiding height 1 identities, Transactions of the AMS 374 pp 327—350 (2021), doi:10.1090/tran/8179. arXiv:2006.12254. (bib)
  4. with Alexandr Kazda, Matt Valeriote, Dmitriy Zhuk, Deciding the existence of minority terms, Canadian Mathematical Bulletin, doi:10.4153/S0008439519000651, arXiv:1901.00316. (bib)
  5. 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. (bib)
  6. 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. arXiv:1709.01759 (bib)
  7. 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. (bib)
  8. 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. (bib)
  9. A relational description of higher commutators in Mal’cev algebras, Algebra Univers. (2016), 76: 367–383. doi:10.1007/s00012-016-0391-2. arXiv:1412.5776. (bib)
  10. 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. (bib)

Talks

(Invited talks are bold.)