2026-07-23T22:06:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2411 2024-03-06T11:09:02Z ddc:004 open_access

Unconditional Lower Bounds against Advice Buhrman, Harry Fortnow, Lance Santhanam, Rahul Advice derandomization diagonalization lower bounds semantic classes 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Harry Buhrman and Lance Fortnow and Rahul Santhanam 2010 Is Part Of Dagstuhl Seminar Proceedings, Volume 9421, Algebraic Methods in Computational Complexity (2010) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.09421.8 urn:nbn:de:0030-drops-24112 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09421.8 eng https://creativecommons.org/licenses/by/4.0/legalcode