Given a problem whose input is split between Alice and Bob, how much do they need to communicate in order to solve it?
This question has been studied extensively in cases where the answer grows poly-logarithmically in terms of the input sizes.
However, relatively little attention has been directed at the constant-cost regime: where communication complexity is independent of the input size.
This very intricate class of functions evades all established proof-techniques and is thus still very poorly understood.
I will motivate the study of these objects by presenting some of our recent progress in this area, featuring an exciting mix of new methods involving
Geometry, Linear Algebra, Ramsey Theory, the Combinatorial Nullstellensatz, Rank Methods, and a crucial fact about hypercubes first observed by Paul Erdős.
