Jansen, Maurice ;
Santhanam, Rahul
Stronger Lower Bounds and RandomnessHardness TradeOffs Using Associated Algebraic Complexity Classes
Abstract
We associate to each Boolean language complexity class C the algebraic class a.C consisting of families of polynomials {f_n} for which the evaluation problem over the integers is in C. We prove the following lower bound and randomnesstohardness results:
1. If polynomial identity testing (PIT) is in NSUBEXP then a.NEXP does not have poly size constantfree arithmetic circuits.
2. a.NEXP^RP does not have poly size constantfree arithmetic circuits.
3. For every fixed k, a.MA does not have arithmetic circuits of size n^k.
Items 1 and 2 strengthen two results due to (Kabanets and Impagliazzo, 2004). The third item improves a lower bound due to (Santhanam, 2009).
We consider the special case lowPIT of identity testing for (constantfree) arithmetic circuits with low formal degree, and give improved hardnesstorandomness tradeoffs that apply to this case.
Combining our results for both directions of the hardnessrandomness connection, we demonstrate a case where derandomization of PIT and proving lower bounds are equivalent. Namely, we show that lowPIT is in i.oNTIME[2^{n^{o(1)}}]/n^{o(1)} if and only if there exists a family of multilinear polynomials in a.NE/lin that requires constantfree arithmetic circuits of superpolynomial size and formal degree.
BibTeX  Entry
@InProceedings{jansen_et_al:LIPIcs:2012:3430,
author = {Maurice Jansen and Rahul Santhanam},
title = {{Stronger Lower Bounds and RandomnessHardness TradeOffs Using Associated Algebraic Complexity Classes}},
booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
pages = {519530},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897354},
ISSN = {18688969},
year = {2012},
volume = {14},
editor = {Christoph D{\"u}rr and Thomas Wilke},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3430},
URN = {urn:nbn:de:0030drops34307},
doi = {http://dx.doi.org/10.4230/LIPIcs.STACS.2012.519},
annote = {Keywords: Computational Complexity, Circuit Lower Bounds, Polynomial Identity Testing, Derandomization}
}
Keywords: 

Computational Complexity, Circuit Lower Bounds, Polynomial Identity Testing, Derandomization 
Seminar: 

29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Issue date: 

2012 
Date of publication: 

24.02.2012 