Kumar, Mrinal ;
Saraf, Shubhangi
Arithmetic Circuits with Locally Low Algebraic Rank
Abstract
In recent years there has been a flurry of activity proving lower bounds for homogeneous depth4 arithmetic circuits, 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 depth4 circuits of low algebraic rank, which are a natural extension of homogeneous depth4 arithmetic circuits.
A depth4 circuit is a representation of an Nvariate, degree n polynomial P as P = sum_{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 in [T], sum_{j} degree(Q_{ij}) = n. We study an extension where, for every i in [T], the algebraic rank of the set of polynomials {Q_{i1}, Q_{i2}, ... ,Q_{it}} is at most some parameter k. We call this the class of spnew circuits. Already for k=n, these circuits are a strong generalization of the class of homogeneous depth4 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 VNP, such that any spnewn circuit computing P_n has size at least exp{(Omega(sqrt(n)*log(N)))}. This strengthens and unifies two lines of work: it generalizes the recent exponential lower bounds for homogeneous depth4 circuits [KLSS14, KSfull] as well as the Jacobian based lower bounds of Agrawal et al. which worked for spnew circuits in the restricted setting where T * k <= n.
2. Hitting sets: Let spnewbounded be the class of spnew circuits with bottom fanin at most d. We show that if d and k are at most poly(log(N)), then there is an explicit hitting set for spnewbounded circuits of size quasipolynomial in N and the size of the circuit. This strengthens a result of Forbes 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), 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.
BibTeX  Entry
@InProceedings{kumar_et_al:LIPIcs:2016:5828,
author = {Mrinal Kumar and Shubhangi Saraf},
title = {{Arithmetic Circuits with Locally Low Algebraic Rank}},
booktitle = {31st Conference on Computational Complexity (CCC 2016)},
pages = {34:134:27},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770088},
ISSN = {18688969},
year = {2016},
volume = {50},
editor = {Ran Raz},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5828},
URN = {urn:nbn:de:0030drops58288},
doi = {10.4230/LIPIcs.CCC.2016.34},
annote = {Keywords: algebraic independence, arithmetic circuits, lower bounds}
}
2016
Keywords: 

algebraic independence, arithmetic circuits, lower bounds 
Seminar: 

31st Conference on Computational Complexity (CCC 2016)

Issue date: 

2016 
Date of publication: 

2016 