Hamoudi, Yassine
Simultaneous Multiparty Communication Protocols for Composed Functions
Abstract
The Number On the Forehead (NOF) model is a multiparty communication game between k players that collaboratively want to evaluate a given function F : X_1 x *s x X_k  > Y on some input (x_1,...,x_k) by broadcasting bits according to a predetermined protocol. The input is distributed in such a way that each player i sees all of it except x_i (as if x_i is written on the forehead of player i). In the Simultaneous Message Passing (SMP) model, the players have the extra condition that they cannot speak to each other, but instead send information to a referee. The referee does not know the players' inputs, and cannot give any information back. At the end, the referee must be able to recover F(x_1,...,x_k) from what she obtained from the players.
A central open question in the simultaneous NOF model, called the log n barrier, is to find a function which is hard to compute when the number of players is polylog(n) or more (where the x_i's have size poly(n)). This has an important application in circuit complexity, as it could help to separate ACC^0 from other complexity classes [Håstad and Goldmann, 1991; Babai et al., 2004]. One of the candidates for breaking the log n barrier belongs to the family of composed functions. The input to these functions in the kparty NOF model is represented by a k x (t * n) boolean matrix M, whose row i is the number x_i on the forehead of player i and t is a blockwidth parameter. A symmetric composed function acting on M is specified by two symmetric n and ktvariate functions f and g (respectively), that output f o g(M) = f(g(B_1),...,g(B_n)) where B_j is the jth block of width t of M. As the majority function Maj is conjectured to be outside of ACC^0, Babai et. al. [Babai et al., 1995; Babai et al., 2004] suggested to study the composed function Maj o Maj_t, with t large enough, for breaking the log n barrier (where Maj_t outputs 1 if at least kt/2 bits of the input block are set to 1).
So far, it was only known that blockwidth t = 1 is not enough for Maj o Maj_t to break the log n barrier in the simultaneous NOF model [Babai et al., 2004] (Chattopadhyay and Saks [Chattopadhyay and Saks, 2014] found an efficient protocol for t <= polyloglog(n), but it requires randomness to be simultaneous). In this paper, we extend this result to any constant blockwidth t > 1 by giving a deterministic simultaneous protocol of cost 2^O(2^t) log^(2^(t+1))(n) for any symmetric composed function f o g (which includes Maj o Maj_t) when there are more than 2^Omega(2^t) log n players.
BibTeX  Entry
@InProceedings{hamoudi:LIPIcs:2018:9596,
author = {Yassine Hamoudi},
title = {{Simultaneous Multiparty Communication Protocols for Composed Functions}},
booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
pages = {14:114:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770866},
ISSN = {18688969},
year = {2018},
volume = {117},
editor = {Igor Potapov and Paul Spirakis and James Worrell},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9596},
URN = {urn:nbn:de:0030drops95969},
doi = {10.4230/LIPIcs.MFCS.2018.14},
annote = {Keywords: Communication complexity, Number On the Forehead model, Simultaneous Message Passing, Log n barrier, Symmetric Composed functions}
}
27.08.2018
Keywords: 

Communication complexity, Number On the Forehead model, Simultaneous Message Passing, Log n barrier, Symmetric Composed functions 
Seminar: 

43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Issue date: 

2018 
Date of publication: 

27.08.2018 