Swarthmore College Department of Computer Science

Joshua Brody: Communication Complexity

profile picture

My current research interests are in communication complexity and related applications including data structure lower bounds, property testing, and streaming algorithms. In a typical communication complexity problem, input is distributed to multiple players who wish to compute some joint function of their input. Since no one players knows the entire input, they must communicate to compute the function. Communication complexity is the study of how much players need to communicate to compute a particular function.

Communication complexity is an unusual subfield of computer science for two reasons. First, we have a wide range of tools for proving unconditional lower bounds in communication complexity. For example, if Alice and Bob each have n-bit inputs and want to deterministically check to see whether their inptus are equal, we know that at least n bits must be exchanged, no matter how powerful Alice and Bob are. Secondly, it's possible to apply communication lower bounds to prove unconditional lower bounds in a wide range of other areas, including VLSI chip design, data structures, proof complexity, streaming algorithms, and property testing.

I am interested both in developing tools for proving communication complexity lower bounds, and in applying those lower bounds to other areas. Recently, I have been using tools from information theory and random graph theory to prove communication lower bounds, and I have applied them to prove lower bounds for dynamic data structures and for property testing algorithms. For more information about my research, please check out some of my research papers, listed below:

Research papers: https://www.cs.swarthmore.edu/~brody/research.php