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.

---