Kumar, Mrinal ;
Saraf, Shubhangi
Sums of Products of Polynomials in Few Variables: Lower Bounds and Polynomial Identity Testing
Abstract
We study the complexity of representing polynomials as a sum of products of polynomials in few variables. More precisely, we study representations of the form P = sum_{i=1}^T prod_{j=1}^d Q_{ij} such that each Q_{ij} is an arbitrary polynomial that depends on at most s variables.
We prove the following results.
1. Over fields of characteristic zero, for every constant mu such that 0<=mu<=1, we give an explicit family of polynomials {P_{N}}, where P_{N} is of degree n in N = n^{O(1)} variables, such that any representation of the above type for P_{N} with s = N^{mu} requires Td >= n^{Omega(sqrt(n))}. This strengthens a recent result of Kayal and Saha [Kayal/Saha, ECCC 2014] which showed similar lower bounds for the model of sums of products of linear forms in few variables. It is known that any asymptotic improvement in the exponent of the lower bounds (even for s=sqrt(n)) would separate VP and VNP [Kayal/Saha, ECCC 2014].
2. We obtain a deterministic subexponential time blackbox polynomial identity testing (PIT) algorithm for circuits computed by the above model when T and the individual degree of each variable in P are at most log^{O(1)}(N) and s<=N^{mu} for any constant mu<1/2. We get quasipolynomial running time when s<log^{O(1)}(N). The PIT algorithm is obtained by combining our lower bounds with the hardnessrandomness tradeoffs developed in [Dvir/Shpilka/Yehudayoff, SIAM J. Comp. 2009; Kabanets/Impagliazzo, Comp. Compl. 2004]. To the best of our knowledge, this is the first nontrivial PIT algorithm for this model (even for the case s=2), and the first nontrivial PIT algorithm obtained from lower bounds for small depth circuits.
BibTeX  Entry
@InProceedings{kumar_et_al:LIPIcs:2016:5827,
author = {Mrinal Kumar and Shubhangi Saraf},
title = {{Sums of Products of Polynomials in Few Variables: Lower Bounds and Polynomial Identity Testing}},
booktitle = {31st Conference on Computational Complexity (CCC 2016)},
pages = {35:135:29},
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/5827},
URN = {urn:nbn:de:0030drops58270},
doi = {10.4230/LIPIcs.CCC.2016.35},
annote = {Keywords: arithmetic circuits, lower bounds, polynomial identity testing, hardness vs randomness}
}
2016
Keywords: 

arithmetic circuits, lower bounds, polynomial identity testing, hardness vs randomness 
Seminar: 

31st Conference on Computational Complexity (CCC 2016)

Issue date: 

2016 
Date of publication: 

2016 