Resource trade-offs in syntactically multilinear arithmetic circuits

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

zbMATH Keywords

algebraic branching programsarithmetic circuitscircuit widthsyntactic multilinearityValiant's classes

Mathematics Subject Classification ID

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

Related Items

\textsf{VNP} = \textsf{VP} in the multilinear world, Algebraic Complexity Classes, On the power of algebraic branching programs of width two

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