Resource trade-offs in syntactically multilinear arithmetic circuits
DOI10.1007/S00037-013-0072-XzbMATH Open1286.68135OpenAlexW2094903317MaRDI QIDQ371194FDOQ371194
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
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
algebraic branching programsarithmetic circuitscircuit widthsyntactic multilinearityValiant's classes
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)
Cites Work
- Nondeterministic \(NC^1\) computation
- On uniformity within \(NC^ 1\)
- Computing Algebraic Formulas Using a Constant Number of Registers
- Title not available (Why is that?)
- Title not available (Why is that?)
- Characterizing Valiant's algebraic complexity classes
- On lower bounds for read-\(k\)-times branching programs
- Completeness and reduction in algebraic complexity theory
- Fast Parallel Computation of Polynomials Using Few Processors
- Lower bounds on arithmetic circuits via partial derivatives
- Separation of multilinear circuit and formula size
- A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
- Title not available (Why is that?)
- Multi-linear formulas for permanent and determinant are of super-polynomial size
- Bounded-width polynomial-size Boolean formulas compute exactly those functions in AC\(^ 0\)
- Balancing syntactically multilinear arithmetic circuits
- Simulation of Arithmetical Circuits by Branching Programs with Preservation of Constant Width and Syntactic Multilinearity
- 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
- Title not available (Why is that?)
- Title not available (Why is that?)
- Expressing a fraction of two determinants as a determinant
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)
