The simplicity and generality of communication complexity makes it useful in other interactive models. Diverse examples include streaming, data structures, distributed computation and property testing. In many application areas, the reduction to communication complexity results in protocols with a special structure, e.g., one-way (streaming), bounded rounds or asymmetric protocols (data structures). Different sub-communities have often developed their own set of techniques for proving stronger communication lower bounds under the protocol restrictions occurring from their concrete reductions. Even though several of these restrictions arise in multiple application areas (e.g., one-way communication protocols arise both in streaming and in “encoding" proofs for data structures), researchers in the different areas have traditionally been quite segregated.
In this workshop, we will bring together both core communication complexity researchers, as well as researchers from the different areas relying on communication complexity, in order to strengthen cross-area collaboration, prove new and more general theorems, and expand the scope of their applications.
Further details about this workshop will be posted in due course.
Paul Beame (University of Washington), Joshua Brody (Swarthmore College), Amit Chakrabarti (Dartmouth College), Diptarka Chakraborty (Charles University), Arkadev Chattopadhyay (Tata Institute of Fundamental Research), Raphael Clifford (University of Bristol), Faith Ellen (University of Toronto), Anna Gál (University of Texas at Austin), Sumegha Garg (Princeton University), T.S. Jayram (IBM Almaden), Lior Kamma (Aarhus University), Michael Kapralov (Ecole Polytechnique Federale de Lausanne), Michal Koucky (Charles University), Kasper Larsen (Aarhus University), Troy Lee (Nanyang Technological University), Shachar Lovett (UC San Diego), Andrew McGregor (University of Massachusetts Amherst), Siva Natarajan Ramamoorthy (University of Washington), Rotem Oshman (Tel Aviv University), Toni Pitassi (University of Toronto), Mike Saks (Rutgers University), Sasha Sherstov (UCLA), Justin Thaler (Yahoo Labs), Emanuele Viola (NEU), Thomas Watson (University of Memphis), Omri Weinstein (Columbia University), Grigory Yaroslavtsev (Indiana University, Bloomington), Amir Yehudayoff (Technion Israel Institute of Technology), Huacheng Yu (Harvard University), Qin Zhang (Indiana University Bloomington)