On algebraic branching programs of small width

DOI10.4230/LIPICS.CCC.2017.20MaRDI QIDQ5111150zbMATH OpenFDO

Authors Karl Bringmann, Christian Ikenmeyer, Jeroen Zuiddam

Publication date 26 May 2020

Full work available at URL https://doi.org/10.4230/LIPICS.CCC.2017.20

zbMATH Keywords

algebraic branching programsalgebraic complexity theoryborder complexityformula sizeiterated matrix multiplication

Mathematics Subject Classification ID

Networks and circuits as models of computation; circuit complexity (68Q06) Other nonclassical models of computation (68Q09) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• On Algebraic Branching Programs of Small Width
• Characterizing Valiant’s Algebraic Complexity Classes
• Characterizing Valiant's algebraic complexity classes
• On the power of algebraic branching programs of width two
• On the power of algebraic branching programs of width two

Cited in

(11)

• On the power of algebraic branching programs of width two
• Arithmetic branching programs with memory
• On the power of algebraic branching programs of width two
• Succinct algebraic branching programs characterizing non-uniform complexity classes
• Small-Space Analogues of Valiant’s Classes
• scientific article; zbMATH DE number 36617 (Why is no real title available?)
• On Algebraic Branching Programs of Small Width
• Characterization and Lower Bounds for Branching Program Size Using Projective Dimension.
• A quadratic lower bound for homogeneous algebraic branching programs
• scientific article; zbMATH DE number 7250150 (Why is no real title available?)
• \textsf{VNP} = \textsf{VP} in the multilinear world

This page was built for publication: On algebraic branching programs of small width

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