ECCC-Report TR23-211https://eccc.weizmann.ac.il/report/2023/211Comments and Revisions published for TR23-211en-usSun, 24 Dec 2023 07:53:44 +0200
Paper TR23-211
| Characterizing the Power of (Persistent) Randomness in Log-space |
Oren Renard,
Rafael Pass
https://eccc.weizmann.ac.il/report/2023/211We study the problem of whether \emph{persistent} randomness is helpful for polynomial-time algorithms that only use \emph{logarithmic} space. In more detail, we consider the class $\searchBPLs$, of \emph{search}-problems that are solvable by a polynomial-time Probabilistic Logspace TMs with \emph{2-way} access (i.e., with multiple, as opposed to one-time, access) to a random tape---denoted \PLMs---and demonstrate two complexity-theoretic hardness assumptions that are \emph{equivalent} to $\searchBPLs = \searchL$. Namely, the following are equivalent:
\begin{enumerate}
\item $\searchBPLs= \searchL$,
\item The gap problem, of deciding whether the conditional Kolmogorov-Space complexity of strings $\KS$ is ``large`` (i.e., $\KS(x|y) \ge n-1$) or ``small" (i.e., $\KSc(x|y) \leq O(\log n)$), is worst-case hard for \PLMs with sufficiently bounded time and space, given \emph{any} sufficiently long auxiliary input $y$.
\item The existence of a logspace computable function $f\colon \{0,1\}^n\to\{0,1\}^n$, that is \emph{almost-all-input hard} for sufficiently space and time bounded \PLMs, even in the presence of a bounded-length leakage computable by a (sufficiently time/space-bounded) \PLMs that is given access to the solution.
\end{enumerate}
Our results leverage and extend earlier characterizations of $\BPP = \cP$ of Liu and Pass (CCC'22, CCC'23), and relies on the recent space-efficient reconstruction technique of Doron and Tell (CCC'23).
Taken together with the earlier results of Liu and Pass, our results enable simple comparison between the hardness assumptions required to derandomize $\searchBPP$ (or equivalently $\BPP$) vs. $\searchBPLs$.Sun, 24 Dec 2023 07:53:44 +0200https://eccc.weizmann.ac.il/report/2023/211