Ioannis Eleftheriadis : Model-theoretic insights to algorithmic tractability

Posted by Caroline Terry , part of the Logic Seminar.

At

Oct. 29, 2024, 4 p.m.

In

636 SEO

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).