Dynamic complexity of expansion
From MaRDI portal
Publication:2117075
DOI10.1007/978-3-030-79416-3_MaRDI QIDQ2117075FDOQ2117075
Authors: Samir Datta, Anuj Tawari, Yadu Vasudev 
Publication date: 21 March 2022
Full work available at URL: https://arxiv.org/abs/2008.05728
Cites Work
- On uniformity within \(NC^ 1\)
- Title not available (Why is that?)
- Problems complete for deterministic logarithmic space
- Nonrecursive incremental evaluation of Datalog queries
- Uniform constant-depth threshold circuits for division and iterated multiplication.
- Expressibility and Parallel Complexity
- On testing expansion in bounded-degree graphs
- Testing Expansion in Bounded-Degree Graphs
- An expansion tester for bounded degree graphs
- A more general theory of static approximations for conjunctive queries
- Title not available (Why is that?)
- Dynamic graph queries
- Low-depth uniform threshold circuits and the bit-complexity of straight line programs
- Dyn-FO: A parallel, dynamic complexity class
- The dynamic complexity of transitive closure is in DynTC\(^{0}\).
- Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two
- On the quantifier-free dynamic complexity of reachability
- Dynamic complexity of directed reachability and other problems
- Dynamic Complexity under Definable Changes
- Reachability is in DynFO
- The dynamic descriptive complexity of \(k\)-clique
- Dynamic complexity of the Dyck reachability
- Reachability and distances under multiple changes
- Near-optimal small-depth lower bounds for small distance connectivity
- A strategy for dynamic programs: start over and muddle through
Cited In (3)
This page was built for publication: Dynamic complexity of expansion
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2117075)
