Paper Info
Title
Unconditional Lower Bounds against Advice.
Abstract
We show several unconditional lower bounds for exponential time classes against polynomial time classes with advice, including: 1  For any constant c, \sf NEXP \not Í</font > \sf P\sf NP[nc]/nc{\sf NEXP} \not \subseteq {\rm{\sf P}}^{\sf NP[n^c]}/n^c 1  For any constant c, \sf MAEXP \not Í</font > \sf MA/nc{\sf MAEXP} \not \subseteq {\rm {\sf MA}}/n^c 1  \sf BPEXP \not Í</font > \sf BPP/no(1){\sf BPEXP} \not \subseteq {\sf BPP}/n^{o(1)} It was previously unknown even whether NEXP ⊆ NP/n 0.01. For the probabilistic classes, no lower bounds for uniform exponential time against advice were known before. We also consider the question of whether these lower bounds can be made to work on almost all input lengths rather than on infinitely many. We give an oracle relative to which NEXP ⊆ io NP, which provides evidence that this is not possible with current techniques.
Year
DOI
Venue
2009
10.1007/978-3-642-02927-1_18
international colloquium on automata, languages and programming
Keywords
DocType
Volume
unconditional lower bounds,sf bpp,sf nexp,sf p,sf np,exponential time class,sf ma,lower bound,constant c,sf bpexp,sf maexp
Journal
16
ISSN
Citations 
PageRank 
0302-9743
2
0.37
References 
Authors
24
3
Name
Order
Citations
PageRank
Harry Buhrman11607117.99
Lance Fortnow22788352.32
Rahul Santhanam339538.31