Seminars & Colloquia
Technical University Berlin
"Logic in algorithmics and structural graph theory"
Wednesday March 27, 2019 01:30 PM
Location: 3211, EB2 NCSU Centennial Campus
(Visitor parking instructions)
This talk is part of the Theory Seminar Series
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.
Host: Blair Sullivan, CSC