We consider the $k$-layer pointer jumping problem in the one-way
multi-party number-on-the-forehead communication model. In this problem,
the input is a layered directed graph with each vertex having outdegree
$1$, shared amongst $k$ players: Player~$i$ knows all layers {\em
except} the $i$th. The players must communicate, in the order
$1,2,\ldots,k$, ... more >>>

A t-design for quantum states is a finite set of quantum states with the property of simulating the Haar-measure on quantum states w.r.t. any test that uses at most t copies of a state. We give efficient constructions for approximate quantum t-designs for arbitrary t.

We then show that an ... more >>>

It is well known that $\R^N$ has subspaces of dimension
proportional to $N$ on which the $\ell_1$ norm is equivalent to the
$\ell_2$ norm; however, no explicit constructions are known.
Extending earlier work by Artstein--Avidan and Milman, we prove that
such a subspace can be generated using $O(N)$ random bits.

... more >>>