ELC Seminar (C01)
Date: July 1st
Time: 10:00-12:00
Place: CELC Seminar room (Rm.404)

Speaker: P.D. Arnish Mukherjee(Chennai Mathematical Institute)
Title : The Dynamic Complexity of Reachability and Related Problems.

Abstract : 
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 of reducing
(re-)computation time. Another option is to investigate it from the
perspective of low-level parallel computational complexity.
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 maintained dynamically with
first-order predicate logic (DynFO). The dynamic complexity framework
independently introduced by Dong, Su and Topor as well as Patnaik and
Immerman models this setting.
Very recently we have shown that the Reachability query can be
maintained in DynFO, confirming a two decade old conjecture of Patnaik
and Immerman. After introducing the dynamic complexity framework and
surveying previous upper and lower bounds for the Reachability query
and related problems briefly, I will present the main ideas of the
proof of this result.

The talk is based on joint work with Samir Datta, Raghav Kulkarni,
Thomas Schwentick and Thomas Zeume.


Speaker: P.D. Swagato Sanyal(Tata Institute of Fundamental Research)
Title: Fourier Dimension and Sparsity

Abstract: 
We prove that the Fourier dimension of any Boolean function with
Fourier sparsity $s$ is at most $O\left(\sqrt{s} \log s\right)$. 
This bound is tight up to a factor of $O(\log s)$ as the Fourier 
dimension and sparsity of the addressing function are quadratically
related. We obtain our result by bounding the non-adaptive parity 
decision tree complexity, which is known to be equivalent to the 
Fourier dimension. A consequence of our result is that XOR functions
have a one way deterministic communication protocol of communication 
complexity $O(\sqrt{r} \log r)$, where $r$ is the rank of its communication matrix.