Characterizing Valiant’s Algebraic Complexity Classes

DOI10.1007/11821069_61zbMath1132.68416OpenAlexW1826226336MaRDI QIDQ5756717

Natacha Portier, Guillaume Malod

Publication date: 5 September 2007

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

Full work available at URL: https://doi.org/10.1007/11821069_61

zbMATH Keywords

polynomialsarithmetic circuitsPermanentDeterminantskew circuitsAlgebraic complexityValiant's theory

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (9)

On the expressive power of CNF formulas of bounded tree- and clique-width ⋮ On the Expressive Power of Permanents and Perfect Matchings of Matrices of Bounded Pathwidth/Cliquewidth (Extended Abstract) ⋮ On the closures of monotone algebraic classes and variants of the determinant ⋮ On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices ⋮ The complexity of two problems on arithmetic circuits ⋮ Lower Bounds for Syntactically Multilinear Algebraic Branching Programs ⋮ On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth/cliquewidth ⋮ Simulation of Arithmetical Circuits by Branching Programs with Preservation of Constant Width and Syntactic Multilinearity ⋮ VPSPACE and a transfer theorem over the complex field

This page was built for publication: Characterizing Valiant’s Algebraic Complexity Classes