The classical model of communication complexity, introduced by Yao, has been an object of intense study over the years with many applications to complexity theory, including circuit complexity, proof complexity, extended formulations and so on. I will define a relatively understudied version of this communication model called Multipartition communication complexity, which was introduced in work of Duriš, Hromkovič, Jukna, Sauerhoff, and Schnitger. Using a suitable lower bound for this model, we can derive a nearly optimal monotone vs. non-monotone separation for algebraic circuits, which I will sketch. Joint work with Cavalar, Fabris, Mukhopadhyay and Yehudayoff.
Bio: Srikanth Srinivasan received his PhD in 2011 from IMSc in Chennai, where he was advised by V Arvind. He is on the faculty at the computer science department (DIKU) at the University of Copenhagen after having spent time at IAS, DIMACS, IIT Bombay (Mathematics dept) and Aarhus University. His research interests span all of theoretical computer science in theory but in practice are limited to complexity theory and adjacent areas.
