Resource trade-offs in syntactically multilinear arithmetic circuits

DOI10.1007/S00037-013-0072-XMaRDI QIDQ371194zbMATH OpenOpenAlexFDO

Authors Maurice Jansen, Meena Mahajan, B. V. Raghavendra Rao

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

zbMATH Keywords

algebraic branching programsarithmetic circuitscircuit widthsyntactic multilinearityValiant's classes

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae
• Simulation of Arithmetical Circuits by Branching Programs with Preservation of Constant Width and Syntactic Multilinearity
• Balancing syntactically multilinear arithmetic circuits
• A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
• scientific article; zbMATH DE number 7250151

Cites work

• scientific article; zbMATH DE number 3744549 (Why is no real title available?)
• scientific article; zbMATH DE number 1142309 (Why is no real title available?)
• scientific article; zbMATH DE number 1161568 (Why is no real title available?)
• scientific article; zbMATH DE number 1405642 (Why is no real title available?)
• scientific article; zbMATH DE number 3430129 (Why is no real title available?)
• A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
• Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae
• Arithmetizing Classes Around NC 1 and L
• Balancing syntactically multilinear arithmetic circuits
• Bounded-width polynomial-size Boolean formulas compute exactly those functions in AC\(^ 0\)
• Characterizing Valiant's algebraic complexity classes
• Completeness and reduction in algebraic complexity theory
• Computing Algebraic Formulas Using a Constant Number of Registers
• Expressing a fraction of two determinants as a determinant
• Fast Parallel Computation of Polynomials Using Few Processors
• Lower Bounds for Syntactically Multilinear Algebraic Branching Programs
• Lower bounds on arithmetic circuits via partial derivatives
• Multi-linear formulas for permanent and determinant are of super-polynomial size
• Nondeterministic NC^1 computation
• On lower bounds for read-\(k\)-times branching programs
• On uniformity within \(NC^ 1\)
• Separation of multilinear circuit and formula size
• Simulation of Arithmetical Circuits by Branching Programs with Preservation of Constant Width and Syntactic Multilinearity

Cited in

(5)

• On the power of algebraic branching programs of width two
• Simulation of Arithmetical Circuits by Branching Programs with Preservation of Constant Width and Syntactic Multilinearity
• Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae
• \textsf{VNP} = \textsf{VP} in the multilinear world
• Algebraic complexity classes

This page was built for publication: Resource trade-offs in syntactically multilinear arithmetic circuits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q371194)