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 @math , we give a hitting set of size @math . This implies a lower bound of @math for depth-3 multilinear formulas, for some explicit polynomial. For depth-4 multilinear formulas, of size @math , we give a hitting set of size @math . This implies a lower bound of @math for depth-4 multilinear formulas, for some explicit polynomial. A regular formula consists of alternating layers of @math gates, where all gates at layer @math have the same fan-in. We give a hitting set of size (roughly) @math , for regular depth- @math multilinear formulas of size @math , where @math . This result implies a lower bound of roughly @math 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).
An arithmetic formula is multilinear if the polynomial computed by each of its subformulas is multilinear. We prove that any multilinear arithmetic formula for the permanent or the determinant of an n × n matrix is of size super-polynomial in n. Previously, super-polynomial lower bounds were not known (for any explicit function) even for the special case of multilinear formulas of constant depth. We construct an explicit polynomial @math , with coefficients in @math , such that the size of any syntactically multilinear arithmetic circuit computing @math is at least @math . The lower bound holds over any field. It is shown that any multivariate polynomial of degree d that can be computed sequentially in C steps can be computed in parallel in @math steps using only @math processors.   In their paper on the ''chasm at depth four'', Agrawal and Vinay have shown that polynomials in m variables of degree O(m) which admit arithmetic circuits of size 2^o^(^m^) also admit arithmetic circuits of depth four and size 2^o^(^m^). This theorem shows that for problems such as arithmetic circuit lower bounds or black-box derandomization of identity testing, the case of depth four circuits is in a certain sense the general case. In this paper we show that smaller depth four circuits can be obtained if we start from polynomial size arithmetic circuits. For instance, we show that if the permanent of nxn matrices has circuits of size polynomial in n, then it also has depth 4 circuits of size n^O^(^n^l^o^g^n^). If the original circuit uses only integer constants of polynomial size, then the same is true for the resulting depth four circuit. These results have potential applications to lower bounds and deterministic identity testing, in particular for sums of products of sparse univariate polynomials. We also use our techniques to reprove two results on: -the existence of nontrivial boolean circuits of constant depth for languages in LOGCFL; -reduction to polylogarithmic depth for arithmetic circuits of polynomial size and polynomially bounded degree. An arithmetic circuit or formula is multilinear if the polynomial computed at each of its wires is multilinear. We give an explicit polynomial f(x1,..., xn) with coeffi- cients in 0, 1 such that over any field: 1. f can be computed by a polynomial-size multilinear circuit of depth O(log 2 n). We show that, over Q, if an n-variate polynomial of degree d = nO(1) is computable by an arithmetic circuit of size s (respectively by an arithmetic branching program of size s) then it can also be computed by a depth three circuit (i.e. a ΣΠΣ-circuit) of size exp(O(√(d log n log d log s))) (respectively of size exp(O(√(d log n log s))). In particular this yields a ΣΠΣ circuit of size exp(O(√(d log d))) computing the d × d determinant Detd. It also means that if we can prove a lower bound of exp(omega(√(d log d))) on the size of any ΣΠΣ-circuit computing the d × d permanent Permd then we get super polynomial lower bounds for the size of any arithmetic branching program computing Permd. We then give some further results pertaining to derandomizing polynomial identity testing and circuit lower bounds. The ΣΠΣ circuits that we construct have the property that (some of) the intermediate polynomials have degree much higher than d. Indeed such a counterintuitive construction is unavoidable - it is known that in any ΣΠΣ circuit C computing either Detd or Perm_d, if every multiplication gate has fanin at most d (or any constant multiple thereof) then C must have size at least exp(Ω(d)).