Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR15-138 | 26th August 2015 17:30

Nonuniform catalytic space and the direct sum for space

RSS-Feed

Abstract:

This 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$.



Changes to previous version:

Corrected list of authors.


Paper:

TR15-138 | 25th August 2015 10:55

Nonuniform catalytic space and the direct sum for space


Abstract:

This 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$.



ISSN 1433-8092 | Imprint