Dynamic complexity of expansion

DOI10.1007/978-3-030-79416-3_MaRDI QIDQ2117075

Yadu Vasudev, Anuj Tawari, Samir Datta

Publication date: 21 March 2022

Full work available at URL: https://arxiv.org/abs/2008.05728

zbMATH Keywords

expansioneigenvaluesrandom walksdynamic complexity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Dyn-FO: A parallel, dynamic complexity class
• The dynamic complexity of transitive closure is in DynTC\(^{0}\).
• Uniform constant-depth threshold circuits for division and iterated multiplication.
• Nonrecursive incremental evaluation of Datalog queries
• The dynamic descriptive complexity of \(k\)-clique
• On the quantifier-free dynamic complexity of reachability
• On uniformity within \(NC^ 1\)
• Low-Depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs
• Dynamic Complexity of the Dyck Reachability
• On Testing Expansion in Bounded-Degree Graphs
• Dynamic Complexity under Definable Changes
• A More General Theory of Static Approximations for Conjunctive Queries
• Problems complete for deterministic logarithmic space
• Expressibility and Parallel Complexity
• Reachability Is in DynFO
• Testing Expansion in Bounded-Degree Graphs
• Dynamic Complexity of Directed Reachability and Other Problems
• Near-optimal small-depth lower bounds for small distance connectivity
• Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two
• An Expansion Tester for Bounded Degree Graphs

This page was built for publication: Dynamic complexity of expansion