Carsten Damm, Stasys Jukna, Jiri Sgall

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 >>>

Ilan Komargodski, Pravesh Kothari, Madhu Sudan

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 >>>

Scott Aaronson

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 >>>