Slightly infinite sets
Mikołaj Bojańczyk
(University of Warsaw).
Course Summary |
About the lecturer |
Location and schedule |
Materials |
Assignment
This lecture is about algorithms which work on objects that are infinite, but still finite enough to admit methods like exhaustive search. For example, one can consider graphs with infinitely many vertices, and where the edge relation is represented in some kind of finite way (e.g. by a formula of logic). Under certain assumptions on the input graph (roughly speaking, it needs to be finite up to automorphisms), exhaustive search works. For inputs which satisfy these assumptions, natural problems from discrete mathematics, like graph reachability, become decidable. The underlying theory depends on constructions from model theory, such as the Fraisse limit, or the Ryll-Nardzewski theorem about oligomorphic structures. The lecture is be based on the following book: link.
About the lecturer:Mikołaj Bojańczyk (born 1977, phd 2004) works on the foundations of computer science at the University of Warsaw, where he is a full professor. He has been in Warsaw since his undergraduate studies, excluding shorter trips and a one year postdoc in Paris (Université Paris Diderot-Paris 7). He is interested in finite model theory and algebraic language theory, but most of all in the interplay between automata and logic. The automata are usually finite state, but may process more fancy objects than words, like graphs or infinite trees. The logic is typically some variant of monadic second-order logic. He has been awarded early career awards: Ackermann (2005), Lipski (2006), Kuratowski (2007), Presburger (2010) and the NCN Award (2016), as well as best paper awards at computer science conferences such as PODS or ICALP. He has been a Principal Investigator in an ERC Grant Sosna (Starting) and Lipa (Consolidator).
Location and schedule:5440 except for May 30.
|
|
|
|
||||||||||||||||||||||||||||||||