Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae

DOI10.1007/978-3-540-85238-4_37zbMath1173.68522OpenAlexW1529075126MaRDI QIDQ3599149

Meena Mahajan, B. V. Raghavendra Rao

Publication date: 3 February 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-85238-4_37

Mathematics Subject Classification ID

Related Items (4)

Resource trade-offs in syntactically multilinear arithmetic circuits ⋮ Balancing bounded treewidth circuits ⋮ \textsf{VNP} = \textsf{VP} in the multilinear world ⋮ Simulation of Arithmetical Circuits by Branching Programs with Preservation of Constant Width and Syntactic Multilinearity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Nondeterministic \(NC^1\) computation
• Bounded-width polynomial-size Boolean formulas compute exactly those functions in AC\(^ 0\)
• On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
• Completeness and reduction in algebraic complexity theory
• Balancing syntactically multilinear arithmetic circuits
• On lower bounds for read-\(k\)-times branching programs
• Fast Parallel Computation of Polynomials Using Few Processors
• Arithmetizing Classes Around NC 1 and L
• Computing Algebraic Formulas Using a Constant Number of Registers
• Circuit Definitions of Nondeterministic Complexity Classes
• Multi-linear formulas for permanent and determinant are of super-polynomial size

This page was built for publication: Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae