A la recherche de la definition de la complexite d'espace pour le calcul des polynomes a la maniere de Valiant

DOI10.2178/JSL/1230396913MaRDI QIDQ5502811zbMATH OpenOpenAlexFDO

Authors Bruno Poizat

Publication date 9 January 2009

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2178/jsl/1230396913

zbMATH Keywords

circuit complexityclasses of functionsValiant circuits

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Characterizing Valiant’s Algebraic Complexity Classes
• Characterizing Valiant's algebraic complexity classes
• Feasible arithmetic computations: Valiant's hypothesis
• Circuits arithmétiques et calculs tensoriels
• Small-Space Analogues of Valiant’s Classes

Cites work

• scientific article; zbMATH DE number 2150283 (Why is no real title available?)
• Arithmetization: A new method in structural complexity theory
• Completeness and reduction in algebraic complexity theory
• Fast Parallel Computation of Polynomials Using Few Processors
• Restructuring of Arithmetic Expressions For Parallel Evaluation

Cited in

(12)

• Monotone classes beyond VNP
• Valiant's model and the cost of computing integers
• Interactive proofs and a Shamir-like result for real number computations
• A duality between Boolean functions
• Feasible arithmetic computations: Valiant's hypothesis
• Circuits arithmétiques et calculs tensoriels
• Small-Space Analogues of Valiant’s Classes
• Dual VP classes
• Succinct algebraic branching programs characterizing non-uniform complexity classes
• Characterizing Valiant's algebraic complexity classes
• Dual VP classes
• Malod and the Pascaline

This page was built for publication: A la recherche de la definition de la complexite d'espace pour le calcul des polynomes a la maniere de Valiant

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