You are not logged in | Log in

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.