Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with multiparty communication complexity:
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 >>>

TR05-043 | 5th April 2005
Emanuele Viola

Pseudorandom Bits for Constant-Depth Circuits with Few Arbitrary Symmetric Gates

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

TR08-002 | 19th December 2007
Arkadev Chattopadhyay, Anil Ada

Multiparty Communication Complexity of Disjointness

Revisions: 3

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

TR11-145 | 2nd November 2011
Alexander A. Sherstov

The Multiparty Communication Complexity of Set Disjointness

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

TR13-005 | 2nd January 2013
Alexander A. Sherstov

Communication Lower Bounds Using Directional Derivatives

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

TR17-184 | 29th November 2017
Vladimir Podolskii, Alexander A. Sherstov

Inner Product and Set Disjointness: Beyond Logarithmically Many Parties

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

TR19-016 | 5th February 2019
Alexander A. Sherstov

The hardest halfspace

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

TR20-184 | 10th December 2020
Dmitry Itsykson, Artur Riazanov

Proof complexity of natural formulas via communication arguments

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

ISSN 1433-8092 | Imprint