Dynamic complexity of expansion
From MaRDI portal
Publication:2117075
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
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
