Designing algorithms for space bounded models with restoration requirements on (most of) the space used by the algorithm is an important challenge posed about the catalytic computation model introduced by Buhrman et al (2014). Motivated by the scenarios where we do not need to restore unless $w$ is "useful", we relax the restoration requirement: only when the content of the catalytic tape is $w \in A \subseteq \Sigma^*$, the catalytic Turing machine needs to restore $w$ at the end of the computation. We define, $ACL(A)$ to be the class of languages that can be accepted by almost-catalytic Turing machines with respect to $A$ (which we call the catalytic set), that uses at most $c\log n$ work space and $n^c$ catalytic space. We prove the following for the almost-catalytic model.
- We show that if there are almost-catalytic algorithms for a problem with catalytic set as $A \subseteq \Sigma^*$ and its complement respectively, then the problem can be solved by a zero-error randomized algorithm that runs in expected polynomial time. More formally, for any language $A \subseteq \Sigma^*$, $ACL(A) \cap ACL(\overline{A}) \subseteq ZPP$. In particular, when $A \in LOG$, $ACL(A) \cap ACL(\overline{A}) = CL$. This leads to newer algorithmic approaches for designing catalytic algorithms.
- Using the above, we derive that to design catalytic algorithms for a language, it suffices to design almost-catalytic algorithms where the catalytic set is the set of strings of odd weight ($PARITY$).
Towards this, we consider two complexity measures of the set $A$ which are maximized for $PARITY$. One is the random projection complexity (denoted by ${\cal R}(A)$) and the other is the subcube partition complexity (denoted by ${\cal P}(A)$). We show that, for all $k \ge 1$, there exists a language $A_k \subseteq \Sigma^* $ such that $DSPACE(n^k) \subseteq ACL(A_k)$ where for every $m \ge 1$, ${\cal R}(A_k \cap \{0,1\}^m) \ge \frac{m}{4}$ and ${\cal P}(A_k \cap \{0,1\}^m)=2^{m/4}$. This is in contrast to the catalytic machine model where it is unclear if it can accept all languages in $DSPACE(\log^{1+\epsilon} n)$ for any $\epsilon > 0$.
- Improving the partition complexity of the restoration set $A$ further, we show that for all $k \ge 1$, there exists $A_k \subseteq \{0,1\}^*$ such that $DSPACE(\log^k n) \subseteq ACL(A_k)$ where for every $m \ge 1$, ${\cal R}(A_k \cap \{0,1\}^m) \ge \frac{m}{4}$ and ${\cal P}(A_k \cap \{0,1\}^m)=2^{m/4+\Omega(\log m)}$. Our main new technique for the last two items is the use of error correcting codes to design almost-catalytic algorithms.
- We also show that, even when there are more than two alphabet symbols, if the catalytic set $A$ does not use one of the alphabet symbols, then efficient almost-catalytic algorithms with $A$ as the catalytic set can be designed for any language in $PSPACE$.
