Sundays 14:30-16:30 at Taub 4.
Given by Eldar Fischer. Office hours: TBA (Room 625).
2.2.2010: The last writeup I'll put is now in. Thanks for your participation.
22.1.2010: Two more writeups are now online. Enjoy.
9.1.2011: It took a while, but Nadia's updated summaries are now online. Please read them. Note also a long overdue (retroactive) schedule update, for the record's sake.
29.11.2010: And another update for the wrong class date.
28.11.2010: There is an update to Yonatan's Unique Games writeup, and Tomer's writeup is now on line. The schedule is updated too.
7.11.2010: Some overdue updates to the schedule, and links to Yonatan's writeups are included. Watch also the reading assignment section.
14.10.2010: A background paper is now detailed. Please read the relevant parts (see the reading assignment) in preparation to the seminar.
5.9.2010: Two candidate papers to be analyzed are now in.
17.6.2010: Welcome to the course homepage. Given the current date it is still sparse, so take a look at last year's page to see how this works. Please also read below about the questioner to fill if you are interested in this course.
The object of this course is to experience the reading and analysis of a leading edge research manuscript (it can be a conference or a journal publication, and a brand new technical report is also possible). The manuscript (or manuscripts) to be read will be selected by me based on the background of the participants, as long as they are within the topics of combinatorics, complexity theory and/or algorithmic theory.
The students will be required to read all assigned manuscripts, and fully understand their assigned parts to the point of filling in all the gaps (it is likely that a manuscript will be long enough to get partitioned among several students). Each student will have to explain his/her assigned parts to the class, and submit a compendium that contains the relevant clarifications to the manuscript. The grade will be based solely on the oral and written presentations.
Fully understanding the paper may require tasks such as correcting inaccuracies (brand new research reports sometimes have them), filling in "It is easily seen that..." passages that are sometimes not so easily seen, and sometimes going to a cited reference if a method found there is used in a way that cannot be understood without reading the original. It is my intention to put the submitted written presentations on this site, for the benefit of future people trying to understand the selected papers. These should serve as compendium to the paper rather than a replacement (they should help with the hard parts of the paper without reiterating the easy parts).
Every student has to fill out a questioner (get it in the course materials section below) prior to the beginning of the seminar. If you do this early enough, I may select a paper that best matches your prior experience and interests. Late submission means less influence.
I will aim for the following:
I will post here some examples of new and hard enough manuscripts in the future. Last time this seminar was held the following paper was analyzed: Russel Impagliazzo, Valentine Kabanets and Avi Wigderson, New direct-product testers and 2-query PCPs.
The seminar is intended for graduate students and advanced undergraduates. It is best to have some prior reading experience, for example to have attended an undergraduate seminar. Also some advanced theory courses are necessary background.
The questioner form mentioned above doubles as a check of the prospective student's experience. However, I will be willing to admit to the seminar less experienced students if they are determined enough, as my experience is that determination can sometimes be a good replacement to expertise.
Here it is – please send the filled form to my email at the CS faculty.
The first paper to be analyzed will be selected from the following. You input on this can matter to please email me if you have a preference.
Iftach Haitner, A Parallel Repetition theorem for any interactive argument: Repeating a probabilistic algorithm several times and then taking the majority vote is sure to amplify its success probability. But what about interactive prover-verifier protocols whose instances are invoked in parallel? Can malicious "provers" defeat the amplification by coordinating before the start of their respective interactions with the prover? The role of this question in studies of computational complexity cannot be stressed enough, or even adequately explained in this small space. This particular article shows that every protocol can be made into an amplifiable one by "breaking" it a little. If this article is selected, it is expectable that we will also dwell a bit on the history of this question before we begin with the article itself. Note — currently the link on the author's site seems to be broken, but version of this 2009 article exist on e.g. citeseer.
Sanjeev Arora, Boaz Barak and David Steurer, Subexponential algorithms for Unique Games and related problems: The Unique Game Conjecture of Khot, about the hardness of achieving an approximation for a class of problems which captures the essence of many others, has been on the minds of complexity theorists for some time. This article, while not refuting the conjecture, does provide an approximation algorithm for Unique Games that sets it apart from other known NP-hard problems. You can find the paper in Steurer's page.
Something else completely: Feel free to suggest one. I might add it (and others) to the above list.
Boulos Harb, The unique games conjecture and some of its implications on inapproximability. This gives background for both papers above and to related topics such as inapproximability.
A start: Read in the paper by Harb (see the background material section above) Sections 1-3, and think about what needs filling in in this succinct overview.
9.1.2011: Read the new updated writeup by Nadia. It is also time to read the rest of the article. We may not cover all of Sections 7 and 8 (in fact we will probably cover a little of 7 and none of 8), but still it is best if you get up to speed on them and ask questions during the seminar.
7.11.2010: If you have not done so already, read Yonatan's summaries and present all questions you have in his next talk. Also start reading the Unique Games article itself, the introduction (Section 1) for now, and be ready with questions.
28.11.2010: Use the time you now have to read all the summaries if you haven't already done so. In the article it is a good idea to finish reading up to and including Section 3. Have your questions ready.
The first topic would center around subexponential algorithms for unique games, so naturally we begin with a brief introduction to the motivation and applications of label covering and unique games.
| Date | Person | Topic | Comments |
| 17.10, 24.10 | me | Introduction and topic primer | |
| 31.10 | Yonatan | Label cover and hardness of approximation | |
| 7.11 | Yonatan | Unique games and hardness of approximation | |
| 14.11 | Yonatan | Addenda | first hour |
| Tomer | Introduction to the UG article | ||
| 21.11 | Tomer | Finding small non-expanding sets | No class on 28.11 |
| 12.12 | Tomer | Finding sets concluded | short |
| Nadia | Threshold rank and non-expanding sets | ||
| 19.12 | Nadia | Threshold rank continued | |
| 26.12 | Nadia | Threshold rand continued more | |
| Yonatan | Brief introduction to graph decomposition | 15 minutes | |
| 2.1 | Yonatan | Graph decomposition | |
| 9.1 | Tomer | Unique Games algorithm | |
| 16.1 | Tomer | Unique Games algorithm concluded | short |
| Nadia | Plugging a final hole | 10 minutes | |
| A multicut application | |||
| 23.1 | various | What came next |