| Résume | In the standard two-party communication complexity framework, introduced by Yao in the 70s, we study the amount of communication required for two parties to compute a fixed function of their two private inputs. A variant of this model, known as *Multipartition Communication Complexity* was introduced by Duris, Hromkovic, Jukna, Sauerhoff, and Schnitger in 2001 and allows for much more general "communication protocols". We show how to prove lower bounds for some simple explicit functions in this model using expander graphs. We use this to prove optimal separations between monotone algebraic circuits and non-monotone algebraic circuits.
Joint work with Bruno Cavalar (Oxford), Théo Borém Fabris (University of Copenhagen), Partha Mukhopadhyay (Chennai Mathematical Institute) and Amir Yehudayoff (University of Copenhagen). The paper is here: https://arxiv.org/abs/2512.19515 and will appear in the upcoming conference STOC 2026. |
