Resource trade-offs in syntactically multilinear arithmetic circuits
From MaRDI portal
Publication:371194
DOI10.1007/s00037-013-0072-xzbMath1286.68135MaRDI QIDQ371194
B. V. Raghavendra Rao, Maurice Jansen, Meena Mahajan
Publication date: 30 September 2013
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-013-0072-x
algebraic branching programs; arithmetic circuits; circuit width; syntactic multilinearity; Valiant's classes
03D15: Complexity of computation (including implicit computational complexity)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
On the power of algebraic branching programs of width two, \textsf{VNP} = \textsf{VP} in the multilinear world, Algebraic Complexity Classes
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Nondeterministic \(NC^1\) computation
- Bounded-width polynomial-size Boolean formulas compute exactly those functions in AC\(^ 0\)
- Lower bounds on arithmetic circuits via partial derivatives
- Completeness and reduction in algebraic complexity theory
- Balancing syntactically multilinear arithmetic circuits
- On lower bounds for read-\(k\)-times branching programs
- Characterizing Valiant's algebraic complexity classes
- On uniformity within \(NC^ 1\)
- Fast Parallel Computation of Polynomials Using Few Processors
- Simulation of Arithmetical Circuits by Branching Programs with Preservation of Constant Width and Syntactic Multilinearity
- A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
- Arithmetizing Classes Around NC 1 and L
- Lower Bounds for Syntactically Multilinear Algebraic Branching Programs
- Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae
- Computing Algebraic Formulas Using a Constant Number of Registers
- Expressing a fraction of two determinants as a determinant
- Multi-linear formulas for permanent and determinant are of super-polynomial size
