Characterizing Valiant’s Algebraic Complexity Classes
From MaRDI portal
Publication:5756717
DOI10.1007/11821069_61zbMath1132.68416MaRDI 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
polynomials; arithmetic circuits; Permanent; Determinant; skew circuits; Algebraic complexity; Valiant's theory
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices, On the closures of monotone algebraic classes and variants of the determinant, 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, VPSPACE and a transfer theorem over the complex field, The complexity of two problems on arithmetic circuits, Simulation of Arithmetical Circuits by Branching Programs with Preservation of Constant Width and Syntactic Multilinearity, On the Expressive Power of Permanents and Perfect Matchings of Matrices of Bounded Pathwidth/Cliquewidth (Extended Abstract), Lower Bounds for Syntactically Multilinear Algebraic Branching Programs