DD2441 Seminars on Theoretical Computer Science Autumn 2012: Communication Complexity
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.:
The course will cover some exciting results in this area and bring students right up to the research frontier. We will also have guest lectures by a couple of leading international experts, namely Joshua Brody from Aarhus University and Troy Lee from the Centre for Quantum Technologies in Singapore.
The course was given in period 1 in the autumn of 2012. We had a total of 16 lectures, with 2-3 lectures per week.
In accordance with the academic quarter tradition at KTH, 10 am in the schedule below actually means 10:15 am.
We also had an optional extra minilecture on Wednesday September 19 at 16:15 to 17-ish in seminar room 4523, when Joshua Brody presented an analysis of the graph bipartiteness test.
The main lecturer on the course was Jakob Nordström, who was responsible for all aspects of the course.
Massimo Lauria was co-lecturer on the course and also helped out with practical aspects such as constructing and grading problem sets.
We used Piazza for teacher-student interaction on the course. Thus, questions were not e-mailed to Jakob or Massimo, but instead posted on Piazza (where it was possible to send private notes to the instructors if needed).
The course is open to anyone, but the main target audience are advanced Master's students and PhD students. As stated on the Study Handbook webpage you need to have taken DD1352 Algorithms, Data Structures, and Complexity or DD2354 Algorithms and Complexity or corresponding courses at other universities (and should feel comfortable with that material). You will also need to know some probability theory and basic linear and abstract algebra. There are no additional formal prerequisites on top of what is stated in the Study Handbook, but you will need mathematical maturity and a willingness to learn new stuff.
The lectures are given in English.
Although the formal prerequisites are very limited, it should be noted that this is a somewhat demanding course (but hopefully even more fun!).
This course is intended to
To pass the course, students will be required to solve four problem sets. If you are a PhD student, you can take this course as a research-level doctoral course with course code DD3441 instead. The requirements are slightly tougher and the grading is only pass/fail, but the course counts fully towards the course credit requirements in the PhD program.
The grades for Master's students taking DD2441 are determined as follows:
Commenting explicitly on one possible corner case: If one pset is slightly below pass but very close, and other psets are clearly above pass, then the student will pass.
Given that this is a course that is intended to bring us right up to the research frontier, one option could be to substitute a small reading and/or research project instead of one or a few problem sets. If so, the details will be determined on a case-by-case basis by mutual agreement between the student and the main lecturer. [UPDATE: None of the students wanted to exercise this option.]
Please note the code of honour that applies to all courses at KTH CSC.
The course has no official textbook. Below follows some information about books and articles that might be useful for participants on the course.
Note that if you are not at KTH, or if you are connected to the KTH network via wireless, then you might not be able to download the PDF files on some of the webpages linked to below. If so, just googling for the title should hopefully help you find free preliminary versions of the same papers on the webpages of the authors or similar.
Another solution to this problem (courtesy of
is to invoke the KTH library proxy server directly in the address field of
the browser. You do this by adding
Some of the material that we cover can be found in the book
While certainly not required, the book
Chapter 8 of A Computational Introduction to Number Theory and Algebra by Victor Shoup provides a good survey of basic probability theory for computer scientists, some of which we will need to use in this course (but certainly not all of it!).
Two survey articles on communication complexity that might be useful are:
Below follows a list (being updated throughout the course) of the research articles on which the lectures are based. Note that some of this material is also covered in the surveys above (possibly even in more readable form) but the links below are to the original papers. Whenever available, the link is to the journal version (or full-length technical report), which means that the date of the paper can be a few years later than that of the original conference publication.
Solutions to the
problems sets should be submitted as PDF-files by e-mail to
lauria at kth dot se.
Please use the subject line
When you are working on the problem sets, discussions of ideas in groups of two to three people are allowed, but you should always write down your own solution individually and understand all aspects of it fully. You should also acknowledge in your solutions with whom you have been collaborating.
You can (and should) also ask the instructors if anything about the problem sets is unclear. Make sure to post private messages to the instructors on Piazza in that case, so that your questions do not accidentally give away unintended information about the problems to the other students. If there is some issue needing clarification regarding some problem, the instructors will make public posts on Piazza.
Some of the problems are "classic" and hence their solutions can probably be found on the Internet, in textbooks, or in research papers. It is not allowed to use such solutions in any way unless explicitly stated otherwise. Anything said during the lectures on in the lecture notes should be fair game, though, unless you are specifically asked to show something that we claimed without proof in class.
List of Problem Sets
Links to some other recent courses in communication complexity (some of which have heavily influenced this course):