Dynamic Complexity was introduced by Immerman and Patnaik \cite{ PatnaikImmerman97} (see also \cite{ DongST95}). It has seen a resurgence of interest in the recent past, see \cite{ DattaHK14,ZeumeS15,MunozVZ16,BouyerJ17,Zeume17,DKMSZ18,DMVZ18,BarceloRZ18,DMSVZ19,SchmidtSVZK20,DKMTVZ20} 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 $\DynACz$ (also known as $\dynfo$, for domain independent queries) under batch changes (insertions and deletions) of $O(\frac{ \log{ n}}{ \log{ \log{ n}}})$ many edges. The spectral graph theoretic material of this work is based on the paper by Kale-Seshadri \cite{ KaleS11}. Our primary technical contribution is to maintain up to logarithmic powers of the transition matrix of a bounded degree undirected graph in $\DynACz$.
Categories: cs.CC