Speaker: Joshua Brody
Title: Communication Complexity and You: A Winning Combination
Abstract: Communication Complexity has been used to prove lower bounds and hardness
results in a wide variety of domains, from the theoretical (circuit complexity,
proof complexity) to the practical (streaming algorithms, data structures, etc.)
In this talk I'll present some recent results on two communication problems:
Gap Hamming Distance and Multiparty Pointer Jumping. The Gap Hamming Distance
problem captures the hardness of computing certain functions on data streams,
even when randomness and approximation are used. Proving sufficiently strong
lower bounds for Multiparty Pointer Jumping would resolve a major open question
in circuit complexity.
Despite the different nature of the applications, the lower-bounds proofs in
each problem use similar techniques, which should be useful in other problems as
The results on Gap Hamming Distance are joint work with Amit Chakrabarti, Oded
Regev, Thomas Vidick, and Ronald de Wolf. This talk assumes no prior
knowledge of communication complexity.