论文标题
膨胀的动态复杂性
Dynamic Complexity of Expansion
论文作者
论文摘要
动态复杂性是由Immerman和Patnaik \ cite {patnaikimmeran97}引入的（另请参见\ cite {dongst95}）。在最近的过去，它引起了人们的兴趣，请参见\ cite {dattahk14，zeumes15，munozvz16，bouyerj17，zeume17，dkmsz18，dmvz18，dmvz18，barcelorz18，barcelorz18，dmsvz19，dmsvz19，dmsvz19，schmidtsvzk20，dkmtvz20，dkmtvz20，dkmtvz20，dkmtvz20，dkmtvz20，dkmtvz20，dkmtvz20，dkmtvz20，dkmtvz20，dkmtvz20，dkmtvz20，dkmtvz20，dkmtvz20，线性代数的使用一直是其中一些论文的显着特征。我们扩展了此主题，以表明可以在$ \ dynacz $（也称为$ \ dynfo $的类中的差异版本扩展）中保持在批处理更改（\ frac {\ frac {\ log {n}} $ gog} $ o（n} $ log}的$ o（插入和删除）下， 这项工作的光谱图理论材料基于羽衣甘蓝 - 夏德里\ cite {kales11}的论文。我们的主要技术贡献是维持$ \ dynacz $中有限程度的无向图的过渡矩阵的对数能力。
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$.
