2D2441 Seminars on Theoretical Computer Science 6 ECTS Credits

This is a course in theoretical computer science which is given at somewhat irregular intervals and with varying content.

In the autumn of 2012, the course will focus on communication complexity. More information follows below, and closer to the start date of the course there will also be dedicated webpages for the current round of the course [link currently broken].

DD2441 Communication Complexity, 6 ECTS Credits, Autumn 2012

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 the fact that it is NP-complete).
• And more…

The course will cover some exciting results in this area and bring students right up to the research frontier. We also hope to have some guest lectures by leading international experts.

Schedule

This course will be given in period 1 2012, and there will be a total of 16 lectures. The official KTH schedule is not too great and so we will probably change it. We will meet for the first two lectures on Monday August 27 and Tuesday August 28 at 10:15-12:00 and then discuss where to take it from there. Further updates will be posted here.

Prerequisites

The course is open to anyone, but the main target audience are grad students and advanced Master's students. There are no extra formal prerequisites, but you will need mathematical maturity and a willingness to learn new stuff. This will probably be a somewhat demanding course, but hopefully even more fun.

Interested?

For more details, watch this space — it will be updated as the course start date gets closer — or contact the lecturer Jakob Nordström.