License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2016.35
URN: urn:nbn:de:0030-drops-58270
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5827/
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 hardness-randomness 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:1--35:29},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-008-8},
ISSN = {1868-8969},
year = {2016},
volume = {50},
editor = {Ran Raz},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5827},
URN = {urn:nbn:de:0030-drops-58270},
doi = {10.4230/LIPIcs.CCC.2016.35},
annote = {Keywords: arithmetic circuits, lower bounds, polynomial identity testing, hardness vs randomness}
}
|
Keywords: |
|
arithmetic circuits, lower bounds, polynomial identity testing, hardness vs randomness |
|
Collection: |
|
31st Conference on Computational Complexity (CCC 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
19.05.2016 |
