DD2441 Seminars on Theoretical Computer Science Autumn 2012: Communication Complexity

Follow these shortcut links to go directly to news, short overview of course, schedule, lecturers, prerequisites, course goals, course requirements, course material, problem sets, or links.

News

The course is over.
The course analysis contains a description of the course together with an analysis of what aspects should be kept the same or be modified the next time the TCS seminar course is given.

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 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.

Schedule

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.

Weekday	Date	Time	Room	#	Plan of lectures	References
Monday	Aug 27	10-12	1537	1.	Introduction to communication complexity; course overview; practicalities	[KN97] Chap 1, notes
Tuesday	Aug 28	10-12	1537	2.	Lower bounds on deterministic communication complexity	[KN97] Chap 1, notes
Monday	Sep 3	10-12	1537	3.	Randomized communication complexity	[KN97] Chap 3, notes
Wednesday	Sep 5	9-11	1537	4.	Streaming algorithms: upper bounds	[AMS99], notes
Monday	Sep 10	10-12	1537	5.	Streaming algorithms: lower bounds	[AMS99], notes
Wednesday	Sep 12	10-12	1537	6.	Guest lecture by Joshua Brody: Property testing	[BBM12], notes
Thursday	Sep 13	10-12	1537	7.	Guest lecture by Joshua Brody: Property testing (cont.)	[BBM12], notes
Monday	Sep 17	10-12	4523	8.	Guest lecture by Joshua Brody: Some open problems in communication complexity	[BBCR10], [BLR12], [Pat10], [Raz00], notes
Wednesday	Sep 19	10-12	4523	9.	Crash course in information theory	[CT06] Chap 2, notes
Thursday	Sep 20	10-12	4523	10.	Randomized communication complexity lower bounds for set disjointness	[BJKS04], notes
Monday	Oct 1	10-12	1537	11.	Randomized communication complexity lower bounds for set disjointness (cont.)	[BJKS04], notes
Wednesday	Oct 3	10-12	1537	12.	Guest lecture by Troy Lee: Generalized discrepancy and composed functions	Notes
Thursday	Oct 4	10-12	1537	13.	Guest lecture by Troy Lee: Multiparty NOF communication complexity	Notes
Monday	Oct 8	10-12	1537	14.	Massimo Lauria: Proof complexity and time-space trade-offs	[HN12], slides
Wednesday	Oct 10	10-12	1537	15.	Massimo Lauria: Proof complexity and time-space trade-offs (cont.)	[HN12], notes
Wednesday	Oct 17	10-12	1537	16.	Boolean circuit depth; wrap-up	[KN97] Chap 10, notes

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.

Lecturers

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).

Joshua Brody from Aarhus University and Troy Lee from the Centre for Quantum Technologies in Singapore gave guest lectures on the course.

Prerequisites

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!).

Course Goals

This course is intended to

give an introduction to communication complexity,
survey some of the most recent exciting results in this area,
give examples of applications of communication complexity in other areas of theoretical computer science, and
present a number of open problems right at the frontier of current research,

so that that students after having completed the course

will have a good grasp of the fundamentals of communication complexity,
will be able to reconstruct the proofs, at least in principle, of some of the major results during the last 10-15 years, and
will be well equipped to attack open problems in the area (or will potentially already successfully have done so).

Course Requirements

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:

To pass the course, you need a pass (E) on all psets.
In principle, the final grade will be the arithmetic mean of the grades for the 4 psets (think of A-E as {5,4,3,2,1}, sum up, and divide by 4).
If this mean is not integral, later psets will affect the rounding more than earlier psets.
It is very possible that there will be some corner cases that this set of rules, or any set of rules of reasonable length, cannot exactly capture. In such cases, we will strive to be generous rather than stingy.

For PhD students taking DD3441, the principle is that C is needed on all psets to pass. PhD students also have the option to take the Master's level course.

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.

Course Material

Note that the information below about course material is being updated as we go along.

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 Lars Arvestad) is to invoke the KTH library proxy server directly in the address field of the browser. You do this by adding .focus.lib.kth.se to the domain of the web address where you found the paper in question, which will work if the KTH library has a subscription. For instance, if you want to look at http://www.journal.com/somepaper.html but this paper is behind a pay-wall, you try to change the URL to http://www.journal.com.focus.lib.kth.se/somepaper.html. Supposing that the KTH library is paying for the journal in question, this should take you to the paper via a login page for your KTH account.

Books and Surveys

Some of the material that we cover can be found in the book

[KN97] Eyal Kushilevitz and Noam Nisan: Communication Complexity.

While this is by all accounts a truly excellent book, it is beginning to get fairly out-of-date. Therefore, there is not enough overlap with the lectures to make it an officially recommended textbook for the course.

While certainly not required, the book

[CT06] Thomas M. Cover and Joy A. Thomas: Elements of Information Theory

is a useful reference for the tools and techniques from information theory that we use.

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:

[CP10] Arkadev Chattopadhyay and Toniann Pitassi: The Story of Set Disjointness.
[LS07] Troy Lee and Adi Shraibman: Lower Bounds in Communication Complexity.

Research Articles

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.

[AMS99] Noga Alon, Yossi Matias, and Mario Szegedy: The Space Complexity of Approximating the Frequency Moments.
[BBCR10] Boaz Barak, Mark Braverman, Xi Chen, Anup Rao: How to Compress Interactive Communication.
[BBM12] Eric Blais, Joshua Brody, and Kevin Matulef: Property Testing Lower Bounds via Communication Complexity.
[BJKS04] Ziv Bar-Yossef, T.S. Jayram, Ravi Kumar, and D. Sivakumar: An Information Statistics Approach to Data Stream and Communication Complexity.
[BLR12] Eli Ben-Sasson, Shachar Lovett, and Noga Ron-Zewi: An Additive Combinatorics Approach Relating Rank to Communication Complexity.
[HN12] Trinh Huynh and Jakob Nordström: On the Virtue of Succinct Proofs: Amplifying Communication Complexity Hardness to Time-Space Trade-offs in Proof Complexity.
[Pat10] Mihai Pătraşcu: Towards Polynomial Lower Bounds for Dynamic Problems.
[Raz00] Ran Raz: The BNS-Chung Criterion for Multiparty Communication Complexity.

Problem Sets

General Information

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 Problem set <N>: <your name> and name the PDF file PS<N>_<YourName>.pdf with any national characters converted to standard ASCII (so the solutions to the second problem set by the main lecturer would have the file name PS2_JakobNordstrom.pdf, for instance). Solutions should be typeset in some math-aware system (read: LaTeX or such like; MS Word with Equation Editor is borderline but might pass).

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

Problem set 1 (last revised September 6, 2012): Deadline Friday September 14, 2012.
Problem set 2 (last revised September 30, 2012): Deadline Sunday September 30, 2012.
Problem set 3 (last revised October 27, 2012, to fix some typos): Deadline Sunday October 21, 2012.
Problem set 4 (last revised November 2, 2012): Deadline Sunday November 25, 2012.