Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR14-157 | 27th November 2014 08:34

#### Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas

TR14-157
Authors: Rafael Mendes de Oliveira, Amir Shpilka, Ben Lee Volk
Publication: 27th November 2014 09:17
Keywords:

Abstract:

In this paper we give subexponential size hitting sets for bounded depth multilinear arithmetic formulas. Using the known relation between black-box PIT and lower bounds we obtain lower bounds for these models.

For depth-3 multilinear formulas, of size $\exp(n^\delta)$, we give a hitting set of size $\exp(\tilde{O}(n^{2/3 + 2\delta/3}))$.
This implies a lower bound of $\exp(\tilde{\Omega}(n^{1/2}))$ for depth-3 multilinear formulas, for some explicit polynomial.

For depth-4 multilinear formulas, of size $\exp(n^\delta)$, we give a hitting set of size $\exp(\tilde{O}(n^{2/3 + 4\delta/3}))$.
This implies a lower bound of $\exp(\tilde{\Omega}(n^{1/4}))$ for depth-4 multilinear formulas, for some explicit polynomial.

A regular formula consists of alternating layers of $+,\times$ gates, where all gates at layer $i$ have the same fan-in. We give a hitting set of size (roughly) $\exp\left(n^{1- \delta} \right)$, for regular depth-$d$ multilinear formulas of size $\exp(n^\delta)$, where $\delta = O(\frac{1}{\sqrt{5}^d})$.
This result implies a lower bound of roughly $\exp(\tilde{\Omega}(n^{\frac{1}{\sqrt{5}^d}}))$ for such formulas.

We note that better lower bounds are known for these models, but also that none of these bounds was achieved via construction of a hitting set. Moreover, no lower bound that implies such PIT results, even in the white-box model, is currently known.

Our results are combinatorial in nature and rely on reducing the underlying formula, first to a depth-4 formula, and then to a
read-once algebraic branching program (from depth-3 formulas we go straight to read-once algebraic branching programs).

ISSN 1433-8092 | Imprint