TR22-090 Authors: Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

Publication: 24th June 2022 15:52

Downloads: 359

Keywords:

We make progress on understanding a lower bound technique that was recently used by the authors to prove the first superpolynomial constant-depth circuit lower bounds against algebraic circuits.

More specifically, our previous work applied the well-known partial derivative method in a new setting, that of 'lopsided' set-multilinear polynomials. A set-multilinear polynomial $P\in F[X_1,\ldots,X_d]$ (for disjoint sets of variables $X_1,\ldots,X_d$) is a linear combination of monomials, each of which contains one variable from $X_1,\ldots,X_d$. A lopsided space of set-multilinear polynomials is one where the sets $X_1,\ldots,X_d$ are allowed to have different sizes (we use the adjective `lopsided' to stress this feature). By choosing a suitable lopsided space of polynomials, and using a suitable version of the partial-derivative method for proving lower bounds, we were able to prove constant-depth superpolynomial set-multilinear formula lower bounds even for very low-degree polynomials (as long as $d$ is a growing function of the number of variables $N$). This in turn implied lower bounds against general formulas of constant-depth.

A priori, there is nothing stopping these techniques from giving us lower bounds against algebraic formulas of 'any' depth. We investigate the extent to which this lower bound can extend to greater depths. We prove the following results.

** We observe that our choice of the lopsided space and the kind of partial-derivative method used can be modelled as the choice of a multiset $W\subseteq [-1,1]$ of size $d$. Our first result completely characterizes, for any product-depth $\Delta,$ the best lower bound we can prove for set-multilinear formulas of product-depth $\Delta$ in terms of some combinatorial properties of $W$, that we call the 'depth-$\Delta$ tree bias' of $W$.

** We show that the maximum depth-$3$ tree bias, over multisets $W$ of size $d$, is $\Theta(d^{1/4}).$ This shows a stronger formula lower bound of $N^{\Omega(d^{1/4})}$ for set-multilinear formulas of product-depth $3$, and also puts a non-trivial constraint on the best lower bounds we can hope to prove at this depth in this framework (a priori, we could have hoped to prove a lower bound of $N^{\Omega(\Delta d^{1/\Delta})}$ at product-depth $\Delta$).

** Finally, we show that for small $\Delta,$ our proof technique cannot hope to prove lower bounds of the form $N^{\Omega(d^{1/\poly(\Delta)})}.$ This seems to strongly hint that new ideas will be required to prove lower bounds for formulas of unbounded depth.