Logic in algorithmics and structural graph theory
- Speaker: Dr. Jakub Gajarsky, Logic and Semantics Research Group, TU Berlin, Germany.
- Date: Tuesday, 12 February 2019 from 17:00 to 18:00
- Location: Room 151
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 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.