Small space analogues of Valiant's classes and the limitations of skew formulas

DOI10.1007/s00037-011-0024-2zbMath1279.68083OpenAlexW2012433578MaRDI QIDQ1947043

B. V. Raghavendra Rao, Meena Mahajan

Publication date: 11 April 2013

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-011-0024-2

zbMATH Keywords

algebraic branching programsarithmetic circuitsspace complexitycircuit widthValiant's classes

Mathematics Subject Classification ID

Related Items (3)

On Hard Instances of Non-Commutative Permanent ⋮ On hard instances of non-commutative permanent ⋮ On the power of algebraic branching programs of width two

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• VPSPACE and a transfer theorem over the reals
• On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth/cliquewidth
• VPSPACE and a transfer theorem over the complex field
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Graph-theoretic properties in computational complexity
• Nondeterministic \(NC^1\) computation
• Completeness and reduction in algebraic complexity theory
• Characterizing Valiant's algebraic complexity classes
• Division in logspace-uniformNC¹
• Small-Space Analogues of Valiant’s Classes
• On polynomial-time truth-table reducibility of intractable sets to P-selective sets
• Simulation of Arithmetical Circuits by Branching Programs with Preservation of Constant Width and Syntactic Multilinearity
• Balancing Bounded Treewidth Circuits
• Arithmetizing Classes Around NC 1 and L
• Lower Bounds for Syntactically Multilinear Algebraic Branching Programs
• On Lower Bounds for Constant Width Arithmetic Circuits
• Circuit Definitions of Nondeterministic Complexity Classes
• On Relating Time and Space to Size and Depth
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• Expressing a fraction of two determinants as a determinant
• Computational Complexity
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• Logical Approaches to Computational Barriers
• Depth-3 arithmetic circuits over fields of characteristic zero

This page was built for publication: Small space analogues of Valiant's classes and the limitations of skew formulas