Communication Complexity

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

• Junwei Yuan, Churchill College
• Wednesday 31 January 2018, 19:00-19:30
• Wolfson Hall, Churchill College.

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.

This talk is included in these lists:

• Churchill CompSci Talks
• Wolfson Hall, Churchill College
• computer science
• se393's list

Note that ex-directory lists are not shown.