Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR23-070 | 9th May 2023 19:58

Bounded Relativization



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 $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.

ISSN 1433-8092 | Imprint