The LSV seminar takes place on Tuesday at 11:00 AM. The usual location is the conference room at Pavillon des Jardins (venue). If you wish to be informed by e-mail about upcoming seminars, please contact Stéphane Le Roux and Matthias Fuegger.
The seminar is open to public and does not require any form of registration.
In most real-life databases data changes frequently and thus makes efficient query answering challenging. Auxiliary data might help to avoid computing query answers from scratch all the time. One way to study this incremental maintenance scenario is from the perspective of dynamic algorithms with the goal to reduce (re-)computation time. Another option is to investigate it from the perspective of low-level parallel computational complexity  or parallelizable database queries . As the "lowest" complexity class AC^0 (with a suitable unifomity condition) and the core of the standard database query language SQL both coincide with first-order predicate logic, one naturally arrives at the question which queries can be answered/maintained dynamically with first-order predicate logic (DynFO).
The most intensely investigated query in Dynamic Complexity is the reachability query on graphs (arguably the "simplest recursive" query). It has been shown that it can be maintained in DynFO on undirected  or acyclic directed graphs  and on directed embedded planar graphs . Recently it could be shown that it can be maintained in DynFO, for the class of all directed graphs.
The talk will give an introduction into dynamic complexity, survey some of its most important results, and report about recent work on fragments of DynFO.
 Sushant Patnaik and Neil Immerman. Dyn-FO: A parallel, dynamic complexity class. J. Comput. Syst. Sci., 55(2):199--209, 1997.
 Guozhu Dong and Jianwen Su. Incremental and decremental evaluation of transitive closure by first-order queries. Inf. Comput., 120(1):101--106, 1995.
 Samir Datta, William Hesse and Raghav Kulkarni. Dynamic Complexity of Directed Reachability and Other Problems. ICALP 2014.