Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > MULTIPARTY COMMUNICATION:
Reports tagged with Multiparty communication:
TR07-050 | 25th May 2007

#### Discrepancy and the power of bottom fan-in in depth-three circuits

We develop a new technique of proving lower bounds for the randomized communication complexity of boolean functions in the multiparty 'Number on the Forehead' model. Our method is based on the notion of voting polynomial degree of functions and extends the Degree-Discrepancy Lemma in the recent work of Sherstov (STOC'07). ... more >>>

TR12-004 | 10th January 2012
Marcos Villagra, Masaki Nakanishi, Shigeru Yamashita, Yasuhiko Nakashima

#### Tensor Rank and Strong Quantum Nondeterminism in Multiparty Communication

Revisions: 3

In this paper we study quantum nondeterminism in multiparty communication. There are three (possibly) different types of nondeterminism in quantum computation: i) strong, ii) weak with classical proofs, and iii) weak with quantum proofs. Here we focus on the first one. A strong quantum nondeterministic protocol accepts a correct input ... more >>>

TR16-111 | 20th July 2016
Amit Chakrabarti, Sagar Kale

#### Strong Fooling Sets for Multi-Player Communication with Applications to Deterministic Estimation of Stream Statistics

We develop a paradigm for studying multi-player deterministic communication,
based on a novel combinatorial concept that we call a {\em strong fooling
communication required for solving multi-player $\textsc{equality}$
problems in a private-message setting. This in turn gives a ... more >>>

TR16-138 | 3rd September 2016
Alexander A. Sherstov

#### On multiparty communication with large versus unbounded error

The communication complexity of $F$ with unbounded error is the limit of the $\epsilon$-error randomized complexity of $F$ as $\epsilon\to1/2.$ Communication complexity with weakly bounded error is defined similarly but with an additive penalty term that depends on $1/2-\epsilon$. Explicit functions are known whose two-party communication complexity with unbounded error ... more >>>

TR17-095 | 26th May 2017
Ran Gelles, Yael Tauman Kalai

#### Constant-Rate Interactive Coding Is Impossible, Even In Constant-Degree Networks

Multiparty interactive coding allows a network of $n$ parties to perform distributed computations when the communication channels suffer from noise. Previous results (Rajagopalan and Schulman, STOC '94) obtained a multiparty interactive coding protocol, resilient to random noise, with a blowup of $O(\log(\Delta+1))$ for networks whose topology has a maximal degree ... more >>>

ISSN 1433-8092 | Imprint