Communication complexity is the study of how two or more parties with private inputs compute a function that depends on all their inputs. The scarce resource is communication, or the number of bits exchanged between the parties. What is amazing about this field is that it has applications not only in areas where there is actual communication between parties, such as auction design and distributed computing, but also in areas which superficially may seem completely unrelated to communication, such as graph streaming and data structures. This is because bounds on communication can often be translated into bounds on other resources of interest, such as memory and the number of wires.
In this talk, I will cover my work in developing and applying new communication complexity tools to mechanism design, streaming algorithms, error-resilient circuits, and interactive coding, with a special focus on the latter. Specifically, I shall cover two of my recent results [EKS20a] and [EKSZ22], that develop new codes resilient to a larger fraction of noise than the previous state-of-the-art. In the case of [EKSZ22], I will also explain why our result opens a whole new paradigm for error correcting codes that was previously unexplored. No prior background will be assumed.
