Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > COMPOSED FUNCTIONS:
Reports tagged with composed functions:
TR11-155 | 22nd November 2011

#### The NOF Multiparty Communication Complexity of Composed Functions

We study the $k$-party `number on the forehead' communication complexity of composed functions $f \circ \vec{g}$, where $f:\{0,1\}^n \to \{\pm 1\}$, $\vec{g} = (g_1,\ldots,g_n)$, $g_i : \{0,1\}^k \to \{0,1\}$ and for $(x_1,\ldots,x_k) \in (\{0,1\}^n)^k$, $f \circ \vec{g}(x_1,\ldots,x_k) = f(\ldots,g_i(x_{1,i},\ldots,x_{k,i}), \ldots)$. When $\vec{g} = (g,g,\ldots,g)$ we denote $f \circ \vec{g}$ by ... more >>>

TR21-065 | 5th May 2021
Nikhil Mande, Swagato Sanyal

#### One-way communication complexity and non-adaptive decision trees

Revisions: 1

We study the relationship between various one-way communication complexity measures of a composed function with the analogous decision tree complexity of the outer function. We consider two gadgets: the AND function on 2 inputs, and the Inner Product on a constant number of inputs. Let $IP$ denote Inner Product on ... more >>>

ISSN 1433-8092 | Imprint