BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Communication Complexity and When Dubious Data Structures can be D
 etected - Ranganath Kondapally\, Dartmouth College
DTSTART:20120329T080000Z
DTEND:20120329T090000Z
UID:TALK37174@talks.cam.ac.uk
CONTACT:Microsoft Research Cambridge Talks Admins
DESCRIPTION:Communication complexity is one of the most general and useful
  techniques for proving lower bounds in theoretical computer science. For 
 example\, it has been used to prove lower bounds in data structures\, circ
 uits\, pseudorandomness\, data streaming\, and property testing. Communica
 tion problems capture the innate hardness of many problems and therefore t
 heir lower bounds can be leveraged to prove lower bounds on a variety of a
 pplications. In this talk\, I will present the problem of detecting dubiou
 s data structures and show lower bounds for it using communication complex
 ity.\n\nSuppose we have access to an untrusted implementation of a data st
 ructure\, hosted Somewhere In The Cloud. We engage this data structure in 
 a (very) long session of operations\, resulting in an interaction stream. 
 Can we decide whether the data structure worked correctly\, using much les
 s space than it would take to reimplement its functionality? This question
  is one of a large and growing class of questions on Data Stream Algorithm
 s\, i.e.\, algorithms that get to access their input only in streaming---r
 ather than random-access---fashion\, and must use space sublinear in the i
 nput size. We shall see that the answer to our particular question is "Yes
 "\, for several natural data structures\, including priority queues\, stac
 ks\, queues and dequeues.\n\nI will present the outline of our algorithm t
 hat uses O(sqrt(n)) space in the worst case and also prove that this space
  bound is tight using a novel information theoretic lower bound for a comm
 unication game called Augmented Index.\n\n(Joint work with Chakrabarti\, C
 ormode\, and McGregor)\n
LOCATION:Small lecture theatre\, Microsoft Research Ltd\, 7 J J Thomson Av
 enue (Off Madingley Road)\, Cambridge
END:VEVENT
END:VCALENDAR