Succinct algebraic branching programs characterizing non-uniform complexity classes

DOI10.1007/978-3-642-22953-4_18MaRDI QIDQ3088284zbMATH OpenOpenAlexFDO

Authors Guillaume Malod

Publication date 19 August 2011

Published in Fundamentals of Computation Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-22953-4_18

Mathematics Subject Classification ID

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

Recommendations

• Characterizing Valiant's algebraic complexity classes
• On algebraic branching programs of small width
• On Algebraic Branching Programs of Small Width
• Characterizing Valiant’s Algebraic Complexity Classes
• Arithmetic branching programs with memory

Cites work

• A la recherche de la definition de la complexite d'espace pour le calcul des polynomes a la maniere de Valiant
• Arithmetization: A new method in structural complexity theory
• Characterizing Valiant's algebraic complexity classes
• Circuit Definitions of Nondeterministic Complexity Classes
• Completeness and reduction in algebraic complexity theory
• Computational Complexity
• Computing Algebraic Formulas Using a Constant Number of Registers
• Counting classes and the fine structure between {\textsf{NC}}\(^{1}\) and {\textsf{L}}
• Fast Parallel Computation of Polynomials Using Few Processors
• Feasible arithmetic computations: Valiant's hypothesis
• Functions computable in polynomial space
• On Relating Time and Space to Size and Depth
• On uniform circuit complexity
• PSPACE SURVIVES CONSTANT-WIDTH BOTTLENECKS
• Small-Space Analogues of Valiant’s Classes
• Succinct representation, leaf languages, and projection reductions
• Succinct representations of graphs

Cited in

(6)

• Interactive proofs and a Shamir-like result for real number computations
• Arithmetic branching programs with memory
• Lower Bounds for Syntactically Multilinear Algebraic Branching Programs
• On Algebraic Branching Programs of Small Width
• Monotone classes beyond VNP
• Monotone classes beyond VNP

This page was built for publication: Succinct algebraic branching programs characterizing non-uniform complexity classes

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