About
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.
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.
Chairs/Organizers
Invited Participants
Eric Allender (Rutgers University), Joshua Brody (Swarthmore College), Mark Bun (Princeton University), Igor Carboni Oliveira (University of Oxford), Marco Carmosino (UC San Diego), Amit Chakrabarti (Dartmouth College), Diptarka Chakraborty (Charles University), Arkadev Chattopadhyay (Tata Institute of Fundamental Research), Lijie Chen (MIT), Faith Ellen (University of Toronto), Anna Gál (University of Texas at Austin), Venkata Gali (UC San Diego), Sumegha Garg (Princeton University), Johan Håstad (KTH), Hamed Hatami (McGill University), Xuangui Huang (Northeastern University), Christian Ikenmeyer (Max-Planck-Institut für Informatik), T.S. Jayram (IBM Almaden Research), Valentine Kabanets (Simon Fraser University), John Kallaugher (University of Texas at Austin), Lior Kamma (Aarhus University), Michael Kapralov (Ecole Polytechnique Federale de Lausanne (EPFL)), Matthew Katzman (University of Oxford), Antonina Kolokolova (Memorial University of Newfoundland), Michal Koucky (Charles University), Mrinal Kumar (Harvard University), Troy Lee (University of Technology Sydney), Yaqiao Li (McGill University), Nutan Limaye (Indian Institute of Technology Bombay), Shachar Lovett (UC San Diego), Andrew McGregor (University of Massachusetts Amherst), Or Meir (University of Haifa), Rafael Mendes de Oliveira (University of Toronto), Andrew Morgan (University of Wisconsin, Madison), Cody Murray (MIT), Vishvajeet Nagargoje (Rutgers University), Siva Natarajan Ramamoorthy (University of Washington), Jakob Nordström (KTH Royal Institute of Technology), Rotem Oshman (Tel Aviv University), Rasmus Pagh (IT University of Copenhagen), Toni Pitassi (University of Toronto), Pavel Pudlák (Academy of Sciences of the Czech Republic), Robert Robere (University of Toronto), Ben Rossman (University of Toronto), Rahul Santhanam (University of Oxford), Sasha Sherstov (UCLA), Morgan Shirley (University of Toronto), Srikanth Srinivasan (Indian Institute of Technology Bombay), Madhu Sudan (Harvard University), Joseph Swernofsky (KTH), Avishay Tal (Stanford University), Justin Thaler (Yahoo Labs), Thomas Watson (University of Memphis), Omri Weinstein (Columbia University), Ryan Williams (MIT), Grigory Yaroslavtsev (Indiana University, Bloomington), Amir Yehudayoff (Technion Israel Institute of Technology), Huacheng Yu (Harvard University), Richard Zemel (University of Toronto), Qin Zhang (Indiana University Bloomington)