ECCC-Report TR15-138https://eccc.weizmann.ac.il/report/2015/138Comments and Revisions published for TR15-138en-usWed, 26 Aug 2015 17:30:39 +0300
Revision 1
| Nonuniform catalytic space and the direct sum for space |
Vincent Girard,
Michal Koucky,
Pierre McKenzie
https://eccc.weizmann.ac.il/report/2015/138#revision1This paper initiates the study of $k$-catalytic branching programs, a nonuniform model of computation that is the counterpart to the uniform catalytic space model of Buhrman, Cleve, Koucky, Loff and Speelman (STOC 2014). A $k$-catalytic branching program computes $k$ boolean functions simultaneously on the same $n$-bit input. Each function has its own entry, accept and reject nodes in the branching program but internal nodes can otherwise be shared. The question of interest is to determine the conditions under which some form of a direct sum property for deterministic space can be shown to hold, or shown to fail.
We exhibit both cases. There are functions that are correlated in such a way that their direct sum fails: a significant amount of space can be saved by sharing internal computation among the $k$ functions. By contrast, direct sum is shown to hold in some special cases, such as for the family of functions $(l_1\circ (l_2\circ (\cdots (l_{n-1}\circ l_n)\cdots)$ where each $l_i$ is a literal on variable $x_i$, $1\leq i\leq n$ and each $\circ$ stands individually for either $\wedge$ or $\vee$.Wed, 26 Aug 2015 17:30:39 +0300https://eccc.weizmann.ac.il/report/2015/138#revision1
Paper TR15-138
| Nonuniform catalytic space and the direct sum for space |
Michal Koucky
https://eccc.weizmann.ac.il/report/2015/138This paper initiates the study of $k$-catalytic branching programs, a nonuniform model of computation that is the counterpart to the uniform catalytic space model of Buhrman, Cleve, Koucky, Loff and Speelman (STOC 2014). A $k$-catalytic branching program computes $k$ boolean functions simultaneously on the same $n$-bit input. Each function has its own entry, accept and reject nodes in the branching program but internal nodes can otherwise be shared. The question of interest is to determine the conditions under which some form of a direct sum property for deterministic space can be shown to hold, or shown to fail.
We exhibit both cases. There are functions that are correlated in such a way that their direct sum fails: a significant amount of space can be saved by sharing internal computation among the $k$ functions. By contrast, direct sum is shown to hold in some special cases, such as for the family of functions $(l_1\circ (l_2\circ (\cdots (l_{n-1}\circ l_n)\cdots)$ where each $l_i$ is a literal on variable $x_i$, $1\leq i\leq n$ and each $\circ$ stands individually for either $\wedge$ or $\vee$.Tue, 25 Aug 2015 16:36:00 +0300https://eccc.weizmann.ac.il/report/2015/138