A quadratic lower bound for algebraic branching programs

DOI10.4230/LIPIcs.CCC.2020.2OpenAlexW2998669040MaRDI QIDQ5092449

Prerona Chatterjee, Mrinal Kumar, Adrian She, Ben lee Volk

Publication date: 21 July 2022

Full work available at URL: https://doi.org/10.4230/LIPIcs.CCC.2020.2

zbMATH Keywords

lower boundalgebraic branching programs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (2)

Quadratic lower bounds for algebraic branching programs and formulas ⋮ Limitations of sums of bounded read formulas and ABPs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Quadratic lower bound for permanent vs. determinant in any characteristic
• The complexity of partial derivatives
• On sparse graphs with dense long paths
• Easy lower bound for a strange computational model
• Lower bounds on arithmetic circuits via partial derivatives
• Balancing syntactically multilinear arithmetic circuits
• A quadratic lower bound for homogeneous algebraic branching programs
• Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
• Arithmetic Circuits: A Chasm at Depth 3
• A Lower Bound for the Formula Size of Rational Functions
• Separating multilinear branching programs and formulas

This page was built for publication: A quadratic lower bound for algebraic branching programs