On Proving Parameterized Size Lower Bounds for Multilinear Algebraic Models

We consider the problem of obtaining parameterized lower bounds for the size of arithmetic circuits computing polynomials with the degree of the polynomial as the parameter. In particular, we consider the following special classes of multilinear algebraic branching programs: (1) Read Once Oblivious Algebraic Branching Programs (ROABPs); (2) Strict interval branching programs; and (3) Sum of read once formulas with restricted ordering. We obtain parameterized lower bounds (i.e., (forumala presented). lower bound for some function t of k) on the size of the above models computing a multilinear polynomial that can be computed by a depth four circuit of size g(k) nO(1) for some computable function g. Our proof is an adaptation of the existing techniques to the parameterized setting. The main challenge we address is the construction of hard parameterized polynomials. In fact, we show that there are polynomials computed by depth four circuits of small size (in the parameterized sense), but have high rank of the partial derivative matrix.