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

Emanuele Viola

We exhibit an explicitly computable `pseudorandom' generator stretching $l$ bits into $m(l) = l^{\Omega(\log l)}$ bits that look random to constant-depth circuits of size $m(l)$ with $\log m(l)$ arbitrary symmetric gates (e.g. PARITY, MAJORITY). This improves on a generator by Luby, Velickovic and Wigderson (ISTCS '93) that achieves the same ... more >>>

Arkadev Chattopadhyay, Anil Ada

We extend the 'Generalized Discrepancy' technique suggested by Sherstov to the `Number on the Forehead' model of multiparty communication. This allows us to prove strong lower bounds of n^{\Omega(1)} on the communication needed by k players to compute the Disjointness function, provided $k$ is a constant. In general, our method ... more >>>

Alexander A. Sherstov

We study the set disjointness problem in the number-on-the-forehead model.

(i) We prove that $k$-party set disjointness has randomized and nondeterministic

communication complexity $\Omega(n/4^k)^{1/4}$ and Merlin-Arthur complexity $\Omega(n/4^k)^{1/8}.$

These bounds are close to tight. Previous lower bounds (2007-2008) for $k\geq3$ parties

were weaker than $n^{1/(k+1)}/2^{k^2}$ in all ...
more >>>

Alexander A. Sherstov

We prove that the set disjointness problem has randomized communication complexity

$\Omega(\sqrt{n}/2^{k}k)$ in the number-on-the-forehead model with $k$ parties, a quadratic improvement

on the previous bound $\Omega(\sqrt{n}/2^{k})^{1/2}$. Our result remains valid for quantum

protocols, where it is essentially tight. Proving it was an open problem since 1997, ...
more >>>

Vladimir Podolskii, Alexander A. Sherstov

A basic goal in complexity theory is to understand the communication complexity of number-on-the-forehead problems $f\colon(\{0,1\}^n)^{k}\to\{0,1\}$ with $k\gg\log n$ parties. We study the problems of inner product and set disjointness and determine their randomized communication complexity for every $k\geq\log n$, showing in both cases that $\Theta(1+\lceil\log n\rceil/\log\lceil1+k/\log n\rceil)$ bits are ... more >>>