|
Abstract : |
Abstract. 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 GAFG;k, where G is a nite group and k denotes the number of players, plays an important role in SM complexity. In particular, lower bounds on SM complexity of GAFG;k were used in [PRS] and [BKL] to show that the SM model is exponentially weaker than the general communication model [CFL] for suciently small number of players. Moreover, certain unexpected upper bounds from [PRS] and [BKL] on SM complexity of GAFG;k have led to rened formulations of certain approaches to circuit lower bounds. In this paper, we show improved upper bounds on the SM complexity of GAFZ, |
