Derandomizing Logspace With a Small Shared Hard Drive

Abstract We obtain new catalytic algorithms for space-bounded derandomization. In the catalytic computation model introduced by (Buhrman, Cleve, Koucký, 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 $$BPSPACE[S] \subseteq CSPACE[{S},{S^2}]$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>B</mml:mi> <mml:mi>P</mml:mi> <mml:mi>S</mml:mi> <mml:mi>P</mml:mi> <mml:mi>A</mml:mi> <mml:mi>C</mml:mi> <mml:mi>E</mml:mi> <mml:mrow> <mml:mo>[</mml:mo> <mml:mi>S</mml:mi> <mml:mo>]</mml:mo> </mml:mrow> <mml:mo>⊆</mml:mo> <mml:mi>C</mml:mi> <mml:mi>S</mml:mi> <mml:mi>P</mml:mi> <mml:mi>A</mml:mi> <mml:mi>C</mml:mi> <mml:mi>E</mml:mi> <mml:mrow> <mml:mo>[</mml:mo> <mml:mi>S</mml:mi> <mml:mo>,</mml:mo> <mml:msup> <mml:mi>S</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>]</mml:mo> </mml:mrow> </mml:mrow> </mml:math> where $$BPSPACE[S]$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>B</mml:mi> <mml:mi>P</mml:mi> <mml:mi>S</mml:mi> <mml:mi>P</mml:mi> <mml:mi>A</mml:mi> <mml:mi>C</mml:mi> <mml:mi>E</mml:mi> <mml:mo>[</mml:mo> <mml:mi>S</mml:mi> <mml:mo>]</mml:mo> </mml:mrow> </mml:math> corresponds to randomized space S computation, and $$CSPACE[{S},{C}]$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>C</mml:mi> <mml:mi>S</mml:mi> <mml:mi>P</mml:mi> <mml:mi>A</mml:mi> <mml:mi>C</mml:mi> <mml:mi>E</mml:mi> <mml:mo>[</mml:mo> <mml:mi>S</mml:mi> <mml:mo>,</mml:mo> <mml:mi>C</mml:mi> <mml:mo>]</mml:mo> </mml:mrow> </mml:math> corresponds to catalytic algorithms that use O(S) bits of workspace and O(C) bits of catalytic space. Previously, only $$BPSPACE[S]\subseteq CSPACE[{S},{2^{O(S)}}]$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>B</mml:mi> <mml:mi>P</mml:mi> <mml:mi>S</mml:mi> <mml:mi>P</mml:mi> <mml:mi>A</mml:mi> <mml:mi>C</mml:mi> <mml:mi>E</mml:mi> <mml:mrow> <mml:mo>[</mml:mo> <mml:mi>S</mml:mi> <mml:mo>]</mml:mo> </mml:mrow> <mml:mo>⊆</mml:mo> <mml:mi>C</mml:mi> <mml:mi>S</mml:mi> <mml:mi>P</mml:mi> <mml:mi>A</mml:mi> <mml:mi>C</mml:mi> <mml:mi>E</mml:mi> <mml:mrow> <mml:mo>[</mml:mo> <mml:mi>S</mml:mi> <mml:mo>,</mml:mo> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>S</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:msup> <mml:mo>]</mml:mo> </mml:mrow> </mml:mrow> </mml:math> was known. In fact, we prove a general tradeoff, that for every $$\alpha \in [1,1.5]$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>α</mml:mi> <mml:mo>∈</mml:mo> <mml:mo>[</mml:mo> <mml:mn>1</mml:mn> <mml:mo>,</mml:mo> <mml:mn>1.5</mml:mn> <mml:mo>]</mml:mo> </mml:mrow> </mml:math> , $$BPSPACE[S] \subseteq CSPACE[{S^{\alpha}},{S^{3-\alpha}}].$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>B</mml:mi> <mml:mi>P</mml:mi> <mml:mi>S</mml:mi> <mml:mi>P</mml:mi> <mml:mi>A</mml:mi> <mml:mi>C</mml:mi> <mml:mi>E</mml:mi> <mml:mrow> <mml:mo>[</mml:mo> <mml:mi>S</mml:mi> <mml:mo>]</mml:mo> </mml:mrow> <mml:mo>⊆</mml:mo> <mml:mi>C</mml:mi> <mml:mi>S</mml:mi> <mml:mi>P</mml:mi> <mml:mi>A</mml:mi> <mml:mi>C</mml:mi> <mml:mi>E</mml:mi> <mml:mrow> <mml:mo>[</mml:mo> <mml:msup> <mml:mi>S</mml:mi> <mml:mi>α</mml:mi> </mml:msup> <mml:mo>,</mml:mo> <mml:msup> <mml:mi>S</mml:mi> <mml:mrow> <mml:mn>3</mml:mn> <mml:mo>-</mml:mo> <mml:mi>α</mml:mi> </mml:mrow> </mml:msup> <mml:mo>]</mml:mo> </mml:mrow> <mml:mo>.</mml:mo> </mml:mrow> </mml:math> 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