License
When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-24112
URL: http://drops.dagstuhl.de/opus/volltexte/2010/2411/
Go to the corresponding Portal


Buhrman, Harry ; Fortnow, Lance ; Santhanam, Rahul

Unconditional Lower Bounds against Advice

pdf-format:
Document 1.pdf (192 KB)


Abstract

We show several unconditional lower bounds for exponential time classes against polynomial time classes with advice, including: (1) For any constant c, NEXP not in P^{NP[n^c]} (2) For any constant c, MAEXP not in MA/n^c (3) BPEXP not in BPP/n^{o(1)}. It was previously unknown even whether NEXP in 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 in i.o.NP, which provides evidence that this is not possible with current techniques.

BibTeX - Entry

@InProceedings{buhrman_et_al:DSP:2010:2411,
  author =	{Harry Buhrman and Lance Fortnow and Rahul Santhanam},
  title =	{Unconditional Lower Bounds against Advice},
  booktitle =	{Algebraic Methods in Computational Complexity},
  year =	{2010},
  editor =	{Manindra Agrawal and Lance Fortnow and Thomas Thierauf and Christopher Umans},
  number =	{09421},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2411},
  annote =	{Keywords: Advice, derandomization, diagonalization, lower bounds, semantic classes}
}

Keywords: Advice, derandomization, diagonalization, lower bounds, semantic classes
Seminar: 09421 - Algebraic Methods in Computational Complexity
Issue Date: 2010
Date of publication: 19.01.2010


DROPS-Home | Fulltext Search | Imprint Published by LZI