DagSemProc.09421.8.pdf
- Filesize: 191 kB
- 11 pages
Document
Unconditional Lower Bounds against Advice
Authors
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 9421
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2010-01-19
Cite As Get BibTex
Harry Buhrman, Lance Fortnow, and Rahul Santhanam. Unconditional Lower Bounds against Advice. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 9421, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
https://doi.org/10.4230/DagSemProc.09421.8
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.
Subject Classification
Keywords
- Advice
- derandomization
- diagonalization
- lower bounds
- semantic classes
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads