Nie jesteś zalogowany | zaloguj się

Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego

  • Skala szarości
  • Wysoki kontrast
  • Negatyw
  • Podkreślenie linków
  • Reset

Aktualności — Wydarzenia

PhD Open


Slightly Infinite Sets

Prelegent: Mikołaj Bojańczyk

2019-05-23 14:15

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: