Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with one-way communication:
TR95-044 | 18th September 1995
Carsten Damm, Stasys Jukna, Jiri Sgall

Some Bounds on Multiparty Communication Complexity of Pointer Jumping

We introduce the model of conservative one-way multiparty complexity
and prove lower and upper bounds on the complexity of pointer jumping.

The pointer jumping function takes as its input a directed layered
graph with a starting node and layers of nodes, and a single edge ... more >>>

TR15-064 | 19th April 2015
Ilan Komargodski, Pravesh Kothari, Madhu Sudan

Communication with Contextual Uncertainty

Revisions: 1

We introduce a simple model illustrating the role of context in communication and the challenge posed by uncertainty of knowledge of context. We consider a variant of distributional communication complexity where Alice gets some information $x$ and Bob gets $y$, where $(x,y)$ is drawn from a known distribution, and Bob ... more >>>

TR17-164 | 3rd November 2017
Scott Aaronson

Shadow Tomography of Quantum States

We introduce the problem of *shadow tomography*: given an unknown $D$-dimensional quantum mixed state $\rho$, as well as known two-outcome measurements $E_{1},\ldots,E_{M}$, estimate the probability that $E_{i}$ accepts $\rho$, to within additive error $\varepsilon$, for each of the $M$ measurements. How many copies of $\rho$ are needed to achieve this, ... more >>>

ISSN 1433-8092 | Imprint