Fully Characterizing Lossy Catalytic Computation

Let $M_e$ be an $\text{LCSPACE}[s,c,e]$ machine. We will devise a $\text{CSPACE}[s+O(e\log c),c]$ machine $M_0$ which simulates $M_e$. Note that in this section, we will not use our parameter restriction on $e$; this direction holds for every setting of $s$, $c$, and $e$. We will presume that $e\le \frac{c}{\log (c)}$, as the inclusion becomes trivial otherwise.

Our simulation will go via an error-correcting code. In particular we will use BCH codes³³3Technically because of our parameters, they can even be considered Reed-Solomon codes, which are a special case of BCH codes; nevertheless we follow the presentation of the more general code form. (BCH), named after Bose, Ray-Chaudhuri, and Hocquenghem [3, 17], which we define as per [13, 12]. We define the mapping BCH and prove the following lemma in the appendix to the the full version of our paper.

We now move on to the simulation of our $\text{LCSPACE}[s,c,e]$ machine $M_e$. Our $\text{CSPACE}[s+O(e\log c),c]$ machine $M_0$ acts as follows:

1. 1.

   Initialization: use the function ${\text{Enc}}_{\text{BCH}}$ to encode the initial state $\tau$ of the catalytic tape into a codeword, using $(2e+1)\lceil \log (c+e)\rceil$ additional bits from clean space,

   $$\tau +{[0]}_{(2e+1)\lceil \log (c+e)\rceil }{\to }_{\text{Enc}}{\tau }_{enc}.$$

2. 2.

   Simulation: Run $M_e$ using clean space $s$ and the first $c$ bits of ${\tau }_{enc}$ as the catalytic tape. When $M_e$ finishes the calculation, we record the answer in a bit of the free work tape. The catalytic tape is, at this point, in a state ${\tau }_{enc}^{\prime }$ which differs in at most $e$ locations from ${\tau }_{enc}$.

3. 3.

   Cleanup: use the function ${\text{Dec}}_{\text{BCH}}$ to detect and correct our resulting catalytic tape ${\tau }_{enc}^{\prime }$:

   $${\tau }_{enc}^{\prime }{\to }_{\text{Dec}}\tau +{[0]}_{(2e+1)\lceil \log (c+e)\rceil }$$

   Once we finish this process, we output our saved answer and halt.

The correctness of $M_0$ is clear, as it gives the same output as $M_e$. By our error guarantee on $M_e$ and the correctness of Dec, our catalytic tape is successfully reset to $\tau$. Our catalytic memory is $c$ as before, while for our free work space we require $s$ bits to simulate $M_e$, an additional $(2e+1)\lceil \log (c+e)\rceil =(2+o(1))e\log c$ zero bits for our codewords, and $O(e\log c)$ space for ${\text{Enc}}_{\text{BCH}}$ and ${\text{Dec}}_{\text{BCH}}$, for $s+O(e\log c)$ space in total. $◀$

Let $M_0$ be a $\text{CSPACE}[s+e\log c,c]$ machine. We will devise a $\text{LCSPACE}[s+(\log e+\log c+2),(e+1)c,e]$ machine $M_e$ which simulates $M_0$. By the definition of a Turing machine, we will assume that in any time step $M_0$ only reads and writes at most one bit on the work tape.

Throughout this proof, we will associate $[2^k]$ with ${\{0,1\}}^k$ in the usual manner, i.e. subtracting 1 and taking the binary representation, and so we will use them interchangeably. Our workhorse is the following folklore⁴⁴4This construction is based on the solution to the so-called “almost impossible chessboard puzzle”; interested readers can find the setup and solution in videos on the YouTube channels 3Blue1Brown (https://www.youtube.com/watch?v=wTJI_WuZSwE) and Stand-up Maths (https://www.youtube.com/watch?v=as7Gkm7Y7h4). It can also be seen as the syndrome of the Hamming code. construction:

Intuitively, Lemma 12 gives us an easily computable mapping where any transformation of the $k$-bit output string can be achieved by flipping one bit of the $2^k$-bit input string, with the location of this single bitflip being determined only by the locations where the current and target output strings differ.⁵⁵5It is not particularly important that the location to flip in $\tau$ to achieve $\text{mem}(\tau )\oplus y$ is exactly ${\sigma }_y$, but only that there exists some such place to flip, depending only on the mask $y$, and that this location can be easily calculated given $y$.

Let $\tau \in {\{0,1\}}^{2^k}$ be indexed by bitstrings $z\in {\{0,1\}}^k$. We will define our mapping mem as the entrywise sum of all indices $z$ where ${\tau }_z=1$, i.e.

This is clearly computable in space $k+1$, as we need only store $z$ and our current sum. Now note that for any $y$, flipping the entry ${\tau }_y$, i.e. $\tau \oplus {\sigma }_y$, flips every $\text{mem}{(\tau )}_j$ entry where $y_j=1$ and leaves all other $\text{mem}{(\tau )}_j$ entry unchanged, which gives $\text{mem}(\tau )\oplus y$ as claimed. $◀$

At a high level, our $\text{LCSPACE}[s+(\log e+\log c+2),(e+1)c,e]$ machine $M_e$ works as follows. $M_e$ will use its $s$ bits of free memory and the first $c$ bits of catalytic memory to represent their equivalent blocks in $M_0$, i.e. $s$ bits of free memory and $c$ bits of catalytic memory. We will break the remaining $e\cdot c$ bits of our catalytic tape of $M_e$ into $e$ blocks $B_1\mathrm{\dots }{B}_e$ of size $c$ each, and we denote by ${\tau }_i$ the memory in block $B_i$. We apply Lemma 12 with $k=\log c$ – recall that we assume $c$ is a power of 2 – and use each $\text{mem}({\tau }_i)$ to represent an additional $\log c$ bits of free memory, giving us an additional $e\log c$ bits of memory in total. Our additional workplace memory will be used to compute the mapping, serve as pointers, and other assorted tasks.

Before formally stating $M_e$, we mention a special case of the construction of Lemma 12, which will allow us to use it in a reversible operational manner.

For all $i\in [t]$, let $b_i\in [k]$ be the location where $\text{mem}({\tau }_i)$ and $\text{mem}({\tau }_{i-1})$ differ, and let ${\beta }_i$ be the location where ${\tau }_i$ and ${\tau }_{i-1}$ differ. Since $\text{mem}({\tau }_t)=\text{mem}({\tau }_0)$, each value $j\in [k]$ must appear an even number of times in the list $b_1\mathrm{\dots }{b}_t$, and since flipping any location $j\in [k]$ in $\text{mem}(\tau )$ can only be obtained from one flip in $\tau$ at the unique location $2^j\in [2^k]$, it follows that each value $J\in [2^k]$ must appear an even number of times in the list ${\beta }_1\mathrm{\dots }{\beta }_t$. This means that ${\tau }_t$ is ${\tau }_0$ with each bit flipped an even number of times, or in other words ${\tau }_t={\tau }_0$. $\mathrm{⊲}$

We now concretely define our machine $M_e$:

1. 1.

   Initialization: for each block $B_i$, calculate ${\text{mem}}_i$ and flip the ${\text{mem}}_i$th element of $B_i$:

   $${\tau }_i\to {\tau }_i\oplus {\sigma }_{\text{mem}({\tau }_i)}\forall i\in [e]$$

   Define ${\tau }_i^{enc}$ to be the memory after this process. Note that we now have exactly $e$ errors on the tape, one in each ${\tau }_i^{enc}$, and we are guaranteed that

   $$\text{mem}({\tau }_i^{enc})=0^{\log c}\forall i\in [e]$$

2. 2.

   Simulation: run $M_0$ using $s$ free work bits and $c$ catalytic bits, with the concatenation of the values ${\text{mem}}_i$ as the other $e\log c$ free work bits. To do this, whenever we read or write a bit in our $e\log c$ bits of memory, we find the $B_i$ responsible for this bit, calculate ${\text{mem}}_i$, and update ${\tau }_i$ using one bitflip to reflect how ${\text{mem}}_i$ changes according to the operation of $M_0$:

   $${\tau }_i^{enc}\to {\tau }_i^{enc}\oplus {\sigma }_{2^j}\text{update occurs in bit }j\text{ of block }i$$

   If ${\text{mem}}_i$ is unchanged, we make no updates to ${\tau }_i$.

3. 3.

   Cleanup: when we reach the end of $M_0$’s computation, record the answer on the free work tape and set each ${\text{mem}}_i$ value to $0^{\log c}$ one bit at a time:

   $${\tau }_i^{enc}\to {\tau }_i^{enc}\oplus {\sigma }_{2^j}\forall i\in [e],j:\text{mem}({\tau }_i^{enc})){}_j=1$$

   Once we finish this process, we output our saved answer and halt.

The correctness of $M_e$ is clear, as we output the same value as $M_0$. Our catalytic space usage is $c+ec$ by construction, while our free space usage is $s$ to simulate $M_0$, one extra bit to save the output, and any additional space required to handle the simulation of the additional $e\log c$ work bits. In particular, we need $\log e$ bits for a pointer into $B_i$ and $\log c+1$ bits for the computation of ${\text{mem}}_i$ by Lemma 12, for a total space usage of $s+\log e+\log c+2$ as claimed.

We also claim that our lossy catalytic condition is satisfied. By the property of $M_0$, we make no errors on the $c$ catalytic bits used for the simulation of $M_0$’s catalytic space. The initialization step introduces at most one error per ${\tau }_i$, thus giving at most $e$ errors on to the catalytic tape. After the initialization step, each other update to ${\tau }_i$ corresponds to changing a single bit in $\text{mem}({\tau }_i)$, with the final value being the same as the value after initialization. Thus by Claim 13 we restore the catalytic tape to its position after the initialization phase, and so our end state corresponds to our original catalytic tape with at most $e$ errors, i.e. those induced by the initialization phase, as required. $◀$

We now return to Theorem 10, which requires only a small modification of the above proof, namely to break the the catalytic tape into more, smaller blocks, which reduces its required length at the cost of a few extra errors. This modification works because the number of pure bits represented is logarithmic in the length of the block, and so making the blocks smaller barely affects the number of bits represented; for example, $c/2$ bits in a block still lets you represent $\log (c)-1$ bits, so half the size only loses one bit per block.

Let $M_0$ be a $\text{CSPACE}[s+e\log c,c]$ machine. We will devise a $\text{LCSPACE}[s+e\log c,(1+o(1))c,(1+ϵ)e]$ machine $M_e$ which simulates $M_0$, where $ϵ$ satisfies $e=o(c^{ϵ/(1+ϵ)})$.

An easy manipulation gives us $c=\omega (e^{1+1/ϵ})$, and so there exists a function $\delta =\omega (1)$ such that $c\ge {(\delta e)}^{1+1/ϵ}$. We will have the same approach as Theorem 11, but now we use $(1+ϵ)e$ blocks of length $2^{\lceil \log c/(\delta e)\rceil }$ each, i.e., using Lemma 12 for $k=\lceil \log c/(\delta e)\rceil$. Since we introduce one error per block, the number of errors the machine makes is at most $(1+ϵ)e$, while our total catalytic tape has length

Lastly, we can use our additional catalytic memory to simulate a work tape of length

and by manipulating our starting assumption we get that

thus giving us a simulation of $e\log c$ work bits as claimed. The correctness and lossy catalytic condition can then be argued as above, and our free space usage is $s$ plus an additional $\log (c\cdot o(1))+2\le \log c$ bits, for a total space usage of $s+\log c$ as claimed. $◀$

This follows immediately from the fact that

combined with the fact that $\text{CL}\subseteq \text{ZPP}$ by [4]. $◀$

As earlier, we need to show both directions. We will prove the same two equivalences as in Theorems 7 and 10, namely

1. 1.

   $\text{L}𝒞[s,c,e]\subseteq 𝒞[s+O(e\log c),c]$

2. 2.

   $𝒞[s+e\log c,c]\subseteq \text{L}𝒞[s+\log c,(1+o(1))c,(1+ϵ)e]$

Both directions will follow immediately via the same simulation as before. For the forward direction, we simulate our L$𝒞$ machine by a $𝒞$ machine as usual, and then at the last step we correct the changes using our BCH code as before; this works just as before because the code allow us to correct any $e$ errors on the catalytic tape, regardless of how they came about.

For the reverse direction, again our $𝒞$ machine will only read or write one bit per time step, and so we use the same $me{m}_i$ approach to simulating our additional $e\log c$ bits of free memory, which does not change based on the operation of the rest of the machine. As in the forward direction, simulating the actual workings of the $𝒞$ machine via the L$𝒞$ machine, given our method of simulating the $e\log c$ additional bits of memory, is straightforward, and our resetting step at the end again resets our extra catalytic tape regardless of the computation path the $𝒞$ machine takes. $◀$