Options
Vasudev Yadu
Loading...
Preferred name
Vasudev Yadu
Official Name
Vasudev Yadu
Alternative Name
Vasudev, Y.
Vasudev, Yadu
Main Affiliation
Email
ORCID
Scopus Author ID
Google Scholar ID
1 results
Now showing 1 - 1 of 1
- PublicationDynamic Complexity of Expansion(01-01-2021)
;Datta, Samir ;Tawari, AnujDynamic 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.