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 ) , we give a hitting set of size exp ( O ( n 2 3+2 3 )) . This implies a lower bound of exp ( ( n 1 2 )) for depth-3 multilinear formulas, for some explicit polynomial.

For depth-4 multilinear formulas, of size exp ( n ) , we give a hitting set of size exp ( O ( n 2 3+4 3 )) . This implies a lower bound of exp ( ( n 1 4 )) for depth-4 multilinear formulas, for some explicit polynomial.

A regular formula consists of alternating layers of + gates, where all gates at layer i have the same fan-in. We give a hitting set of size (roughly) exp n 1 − , for regular depth- d multilinear formulas of size exp ( n ) , where = O ( 1 5 d ) . This result implies a lower bound of roughly exp ( ( n 1 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).