Abstract: Besides its role in foundations of mathematics and establishing limits of formal reasoning, logic has found applications in several areas of computer science, such as formal verification, algorithmics and computational complexity theory. In the talk we will discuss how tools from logic and model theory can be used to find many efficient algorithms for many problems by proving a single theorem. The results of this kind are called algorithmic meta-theorems and have been studied extensively in the past 20 years. We will give an overview of these results, discuss recent developments in the field and show how the search for more general meta-theorems can motivate new notions and results in structural graph theory.

Short Bio: Jakub Gajarsky is currently a postdoctoral researcher at Technical University Berlin. His research revolves around logic, finite model theory, structural graph theory and parameterized algorithms. Currently he is mainly interested in improving our understanding of structurally simple non-sparse graphs and using this understanding to design efficient algorithms on them.