Slightly Infinite Sets

Speaker(s)

Mikołaj Bojańczyk

Affiliation

UW

Date

May 23, 2019, 2:15 p.m.

Room

room 5440

Seminar

PhD Open

---

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.

 

More details: http://phdopen.mimuw.edu.pl/index.php?page=l19w1.

---