Lower bounds for special cases of syntactic multilinear ABPs

DOI10.1016/j.tcs.2019.10.047zbMath1436.68129OpenAlexW2988889505MaRDI QIDQ5919345

B. V. Raghavendra Rao, C. Ramya

Publication date: 29 January 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2019.10.047

zbMATH Keywords

computational complexitypolynomialsalgebraic complexity theory

Mathematics Subject Classification ID

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

Related Items

Limitations of sums of bounded read formulas and ABPs

Uses Software

• lowerbounds-survey

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower bounds and separations for constant depth multilinear circuits
• The complexity of partial derivatives
• Lower bounds on arithmetic circuits via partial derivatives
• Sums of read-once formulas: how many summands are necessary?
• Balancing syntactically multilinear arithmetic circuits
• Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication
• Lower Bounds for Syntactically Multilinear Algebraic Branching Programs
• Separation Between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits
• Small-Depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication with Applications
• Identity Testing and Lower Bounds for Read- k Oblivious Algebraic Branching Programs
• Lower bounds for Sum and Sum of Products of Read-once Formulas
• Separating multilinear branching programs and formulas
• Multi-linear formulas for permanent and determinant are of super-polynomial size