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

DOI10.2178/JSL/1230396913zbMATH Open1160.03020OpenAlexW2118951952MaRDI QIDQ5502811FDOQ5502811

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

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

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)

Cites Work

• Completeness and reduction in algebraic complexity theory
• Fast Parallel Computation of Polynomials Using Few Processors
• Arithmetization: A new method in structural complexity theory
• Restructuring of Arithmetic Expressions For Parallel Evaluation
• Title not available (Why is that?)

Cited In (12)

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

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)