ECCC-Report TR23-070https://eccc.weizmann.ac.il/report/2023/070Comments and Revisions published for TR23-070en-usThu, 11 May 2023 22:05:26 +0300
Paper TR23-070
| Bounded Relativization |
Shuichi Hirahara,
Zhenjian Lu,
Hanlin Ren
https://eccc.weizmann.ac.il/report/2023/070Relativization 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 $C$, we say that a statement is *$C$-relativizing* if the statement holds relative to every oracle $O$ in $C$. It is easy to see that every result that relativizes also $C$-relativizes for every complexity class $C$. On the other hand, we observe that many non-relativizing results, such as $IP = PSPACE$, are in fact $PSPACE$-relativizing.
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 $\varepsilon > 0$, $BPE^{MCSP}/2^{\varepsilon n} \not\subseteq SIZE[2^n/n]$. We prove this by $PSPACE$-relativizing the recent pseudodeterministic pseudorandom generator by Lu, Oliveira, and Santhanam (STOC 2021).
Next, we study the limitations of $PSPACE$-relativizing proof techniques, and show that a seemingly minor improvement over the known results using $PSPACE$-relativizing techniques would imply a breakthrough separation $NP \ne L$. For example:
$\bullet$ Impagliazzo and Wigderson (JCSS 2001) proved that if $EXP \ne BPP$, then $BPP$ admits infinitely-often subexponential-time heuristic derandomization. We show that their result is $PSPACE$-relativizing, and that improving it to worst-case derandomization using $PSPACE$-relativizing techniques implies $NP \ne L$.
$\bullet$ Oliveira and Santhanam (STOC 2017) recently proved that every dense subset in $P$ admits an infinitely-often subexponential-time pseudodeterministic construction, which we observe is $PSPACE$-relativizing. Improving this to almost-everywhere (pseudodeterministic) or (infinitely-often) deterministic constructions by $PSPACE$-relativizing techniques implies $NP \ne L$.
$\bullet$ Santhanam (SICOMP 2009) proved that $pr-MA$ does not have fixed polynomial-size circuits. This lower bound can be shown $PSPACE$-relativizing, and we show that improving it to an almost-everywhere lower bound using $PSPACE$-relativizing techniques implies $NP \ne L$.
In fact, we show that if we can use $PSPACE$-relativizing techniques to obtain the above-mentioned improvements, then $PSPACE \ne EXPH$. We obtain our barrier results by constructing suitable oracles computable in $EXPH$ relative to which these improvements are impossible. Thu, 11 May 2023 22:05:26 +0300https://eccc.weizmann.ac.il/report/2023/070