Dynamic complexity of expansion
From MaRDI portal
Publication:2117075
DOI10.1007/978-3-030-79416-3_MaRDI QIDQ2117075FDOQ2117075
Yadu Vasudev, Anuj Tawari, Samir Datta
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?)
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- Near-optimal small-depth lower bounds for small distance connectivity
- Title not available (Why is that?)
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)
