Dynamic Complexity of Expansion
share
Dynamic Complexity was introduced by Immerman and Patnaik <cit.> (see also <cit.>). It has seen a resurgence of interest in the recent past, see <cit.> for some representative examples. Use of linear algebra has been a notable feature of some of these papers. We extend this theme to show that the gap version of spectral expansion in bounded degree graphs can be maintained in the class (also known as , for domain independent queries) under batch changes (insertions and deletions) of O(logn/loglogn) many edges. The spectral graph theoretic material of this work is based on the paper by Kale-Seshadri <cit.>. Our primary technical contribution is to maintain up to logarithmic powers of the transition matrix of a bounded degree undirected graph in .
READ FULL TEXT