BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Churchill CompSci Talks
SUMMARY:Communication Complexity - Junwei Yuan\, Churchill
College
DTSTART;TZID=Europe/London:20180131T190000
DTEND;TZID=Europe/London:20180131T193000
UID:TALK100576AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/100576
DESCRIPTION:In modern days\, communication has become a signif
icant bottleneck to computation\, especially in do
mains 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\, d
efining concrete communication-based models of com
putation and notions of complexity based on such m
odels. Perhaps surprisingly\, communication comple
xity has also proven to be a fruitful avenue to sh
owing lower bounds on problems that have no relati
on to communication at all.\n\nIn this talk\, we w
ill examine the standard two-party model of comput
ation\, define the notion of deterministic communi
cation complexity and prove the commonly used "log
-rank" lower bound on such complexity notion. We w
ill also briefly explore a connection between comm
unication complexity and the usual time/space mode
l. As an application\, we shall prove a (tight) sp
ace-time tradeoff theorem concerning the tradeoff
between the time/space complexities of any algorit
hm deciding if a string is a palindrome.
LOCATION:Wolfson Hall\, Churchill College
CONTACT:Matthew Ireland
END:VEVENT
END:VCALENDAR