Communication Complexity
First two lectures on Monday August 27 and Tuesday August 28 at
10:15-12:00 in seminar room 1537 on Osquars backe 2, 5th floor.
Tid: Må 2012-08-27 kl 10.15 - 12.00
Plats: Seminar room 1537, Osquars backe 2, 5th floor
More information at
www.csc.kth.se/utbildning/kth/kurser/DD2441/semteo12/
.
Brief Course Description
Alice and Bob need to solve a problem together and have all imaginable computational powers at their disposal. The only snag is that the problem input has been split among them, they are far apart, and communicating is expensive. Obviously, Bob could just send his part of the input to Alice and have her solve the whole problem on her own --- she can do NP-complete problems or beyond easily --- but that is far too costly in terms of communication.
Is there anything smarter they can do? And why should we care about this seemingly stupid scenario anyway? Because it turns out that it is key to understanding e.g.:
- Optimal data structures for efficient storage and fast retrieval.
- Streaming algorithms working on data so large that we can just make a pass over it but not store it in memory.
- Testing algorithms detecting properties of huge data sets so quickly that only a fraction of the input can even be read in the first place.
- SAT solving, i.e., computing whether logic formulas are satisfiable (a problem of immense practical importance that has to be solved despite that it is NP-complete).
- And more...
This course will cover some exciting results in this area and bring students right up to the research frontier. We will also have some guest lectures by leading international experts.