Resource trade-offs in syntactically multilinear arithmetic circuits
From MaRDI portal
Publication:371194
DOI10.1007/s00037-013-0072-xzbMath1286.68135OpenAlexW2094903317MaRDI 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 programsarithmetic circuitscircuit widthsyntactic multilinearityValiant's classes
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (3)
\textsf{VNP} = \textsf{VP} in the multilinear world ⋮ Algebraic Complexity Classes ⋮ On the power of algebraic branching programs of width two
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Resource trade-offs in syntactically multilinear arithmetic circuits
