Arithmetic Circuits with Locally Low Algebraic Rank
share
In recent years, there has been a flurry of activity towards proving lower bounds for homogeneous depth-4 arithmetic circuits, which has brought us very close to statements that are known to imply VP≠VNP. It is open if these techniques can go beyond homogeneity, and in this paper we make some progress in this direction by considering depth-4 circuits of low algebraic rank, which are a natural extension of homogeneous depth-4 circuits. A depth-4 circuit is a representation of an N-variate, degree-n polynomial P as P = ∑_i = 1^T Q_i1· Q_i2·...· Q_it , where the Q_ij are given by their monomial expansion. Homogeneity adds the constraint that for every i ∈ [T], ∑_jdeg(Q_ij) = n. We study an extension, where, for every i ∈ [T], the algebraic rank of the set {Q_i1, Q_i2, ... ,Q_it} of polynomials is at most some parameter k. Already for k = n, these circuits are a 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. We show an (Ω(√(n) N)) lower bound for such circuits for an explicit N variate degree n polynomial family when k ≤ n. We also show quasipolynomial hitting sets when the degree of each Q_ij and the k are at most poly( n). A key technical ingredient of the proofs, which may be of independent interest, is a result which states that over any field of characteristic zero, up to a translation, every polynomial in a set of polynomials can be written as a function of the polynomials in a transcendence basis of the set. We combine this with methods based on shifted partial derivatives to obtain our final results.
READ FULL TEXT