Projects per year
Abstract / Description of output
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.
Original language  English 

Title of host publication  29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, February 29th  March 3rd, 2012, Paris, France 
Pages  519530 
Number of pages  12 
DOIs  
Publication status  Published  24 Feb 2012 
Fingerprint
Dive into the research topics of 'Stronger Lower Bounds and RandomnessHardness TradeOffs Using Associated Algebraic Complexity Classes'. Together they form a unique fingerprint.Projects
 1 Finished

Hierarchies, Circuit Lower Bounds and Pseudorandomness
Santhanam, R.
1/10/10 → 31/12/12
Project: Research