Lower Bounds for Syntactically Multilinear Algebraic Branching Programs

DOI10.1007/978-3-540-85238-4_33zbMath1173.68520OpenAlexW1569126348MaRDI QIDQ3599145

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

Related Items (13)

Resource trade-offs in syntactically multilinear arithmetic circuits ⋮ Small space analogues of Valiant's classes and the limitations of skew formulas ⋮ Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits ⋮ Arithmetic circuits: the chasm at depth four gets wider ⋮ On the Power of Algebraic Branching Programs of Width Two ⋮ Unnamed Item ⋮ Lower bounds for special cases of syntactic multilinear ABPs ⋮ \(d\)-Galvin families ⋮ Unnamed Item ⋮ Algebraic Complexity Classes ⋮ Simulation of Arithmetical Circuits by Branching Programs with Preservation of Constant Width and Syntactic Multilinearity ⋮ Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits ⋮ Limitations of sums of bounded read formulas and ABPs

Cites Work

• Unnamed Item
• Unnamed Item
• On computing the determinant in small parallel time using a small number of processors
• Codes with given distances
• Balancing syntactically multilinear arithmetic circuits
• Fast Parallel Computation of Polynomials Using Few Processors
• A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
• On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication
• Forbidden Intersections
• The Parallel Evaluation of General Arithmetic Expressions
• Characterizing Valiant’s Algebraic Complexity Classes
• Balancing sets of vectors

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