Work in progress
- with Victor Dalmau, Local consistency as a reduction between constraint satisfaction problems. arXiv:2301.05084 (bib)
- with Andrei Krokhin and Victor Dalmau, Functors on relational structures which admit both left and right adjoints.
Surveys
- 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
- 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. . (bib)APPROX/RANDOM. 2020.34 - 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) - 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) - 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) - 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) - 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
- with Andrei Krokhin, Marcin Wrochna, Standa Živný, Topology and adjunction in promise constraint satisfaction, arXiv:2003.11351. (accepted to SICOMP) (bib)
- 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) - 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/ . arXiv:2006.12254. (bib)8179 - with Alexandr Kazda, Matt Valeriote, Dmitriy Zhuk, Deciding the existence of minority terms, Canadian Mathematical Bulletin, doi:10.4153/
S0008439519000651 , arXiv:1901.00316. (bib) - 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) - 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) - 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) - Taylors modularity conjecture and related problems for idempotent varieties, Order 35(2018) no. 3: pp 433–460. doi:10.1007/
s11083- . http://rdcu.be/yAo1. (bib)017- 9441- 4 - 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) - 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.)
- Topological characterisation of varieties with meet-semidistributive congruences, Panglobal Algebra and Logic Seminar (PALS), online, 15 Nov 2022. (abstract & video) (notes)
- Datalog reductions between constraint satisfaction problems, Structure Meets Power 2022 (ICALP 2022 Workshop), Paris, 4 Jul 2022. (slides)
- An introduction to promise CSP, free structures, and minions, Dagstuhl Seminar 22201, 16 May 2022.
- 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. (slides/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, Siena, 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)