Separation Between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits

DOI10.4230/LIPIcs.STACS.2016.46zbMath1388.68048OpenAlexW2295840581MaRDI QIDQ4601898

Neeraj Kayal, Chandan Saha, Vineet Nair

Publication date: 24 January 2018

Full work available at URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2016.46

zbMATH Keywords

iterated matrix multiplicationexpander graphsevaluation dimensionmultilinear depth-three circuitsread-once oblivious algebraic branching programsskewed partial derivatives

Mathematics Subject Classification ID

Related Items (8)

Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications. ⋮ Deterministic identity testing for sum of read-once oblivious arithmetic branching programs ⋮ A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas ⋮ Small-Depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication with Applications ⋮ Lower bounds for special cases of syntactic multilinear ABPs ⋮ Blackbox identity testing for sum of special ROABPs and its border class ⋮ On Proving Parameterized Size Lower Bounds for Multilinear Algebraic Models ⋮ Limitations of sums of bounded read formulas and ABPs

This page was built for publication: Separation Between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits