Simulation of Arithmetical Circuits by Branching Programs with Preservation of Constant Width and Syntactic Multilinearity

DOI10.1007/978-3-642-03351-3_18zbMath1248.68207OpenAlexW1580862938MaRDI QIDQ3392953

Maurice Jansen, Raghavendra Rao B. V.

Publication date: 18 August 2009

Published in: Computer Science - Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-03351-3_18

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (5)

Resource trade-offs in syntactically multilinear arithmetic circuits ⋮ Balancing bounded treewidth circuits ⋮ \textsf{VNP} = \textsf{VP} in the multilinear world ⋮ Small space analogues of Valiant's classes and the limitations of skew formulas ⋮ On the Power of Algebraic Branching Programs of Width Two

Cites Work

• Unnamed Item
• Lower bounds and separations for constant depth multilinear circuits
• Reducibility by algebraic projections
• Nondeterministic \(NC^1\) computation
• Completeness and reduction in algebraic complexity theory
• Fast Parallel Computation of Polynomials Using Few Processors
• 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
• Characterizing Valiant’s Algebraic Complexity Classes
• Multi-linear formulas for permanent and determinant are of super-polynomial size

This page was built for publication: Simulation of Arithmetical Circuits by Branching Programs with Preservation of Constant Width and Syntactic Multilinearity