On the Power of Algebraic Branching Programs of Width Two
From MaRDI portal
Publication:3012846
DOI10.1007/978-3-642-22006-7_62zbMath1333.68131MaRDI QIDQ3012846
Fengming Wang, Eric W. Allender
Publication date: 6 July 2011
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-22006-7_62
68Q25: Analysis of algorithms and problem complexity
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Nondeterministic \(NC^1\) computation
- On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
- The Power of Depth 2 Circuits over Algebras
- Small-Space Analogues of Valiant’s Classes
- Simulation of Arithmetical Circuits by Branching Programs with Preservation of Constant Width and Syntactic Multilinearity
- Lower Bounds for Syntactically Multilinear Algebraic Branching Programs
- Computing Algebraic Formulas Using a Constant Number of Registers
- Word Problems Solvable in Logspace