Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR23-211 | 23rd December 2023 09:48

Characterizing the Power of (Persistent) Randomness in Log-space


Authors: Rafael Pass, Oren Renard
Publication: 24th December 2023 07:53
Downloads: 152


We 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:
\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.
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$.

ISSN 1433-8092 | Imprint