Abstract
Relativization is one of the most fundamental concepts in complexity theory, which explains the difficulty of resolving major open problems. In this paper, we propose a weaker notion of relativization called bounded relativization. For a complexity class ℭ, we say that a statement is ℭrelativizing if the statement holds relative to every oracle ? ∈ ℭ. It is easy to see that every result that relativizes also ℭrelativizes for every complexity class ℭ. On the other hand, we observe that many nonrelativizing results, such as IP = PSPACE, are in fact PSPACErelativizing.
First, we use the idea of bounded relativization to obtain new lower bound results, including the following nearly maximum circuit lower bound: for every constant ε > 0, BPE^{MCSP}/2^{εn} ⊈ SIZE[2ⁿ/n].
We prove this by PSPACErelativizing the recent pseudodeterministic pseudorandom generator by Lu, Oliveira, and Santhanam (STOC 2021).
Next, we study the limitations of PSPACErelativizing proof techniques, and show that a seemingly minor improvement over the known results using PSPACErelativizing techniques would imply a breakthrough separation NP ≠ L. For example:
 Impagliazzo and Wigderson (JCSS 2001) proved that if EXP ≠ BPP, then BPP admits infinitelyoften subexponentialtime heuristic derandomization. We show that their result is PSPACErelativizing, and that improving it to worstcase derandomization using PSPACErelativizing techniques implies NP ≠ L.
 Oliveira and Santhanam (STOC 2017) recently proved that every dense subset in P admits an infinitelyoften subexponentialtime pseudodeterministic construction, which we observe is PSPACErelativizing. Improving this to almosteverywhere (pseudodeterministic) or (infinitelyoften) deterministic constructions by PSPACErelativizing techniques implies NP ≠ L.
 Santhanam (SICOMP 2009) proved that prMA does not have fixed polynomialsize circuits. This lower bound can be shown PSPACErelativizing, and we show that improving it to an almosteverywhere lower bound using PSPACErelativizing techniques implies NP ≠ L.
In fact, we show that if we can use PSPACErelativizing techniques to obtain the abovementioned improvements, then PSPACE ≠ EXPH. We obtain our barrier results by constructing suitable oracles computable in EXPH relative to which these improvements are impossible.
BibTeX  Entry
@InProceedings{hirahara_et_al:LIPIcs.CCC.2023.6,
author = {Hirahara, Shuichi and Lu, Zhenjian and Ren, Hanlin},
title = {{Bounded Relativization}},
booktitle = {38th Computational Complexity Conference (CCC 2023)},
pages = {6:16:45},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772822},
ISSN = {18688969},
year = {2023},
volume = {264},
editor = {TaShma, Amnon},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18276},
URN = {urn:nbn:de:0030drops182764},
doi = {10.4230/LIPIcs.CCC.2023.6},
annote = {Keywords: relativization, circuit lower bound, derandomization, explicit construction, pseudodeterministic algorithms, interactive proofs}
}
Keywords: 

relativization, circuit lower bound, derandomization, explicit construction, pseudodeterministic algorithms, interactive proofs 
Collection: 

38th Computational Complexity Conference (CCC 2023) 
Issue Date: 

2023 
Date of publication: 

10.07.2023 