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

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)

Cites Work

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

Cited In (5)

• Interactive proofs and a Shamir-like result for real number computations
• Succinct Algebraic Branching Programs Characterizing Non-uniform Complexity Classes
• Monotone classes beyond VNP
• Une dualité entre fonctions booléennes
• 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)