Speaker: Anil Ada, McGill University
Title: Multiparty Communication Complexity of Composed Functions
In this talk we will discuss the multiparty 'number on the forehead' (NOF) model of communication complexity, which is a fundamental model with applications in circuit complexity, proof complexity, pseudorandom generators, branching programs and Ramsey theory. Our focus will be on "composed" functions (f of g); most of the well-known and studied functions in communication complexity have this structure and all the major open problems remain open in this setting.
The talk has three main parts:
1) In the first part, we study arguably the most important open problem in the NOF model: find an explicit function that is hard when the number of players is log n. We show that any function of the form (sym of g), where sym is any symmetric function and g is any function, can be computed efficiently, thereby ruling out some of the previously considered candidate functions to break the log n barrier. Until this work, such a result was known only when g is symmetric and "compressible" (Babai et al. 2004).
2) In the second part, we study the communication complexities of (majority of g), (mod_m of g), and (nor of g), where the latter two classes of functions generalize the well-known functions Generalized Inner Product = (mod_2 of and) and Disjointness = (nor of and) respectively. We characterize the communication complexity of these functions with respect to the choice of g. This allows us to answer an open question posed by Babai et al. (2004), and also show that these functions have polynomially related classical and quantum communication complexities. Previously, the focus has been on studying the communication complexity of (f of and) and (f of xor) for special choices of f.
3) In the third part, we discuss the connection between the NOF model withRamsey theory discovered by Chandra-Furst-Lipton (1983). This connection has been utilized to give surprising communication complexity upper bounds via known bounds on Ramsey numbers. In our work, we exploit the other direction: we give non-trivial bounds on Ramsey numbers via our protocol for (sym of g). We also discuss connections to an important open problem: find an explicit function that is hard in the deterministic model but easy in the randomized model when the number of players is 3.
This is joint work with Arkadev Chattopadhyay, Omar Fawzi and Phuong Nguyen.