Dynamic complexity of expansion
type: Item
instance of: scholarly article
title: Dynamic complexity of expansion
DOI: 10.1007/978-3-030-79416-3_
author: Samir Datta
author: Anuj Tawari
author: Yadu Vasudev
publication date: 2022-03-21T00:00:00Z
full work available at URL: https://arxiv.org/abs/2008.05728
Mathematics Subject Classification ID: 68Qxx
zbMATH DE Number: 7493524
zbMATH Keywords: dynamic complexity
zbMATH Keywords: expansion
zbMATH Keywords: eigenvalues
zbMATH Keywords: random walks
MaRDI profile type: Publication
cites work: Low-Depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs
cites work: A More General Theory of Static Approximations for Conjunctive Queries
cites work: On uniformity within \(NC^ 1\)
cites work: Dynamic Complexity of the Dyck Reachability
cites work: Near-optimal small-depth lower bounds for small distance connectivity
cites work: Problems complete for deterministic logarithmic space
cites work: Testing Expansion in Bounded-Degree Graphs
cites work: Dynamic Complexity of Directed Reachability and Other Problems
cites work: Reachability Is in DynFO
cites work: Q5376663
cites work: Q5002805
cites work: Nonrecursive incremental evaluation of Datalog queries
cites work: On Testing Expansion in Bounded-Degree Graphs
cites work: Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two
cites work: The dynamic complexity of transitive closure is in DynTC\(^{0}\).
cites work: Uniform constant-depth threshold circuits for division and iterated multiplication.
cites work: Q5614003
cites work: Expressibility and Parallel Complexity
cites work: An Expansion Tester for Bounded Degree Graphs
cites work: Q5276194
cites work: Dyn-FO: A parallel, dynamic complexity class
cites work: Q5874224
cites work: Dynamic Complexity under Definable Changes
cites work: The dynamic descriptive complexity of \(k\)-clique
cites work: On the quantifier-free dynamic complexity of reachability
description: scientific article; zbMATH DE number 7493524