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

Alexander A. Sherstov

We study the approximation of halfspaces $h:\{0,1\}^n\to\{0,1\}$ in the infinity norm by polynomials and rational functions of any given degree. Our main result is an explicit construction of the "hardest" halfspace, for which we prove polynomial and rational approximation lower bounds that match the trivial upper bounds achievable for all ... more >>>

Dmitry Itsykson, Artur Riazanov

A canonical communication problem ${\rm Search}(\phi)$ is defined for every unsatisfiable CNF $\phi$: an assignment to the variables of $\phi$ is distributed among the communicating parties, they are to find a clause of $\phi$ falsified by this assignment. Lower bounds on the randomized $k$-party communication complexity of ${\rm Search}(\phi)$ in ... more >>>