ECCC-Report TR22-026https://eccc.weizmann.ac.il/report/2022/026Comments and Revisions published for TR22-026en-usSun, 20 Feb 2022 14:27:11 +0200
Paper TR22-026
| Trading Time and Space in Catalytic Branching Programs |
Ian Mertz,
James Cook
https://eccc.weizmann.ac.il/report/2022/026An $m$-catalytic branching program (Girard, Koucky, McKenzie 2015) is a set of $m$ distinct branching programs for $f$ which are permitted to share internal (i.e. non-source non-sink) nodes. While originally introduced as a non-uniform analogue to catalytic space, this also gives a natural notion of amortized non-uniform space complexity for $f$, namely the smallest value $|G|/m$ for an $m$-catalytic branching program $G$ for $f$ (Potechin 2017).
Potechin (2017) showed that every function $f$ has amortized size $O(n)$, witnessed by an $m$-catalytic branching program where $m = 2^{2^n-1}$. We recreate this result by defining a catalytic algorithm for evaluating polynomials using a large amount of space but $O(n)$ time. This allows us to balance this with previously known algorithms which are efficient with respect to space at the cost of time (Cook, Mertz 2020, 2021). We show that for any $\epsilon \geq 2n^{-1}$, every function $f$ has an $m$-catalytic branching program of size $O_\epsilon(mn)$, where $m = 2^{2^{\epsilon n}}$. We similarly recreate an improved result due to Robere and Zuiddam (2021), and show that for $d \leq n$ and $\epsilon \geq 2d^{-1}$, the same result holds for $m = 2^{n \choose \leq \epsilon d}$ as long as $f$ is a degree-$d$ polynomial over $\mathbb{F}_2$. We also show that for certain classes of functions, $m$ can be reduced to $2^{poly(n)}$ while still maintaining linear or quasi-linear amortized size.
In the other direction, we bound the necessary length, and by extension the amortized size, of any permutation branching program for an arbitrary function between $3n$ and $4n-4$.Sun, 20 Feb 2022 14:27:11 +0200https://eccc.weizmann.ac.il/report/2022/026