Abstract

In modern days, communication has become a significant bottleneck to computation, especially in domains like distributed systems and VLSI circuits. This presents a mismatch with the more usual time/space complexity theories which lets us understand the power and limits of computation. The study of communication complexity addresses this issue, defining concrete communication-based models of computation and notions of complexity based on such models. Perhaps surprisingly, communication complexity has also proven to be a fruitful avenue to showing lower bounds on problems that have no relation to communication at all.

In this talk, we will examine the standard two-party model of computation, define the notion of deterministic communication complexity and prove the commonly used “log-rank” lower bound on such complexity notion. We will also briefly explore a connection between communication complexity and the usual time/space model. As an application, we shall prove a (tight) space-time tradeoff theorem concerning the tradeoff between the time/space complexities of any algorithm deciding if a string is a palindrome.