Now showing 1 - 1 of 1
  • Placeholder Image
    Publication
    Dynamic Complexity of Expansion
    (01-01-2021)
    Datta, Samir
    ;
    Tawari, Anuj
    ;
    Dynamic Complexity was introduced by Immerman and Patnaik [25] (see also [14]). It has seen a resurgence of interest in the recent past, see [2, 4, 8–12, 24, 26, 30, 31] 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 DynAC0 (also known as DynFO, for domain independent queries) under batch changes (insertions and deletions) of O(lognloglogn) many edges. The spectral graph theoretic material of this work is based on the paper by Kale-Seshadhri [23]. Our primary technical contribution is to maintain up to logarithmic powers of the transition matrix of a bounded degree undirected graph in DynAC0.