Fall 2018

Interactive Complexity

Oct. 15Oct. 18, 2018

Add to Calendar


Kasper Green Larsen (Aarhus University; chair), Mark Braverman (Princeton University), Michael Saks (Rutgers University)
Interactive complexity is the study of the computational complexity of tasks that require interaction between two or more parties. A key model in this area is communication complexity, which studies the number of bits players need to exchange in order to achieve a common goal. Communication complexity is one of the few models in which we know how to prove very strong and often optimal lower bounds. This success has come through the development and application of a range of techniques including information theory, harmonic analysis, Ramsey theory, discrepancy and more. Nonetheless, several core questions still remain open, such as the direct-sum problem and the log-rank conjecture.

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.

Invited Participants: 

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)