Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > ONE-WAY PROTOCOLS:
Reports tagged with one-way protocols:
TR03-083 | 21st November 2003
Jan Arpe, Andreas Jakoby, Maciej Liskiewicz

#### One-Way Communication Complexity of Symmetric Boolean Functions

We study deterministic one-way communication complexity
of functions with Hankel communication matrices.
Some structural properties of such matrices are established
and applied to the one-way two-party communication complexity
of symmetric Boolean functions.
It is shown that the number of required communication bits
does not depend on ... more >>>

TR20-131 | 20th August 2020
Rahul Jain, Srijita Kundu

#### A Direct Product Theorem for One-Way Quantum Communication

We prove a direct product theorem for the one-way entanglement-assisted quantum communication complexity of a general relation $f\subseteq\mathcal{X}\times\mathcal{Y}\times\mathcal{Z}$. For any $\varepsilon, \zeta > 0$ and any $k\geq1$, we show that
$\mathrm{Q}^1_{1-(1-\varepsilon)^{\Omega(\zeta^6k/\log|\mathcal{Z}|)}}(f^k) = \Omega\left(k\left(\zeta^5\cdot\mathrm{Q}^1_{\varepsilon + 12\zeta}(f) - \log\log(1/\zeta)\right)\right),$
where $\mathrm{Q}^1_{\varepsilon}(f)$ represents the one-way entanglement-assisted quantum communication complexity of $f$ with ... more >>>

ISSN 1433-8092 | Imprint