Characterizing Valiant’s Algebraic Complexity Classes

DOI10.1007/11821069_61MaRDI QIDQ5756717zbMATH OpenOpenAlexFDO

Authors 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

Algebraic complexityarithmetic circuitsDeterminantPermanentpolynomialsskew circuitsValiant's theory

Mathematics Subject Classification ID

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

Recommendations

• Characterizing Valiant's algebraic complexity classes
• scientific article; zbMATH DE number 1136078
• Cook's versus Valiant's hypothesis
• scientific article; zbMATH DE number 1375589
• Interpolation in Valiant's theory

Cited in

(26)

• VPSPACE and a transfer theorem over the complex field
• Dual VP classes
• The complexity of two problems on arithmetic circuits
• Characterizing Valiant's algebraic complexity classes
• Algebraic complexity classes
• Dual VP classes
• Succinct algebraic branching programs characterizing non-uniform complexity classes
• Small-Space Analogues of Valiant’s Classes
• 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)
• Circuits arithmétiques et calculs tensoriels
• Lower Bounds for Syntactically Multilinear Algebraic Branching Programs
• scientific article; zbMATH DE number 1375589 (Why is no real title available?)
• scientific article; zbMATH DE number 1136078 (Why is no real title available?)
• Interpolation in Valiant's theory
• scientific article; zbMATH DE number 1796947 (Why is no real title available?)
• Boundaries of VP and VNP
• Noncommutative Valiant's classes: structure and complete problems
• On algebraic branching programs of small width
• Closure results for polynomial factorization
• On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices
• A la recherche de la definition de la complexite d'espace pour le calcul des polynomes a la maniere de Valiant
• 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
• \textsf{VNP} = \textsf{VP} in the multilinear world
• On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth/cliquewidth

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5756717)