Arithmetic circuits with locally low algebraic rank

摘要

In recent years there has been a flurry of activity proving lower bounds for homogeneous depth-4 arithmetic circuits [GKKS13, FLMS14, KLSS14, KS14c], which has brought us very close to statements that are known to imply VP = VNP. It is a big question to go beyond homogeneity, and in this paper we make progress towards this by considering depth-4 circuits of {it low algebraic rank}, which are a natural extension of homogeneous depth-4 arithmetic circuits. A depth-4 circuit is a representation of an N -variate, degree n polynomial P as P = T i =1 Q i 1 Q i 2 Q it where the Q i j are given by their monomial expansion. Homogeneity adds the constraint that for every i [ T ] , j degree ( Q i j ) = n . We study an extension where, for every i [ T ] , the {it algebraic rank} of the set of polynomials Q i 1 Q i 2 Q it is at most some parameter k . We call this the class of ( k ) circuits. Already for k = n , these circuits are a strong generalization of the class of homogeneous depth-4 circuits, where in particular t n (and hence k n ).We study lower bounds and polynomial identity tests for such circuits and prove the following results. 1. Lower bounds : We give an explicit family of polynomials P n of degree n in N = n O (1) variables in VN P , such that any ( n ) circuit computing P n has size at least exp ( ( n log N )) . This strengthens and unifies two lines of work: it generalizes the recent exponential lower bounds for {it homogeneous} depth-4 circuits[KLSS14, KS14c] as well as the Jacobian based lower bounds of Agrawal et al [ASSS12] which worked for ( k ) circuits in the restricted setting where T k n . 2. Hitting sets : Let ( k ) [ d ] be the class of ( k ) circuits with bottom fan-in at most d . We show that if d and k are at most poly ( log N ) , then there is an explicit hitting set for ( k ) [ d ] circuits of size quasipolynomial in N and the size of the circuit. This strengthens a result of Forbes [For15] which showed such quasipolynomial sized hitting sets in the setting where d and t are at most poly ( log N ) . end{enumerate}A key technical ingredient of the proofs is a result which states that over any field of characteristic zero (or sufficiently large characteristic), upto a translation, every polynomial in a set of algebraically dependent polynomials can be written as a function of the polynomials in the transcendence basis. We believe this may be of independent interest. We combine this with shifted partial derivative based methods to obtain our final results.