Dutta, Pranjal ;
Saxena, Nitin ;
Thierauf, Thomas
A Largish SumOfSquares Implies Circuit Hardness and Derandomization
Abstract
For a polynomial f, we study the sum of squares representation (SOS), i.e. f = ∑_{i ∈ [s]} c_i f_i² , where c_i are field elements and the f_i’s are polynomials. The size of the representation is the number of monomials that appear across the f_i’s. Its minimum is the supportsum S(f) of f.
For simplicity of exposition, we consider univariate f. A trivial lower bound for the supportsum of, a fullsupport univariate polynomial, f of degree d is S(f) ≥ d^{0.5}. We show that the existence of an explicit polynomial f with supportsum just slightly larger than the trivial bound, that is, S(f) ≥ d^{0.5+ε(d)}, for a subconstant function ε(d) > ω(√{log log d/log d}), implies that VP ≠ VNP. The latter is a major open problem in algebraic complexity. A further consequence is that blackboxPIT is in SUBEXP. Note that a random polynomial fulfills the condition, as there we have S(f) = Θ(d).
We also consider the sumofcubes representation (SOC) of polynomials. In a similar way, we show that here, an explicit hard polynomial even implies that blackboxPIT is in P.
BibTeX  Entry
@InProceedings{dutta_et_al:LIPIcs.ITCS.2021.23,
author = {Pranjal Dutta and Nitin Saxena and Thomas Thierauf},
title = {{A Largish SumOfSquares Implies Circuit Hardness and Derandomization}},
booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
pages = {23:123:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771771},
ISSN = {18688969},
year = {2021},
volume = {185},
editor = {James R. Lee},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13562},
URN = {urn:nbn:de:0030drops135629},
doi = {10.4230/LIPIcs.ITCS.2021.23},
annote = {Keywords: VP, VNP, hitting set, circuit, polynomial, sparsity, SOS, SOC, PIT, lower bound}
}
04.02.2021
Keywords: 

VP, VNP, hitting set, circuit, polynomial, sparsity, SOS, SOC, PIT, lower bound 
Seminar: 

12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Issue date: 

2021 
Date of publication: 

04.02.2021 