Improved upper bounds on the simultaneous messages complexity of the Generalized Addressing Function

We study communication complexity in the model of Simultaneous Messages (SM). The SM model is a restricted version of the well-known multiparty communication complexity model [CFL, KN]. Motivated by connections to circuit complexity, lower and upper bounds on the SM complexity of several explicit functions have been intensively investigated in [PR, PRS, BKL, Am1, BGKL]. A class of functions called the Generalized Addressing Functions (GAF), denoted GAF_{G, k}, where G is a finite group and k denotes the number of players, plays an important role in SM complexity. In particular, lower bounds on SM complexity of GAF_{G, k} were used in [PRS] and [BKL] to show that the SM model is exponentially weaker than the general communication model [CFL] for sufficiently small number of players. Moreover, certain unexpected upper bounds from [PRS] and [BKL] on SM complexity of GAF_{G, k} have led to refined formulations of certain approaches to circuit lower bounds. In this paper, we show improved upper bounds on the SM complexity of GAF _Z^t_{2, k}. In particular, when there are three players (k = 3), we give an upper bound of O(n^0.73), where n = 2t. This improves a bound of O(n^0.92) from [BKL]. The lower bound in this case is ω (√n) [BKL, PRS]. More generally, for the k player case, we prove an upper bound of O(n^{H (1/(2k-2))}) improving a bound of O(n^H(1/k)) from [BKL], where H(·) denotes the binary entropy function. For large enough k, this is nearly a quadratic improvement. The corresponding lower bound is ω^(n1/(k-1)/(k - 1)) [BKL, PRS]. Our proof extends some algebraic techniques from [BKL] and employs a greedy construction of covering codes.