BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Communication Complexity - Junwei Yuan\, Churchill College
DTSTART:20180131T190000Z
DTEND:20180131T193000Z
UID:TALK100576@talks.cam.ac.uk
CONTACT:Matthew Ireland
DESCRIPTION:In modern days\, communication has become a significant bottle
 neck to computation\, especially in domains like distributed systems and V
 LSI circuits. This presents a mismatch with the more usual time/space comp
 lexity theories which lets us understand the power and limits of computati
 on. The study of communication complexity addresses this issue\, defining 
 concrete communication-based models of computation and notions of complexi
 ty based on such models. Perhaps surprisingly\, communication complexity h
 as also proven to be a fruitful avenue to showing lower bounds on problems
  that have no relation to communication at all.\n\nIn 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-r
 ank" lower bound on such complexity notion. We will also briefly explore a
  connection between communication complexity and the usual time/space mode
 l. As an application\, we shall prove a (tight) space-time tradeoff theore
 m concerning the tradeoff between the time/space complexities of any algor
 ithm deciding if a string is a palindrome.
LOCATION:Wolfson Hall\, Churchill College
END:VEVENT
END:VCALENDAR