Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

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

#### Nonuniform catalytic space and the direct sum for space

Revision #1
Authors: Vincent Girard, Michal Koucky, Pierre McKenzie
Accepted on: 26th August 2015 17:30
Downloads: 464
Keywords:

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

TR15-138
Authors: Michal Koucky
Publication: 25th August 2015 16:36
Downloads: 829
Keywords:

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