Colloquium of Faculty of Informatics

The Informatics Colloquium takes place on Tuesday at 14:30 during the term time. The aim of the colloquia is to introduce state of the art research from all areas of computer science to the wide audience of the Faculty of Informatics.

Robert Ganian
Mapping the Complexity-Theoretic Landscapes of Artificial Intelligence
Tuesday 10 October 2023, 14:30, lecture hall A217

‍Over the past few decades, there has been a concentrated and highly successful scientific effort aimed at identifying the boundaries of theoretical tractability for classical computational problems such as Boolean Satisfiability, Model Checking, Constraint Satisfaction and a variety of fundamental graph problems. Indeed, today we can use the parameterized refinement of complexity theory along with a variety of other cutting-edge tools to draw detailed complexity-theoretic landscapes capturing when these problems are tractable and when they are, at least under well-established assumptions, "hard". However, the rapid ascent of Artificial Intelligence has led to the identification of entirely new kinds of important computational problems, and our understanding of when these can be solved efficiently is in many cases still in its infancy.In this high-level talk, we will explore selected new developments in mapping the landscapes of tractability for fundamental problems in several subfields of Artificial Intelligence, including recommender systems and machine learning. The talk will include an introduction to the foundations of parameterized complexity theory and will cover new algorithms and lower bounds for matrix completion problems as well as the recently introduced parameterized refinement of PAC-learning. The talk starts at 14:30 in room A217 and is preceded by an informal discussion with the speaker in room A220 (from 14:00).