University of Cambridge > > Churchill CompSci Talks > Communication Complexity

Communication Complexity

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Matthew Ireland.

Note unusual time

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.

This talk is part of the Churchill CompSci Talks series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2024, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity