Lower bounds in Dynamic Complexity

Speaker(s)

Thomas Zeume

Affiliation

Uniwersytet Warszawski

Date

May 31, 2017, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

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.

---