Name
Abstract | ||
|---|---|---|
In recent years there has been a flurry of activity proving lower bounds for homogeneous depth-4 arithmetic circuits [14, 11, 18, 27], 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 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 [EQUATION] · Qi2 .... Qit where the Qij are given by their monomial expansion. Homogeneity adds the constraint that for every i ∈ [T], Σj degree(Qij) = n. We study an extension where, for every i ∈ [T], the algebraic rank of the set of polynomials {Qi1, Qi2, ..., Qit} 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 {Pn} of degree n in N = nO(1) variables in VNP, such that any ΣΠ(n) ΣΠ circuit computing Pn has size at least exp ([EQUATION]). This strengthens and unifies two lines of work: it generalizes the recent exponential lower bounds for homogeneous depth-4 circuits [18, 27] as well as the Jacobian based lower bounds of Agrawal et al. [2] 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 [8] which showed such quasipolynomial sized hitting sets in the setting where d and t are at most poly(log N). A key technical ingredient of the proofs is a result which states that over any field of characteristic zero (or sufficiently large characteristic), up to 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. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.4230/LIPIcs.CCC.2016.34 | CCC '16 Proceedings of the 31st Conference on Computational Complexity |
Keywords | DocType | Volume |
algebraic independence,arithmetic circuits,lower bounds | Conference | abs/1806.06097 |
Issue | ISSN | ISBN |
1 | Theory of Computing 13(6):1-33, 2017 | 978-3-95977-008-8 |
Citations | PageRank | References |
3 | 0.37 | 0 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mrinal Kumar 0001 | 1 | 64 | 9.94 |
| Shubhangi Saraf | 2 | 263 | 24.55 |