Logic Seminar
Ioannis Eleftheriadis
University of Cambridge
Model-theoretic insights to algorithmic tractability
Abstract: Abstract: Algorithmic meta-theorems are uniform results in complexity theory that simultaneously yield an efficient solution to a wide class of computational problems, typically those expressible by a sentence of a certain logic. In the context of graphs, various research programmes have identified combinatorial conditions that provide dividing lines for the existence of uniform algorithmic results, such as the graph minors theory of Robertson and Seymour, the sparsity theory of Nesetril and Ossona de Mendez, and the twin-width theory of Bonnet et al. Recent years have seen the emergence of model-theoretic techniques in unifying these programmes and understanding the most general conditions that effectuate algorithmic tractability. This talk will survey the structural tractability programme, and present recent progress towards a conjecture that places monadic NIP as the limit to algorithmic tractability for first-order expressible problems. This is based on joint work with Jan Dreier, Nikolas Mahlmann, Rose McCarty, Michal Pilipczuk, and Szymon Torunczyk (FOCS 2024).
Tuesday October 29, 2024 at 4:00 PM in 636 SEO