Skip to main content

Publications

Publications

Preprints

  1. with Andrei KrokhinMarcin WrochnaStanda ŽivnýTopology and adjunction in promise constraint satisfactionarXiv:2003.11351.

Conference papers

  1. with Venkatesan GuruswamiSai SandeepRevisiting 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.
  2. with Andrei KrokhinThe complexity of 3-colouring H-colourable graphs, IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS 2019), doi:10.1109/FOCS.2019.00076arXiv:1904.03214.
  3. with Manuel BodirskyAntoine Mottet, Miroslav Olšák, Michael PinskerRoss WillardTopology 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.8785883arXiv:1901.04237.
  4. with Jakub BulínAndrei KrokhinAlgebraic 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.
  5. with Víctor DalmauMarcin KozikAndrei KrokhinKonstantin MakarychevYury MakarychevRobust algorithms with polynomial loss for near-unanimity CSPs, Proceeding on 28th ACM-SIAM Symp. on Discrete Algorithms, doi:10.1137/1.9781611974782.22.
  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.

Journal papers

  1. with Libor BartoJakub BulínAndrei KrokhinAlgebraic approach to promise constraint satisfaction, J. ACM 68, 4, Article 28 (July 2021), 66 pages. doi:10.1145/3457606.
  2. with Manuel BodirskyAntoine Mottet, Miroslav Olšák, Michael PinskerRoss Willardω-categorical structures avoiding height 1 identities, Transactions of the AMS Vol. 374 (2021), pp. 327–350, doi:10.1090/tran/8179arXiv:2006.12254.
  3. with Alexandr KazdaMatt ValerioteDmitriy ZhukDeciding the existence of minority terms, Canadian Mathematical Bulletin, doi:10.4153/S0008439519000651arXiv:1901.00316.
  4. with Víctor DalmauMarcin KozikAndrei KrokhinKonstantin MakarychevYury MakarychevRobust algorithms with polynomial loss for near-unanimity CSPs, SIAM J. Comput. 48(6) (2019), pp. 1763–1795, doi:10.1137/18M1163932arXiv:1607.04787.
  5. with Erhard AichingerNebojša MudrinskiComplexity of term representations of finitary functions, Int. J. of Algebra and Computation. Vol. 28, No. 06, pp. 1101–1118 (2018) doi:10.1142/S0218196718500480.
  6. with Libor BartoMichael PinskerThe wonderland of reflections, Isr. J. Math. (2018) 223: pp 363–398. doi:10.1007/s11856-017-1621-9http://rdcu.be/zYj8.
  7. Taylors modularity conjecture and related problems for idempotent varieties, Order 35(2018) no. 3: pp 433–460. doi:10.1007/s11083-017-9441-4http://rdcu.be/yAo1.
  8. A relational description of higher commutators in Mal’cev algebras, Algebra Univers. (2016), 76: 367–383. doi:10.1007/s00012-016-0391-2.
  9. 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

(Invited talks are bold.)

  • Algebraic topology and constraint satisfaction, AAA 101, 4–6 June, 2021. (slides)
  • Promises, constraint satisfaction, and problems: Beyond universal algebra, AAA 100, 6–7 Feb, 2021. (part I) (part II)
  • The future of promises, CSP World Congress 2020, Völs am Schlern, IT, 21 Sep, 2020.
  • Revisiting Alphabet Reduction in Dinur’s PCP, APPROX 2020 (online). (video on yt)
  • The complexity of 3-colouring H-colourable graphs, FOCS 2019, Baltimore, US, 12 Nov, 2019. (video on yt) (slides)
  • Some very weak height 1 identities, AAA 97, Wien, Austria, 2 Mar, 2019. (slides)
  • Promise constraint satisfaction, SSAOS, Špindlerův mlýn, Czech Republic, 4 Sep, 2018. (slides)
  • Blockers of linear Mal’cev conditions, First Algebra Week, Sienna, Italy, 20 Jun, 2018.
  • An algebraic view on promise constraint satisfaction and hardness of coloring a d-colorable graph with 2d-1 colors, Schloß Dagstuhl, 5 Jun, 2018. (slides)