publications

(all.bib)

Work in progress

  1. with Victor Dalmau, Local consistency as a reduction between constraint satisfaction problems. arXiv:2301.05084 (bib)
  2. with Andrei Krokhin and Victor Dalmau, Functors on relational structures which admit both left and right adjoints.

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 (SODA 2017), doi:10.1137/1.9781611974782.22. (bib)
  6. with Arthuro Carpi, Gabriele Fici, Štěpán Holub, Marinella Sciortino, Universal Lyndon Words, In Proceedings of Mathematical Foundations of Computer Science 2014 (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.)