Simulation of Arithmetical Circuits by Branching Programs with Preservation of Constant Width and Syntactic Multilinearity
From MaRDI portal
Publication:3392953
DOI10.1007/978-3-642-03351-3_18zbMATH Open1248.68207OpenAlexW1580862938MaRDI QIDQ3392953FDOQ3392953
Authors: 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
Recommendations
- Resource trade-offs in syntactically multilinear arithmetic circuits
- Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae
- Towards optimal simulations of formulas by bounded-width programs
- Lower Bounds for Syntactically Multilinear Algebraic Branching Programs
- Balancing bounded treewidth circuits
Cites Work
- Nondeterministic \(NC^1\) computation
- Title not available (Why is that?)
- Computing Algebraic Formulas Using a Constant Number of Registers
- Completeness and reduction in algebraic complexity theory
- Fast Parallel Computation of Polynomials Using Few Processors
- Lower bounds and separations for constant depth multilinear circuits
- Lower Bounds for Syntactically Multilinear Algebraic Branching Programs
- Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae
- Reducibility by algebraic projections
- Characterizing Valiant’s Algebraic Complexity Classes
- Multi-linear formulas for permanent and determinant are of super-polynomial size
Cited In (7)
- On the power of algebraic branching programs of width two
- Resource trade-offs in syntactically multilinear arithmetic circuits
- Small space analogues of Valiant's classes and the limitations of skew formulas
- Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae
- \textsf{VNP} = \textsf{VP} in the multilinear world
- Skew circuits of small width
- Balancing bounded treewidth circuits
This page was built for publication: Simulation of Arithmetical Circuits by Branching Programs with Preservation of Constant Width and Syntactic Multilinearity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3392953)
