Communication Complexity represents one of the premier techniques for proving lower bounds in theoretical computer science. Lower bounds on communication problems can be leveraged to prove lower bounds in several different areas. In this talk, I'll present three different communication complexity problems. The lower bounds for these problems have applications in circuit complexity, wireless sensor networks,and streaming algorithms. No prior knowledge of communication complexity is assumed.

Joshua Brody is a postdoc at ITCS, Tsinghua University. He received his Ph.D. in September 2010 from Dartmouth College, working under Amit Chakrabarti. Prior to Dartmouth College, Joshua obtained a B.S. (1997) from Carnegie Mellon University, and an M.S. (2005) from NYU.