摘要：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 k-party 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 block-width parameter. A symmetric composed function acting on M is specified by two symmetric n- and kt-variate functions f and g (respectively), that output f o g(M) = f(g(B_1),...,g(B_n)) where B_j is the j-th 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 block-width 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 block-width 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.
关键词：Communication complexity; Number On the Forehead model; Simultaneous Message Passing; Log n barrier; Symmetric Composed functions
