Nie jesteś zalogowany | Zaloguj się

Lower bounds in Dynamic Complexity

Prelegent(ci)
Thomas Zeume
Afiliacja
Uniwersytet Warszawski
Termin
31 maja 2017 14:15
Pokój
p. 5870
Seminarium
Seminarium „Teoria automatów”

Unconditional lower bounds are are hard to prove. For this
reason recent work on inexpressibility for dynamic complexity has been
centered around fragments of DynFO (i.e. the class of queries
maintainable using first-order formulas). In this talk I will survey the
state of the art of dynamic lower bounds, with a strong focus on the
quantifier-free fragment of DynFO.