Lower Bounds for Syntactically Multilinear Algebraic Branching Programs

DOI10.1007/978-3-540-85238-4_33MaRDI QIDQ3599145zbMATH OpenOpenAlexFDO

Authors Maurice Jansen

Publication date 3 February 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-85238-4_33

zbMATH Keywords

computational complexitylower boundsalgebraic branching programsmultilinear polynomialsarithmetical circuits

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• scientific article; zbMATH DE number 706832
• A quadratic lower bound for algebraic branching programs
• scientific article; zbMATH DE number 3913677
• Quadratic lower bounds for algebraic branching programs and formulas
• Lower bounds for special cases of syntactic multilinear ABPs
• Lower bounds for special cases of syntactic multilinear ABPs
• A quadratic lower bound for homogeneous algebraic branching programs
• A quadratic lower bound for homogeneous algebraic branching programs
• Succinct algebraic branching programs characterizing non-uniform complexity classes
• A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits

Cites work

• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
• Balancing sets of vectors
• Balancing syntactically multilinear arithmetic circuits
• Characterizing Valiant’s Algebraic Complexity Classes
• Codes with given distances
• Fast Parallel Computation of Polynomials Using Few Processors
• Forbidden Intersections
• On computing the determinant in small parallel time using a small number of processors
• On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication
• Separation of multilinear circuit and formula size
• The Parallel Evaluation of General Arithmetic Expressions

Cited in

(20)

• On the power of algebraic branching programs of width two
• Resource trade-offs in syntactically multilinear arithmetic circuits
• scientific article; zbMATH DE number 7561696 (Why is no real title available?)
• Superlinear lower bounds for bounded-width branching programs
• Limitations of sums of bounded read formulas and ABPs
• Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits
• scientific article; zbMATH DE number 7250151 (Why is no real title available?)
• Arithmetic circuits: the chasm at depth four gets wider
• Lower bounds for special cases of syntactic multilinear ABPs
• Small space analogues of Valiant's classes and the limitations of skew formulas
• Simulation of Arithmetical Circuits by Branching Programs with Preservation of Constant Width and Syntactic Multilinearity
• Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae
• A quadratic lower bound for homogeneous algebraic branching programs
• Lower bounds for set-multilinear branching programs
• \(d\)-Galvin families
• Algebraic complexity classes
• Lower bounds for special cases of syntactic multilinear ABPs
• Quadratic lower bounds for algebraic branching programs and formulas
• Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits
• A quadratic lower bound for homogeneous algebraic branching programs

This page was built for publication: Lower Bounds for Syntactically Multilinear Algebraic Branching Programs

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