Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR23-168 | 14th November 2023 18:25

Derandomization in Catalytic Computation

RSS-Feed




Revision #1
Authors: Edward Pyne
Accepted on: 14th November 2023 18:25
Downloads: 213
Keywords: 


Abstract:

We obtain new catalytic algorithms for space-bounded derandomization.
In the catalytic computation model introduced by (Buhrman, Cleve, Koucky, Loff, and Speelman STOC 2013), we are given a small worktape, and a larger catalytic tape that has an arbitrary initial configuration. We may edit this tape, but it must be exactly restored to its initial configuration at the completion of the computation.
We prove that
$$
\text{BPSPACE}[S] \subseteq \text{CSPACE}[S,S^2]
$$
where $\text{CSPACE}[S,C]$ corresponds to catalytic algorithms that use $O(S)$ bits of workspace and $O(C)$ bits of catalytic space. Previously, only $\text{BPSPACE}[S]\subseteq \text{CSPACE}[S,2^{O(S)}]$ was known.
In fact, we prove a general tradeoff. We show that for every $\alpha \in [1,1.5]$,
$$
\text{BPSPACE}[S] \subseteq \text{CSPACE}[S^{\alpha},S^{3-\alpha}].
$$
We do not use the algebraic techniques of prior work on catalytic computation. Instead, we develop an algorithm that branches based on if the catalytic tape is conditionally random, and instantiate this primitive in a recursive framework. Our result gives an alternate proof of the best known time-space tradeoff for $\text{BPSPACE}[S]$, due to (Cai, Chakaravarthy, and van Melkebeek, Theory Comput. Sys. 2006).



Changes to previous version:

A prior version of this paper mistakenly claimed time-space tradeoffs for BPL as a new result. I am grateful to William Hoza for bringing the work of Cai, Chakaravarthy, and van Melkebeek to my attention.


Paper:

TR23-168 | 13th November 2023 23:42

Time-Space Tradeoffs for BPL via Catalytic Computation





TR23-168
Authors: Edward Pyne
Publication: 14th November 2023 01:32
Downloads: 252
Keywords: 


Abstract:

We prove that for every $\alpha \in [1,1.5]$,
$$
\text{BPSPACE}[S]\subseteq \text{TISP}[2^{S^{\alpha}},S^{3-\alpha}]
$$
where $\text{BPSPACE}[S]$ corresponds to randomized space $O(S)$ computation, and $\text{TISP}[T,S]$ to time $poly(T)$, space $O(S)$ computation. Our result smoothly interpolates between the results of (Nisan STOC 1992) and (Saks and Zhou FOCS 1995), which prove $\text{BPSPACE}[S]$ is contained in $\text{TISP}\left[2^S,S^2\right]$ and $\text{TISP}\left[2^{S^{3/2}},S^{3/2}\right]$ respectively.

We obtain this result from new catalytic algorithms for derandomization.
In the catalytic computation model introduced by (Buhrman, Cleve, Koucky, Loff, and Speelman STOC 2013), we are given a small worktape, and a larger catalytic tape that has an arbitrary initial configuration. We may edit this tape, but it must be exactly restored to its initial configuration at the completion of the computation.
We prove that
$$
\text{BPSPACE}[S] \subseteq \text{CSPACE}[S,S^2]
$$
where $\text{CSPACE}[S,C]$ corresponds to catalytic algorithms that use $O(S)$ bits of workspace and $O(C)$ bits of catalytic space. Previously, only $\text{BPSPACE}[S]\subseteq \text{CSPACE}[S,2^{O(S)}]$ was known.
In fact, we prove a general tradeoff. We show that for every $\alpha \in [1,1.5]$,
$$
\text{BPSPACE}[S] \subseteq \text{CSPACE}[S^{\alpha},S^{3-\alpha}].
$$
We do not use the algebraic techniques of prior work on catalytic computation. Instead, we develop an algorithmic win-win argument based on if the catalytic tape is conditionally random, and instantiate this primitive in a recursive framework.



ISSN 1433-8092 | Imprint