Sundays 13:30-15:30, Room 201.
Given by Eldar Fischer. Office hours: Wednesday at 13:30 (Room 625).
15.7.2009: Grades are out - those of you that are not registered the usual way please check with the secretaries. Also, an update to the first installment of Karin's notes, and two more added (there will be a total of four).
5.7.2009: Update to Karin's slides and half of her lecture notes.
24.6.2009: Karin's slides of Section 4.1 are now online.
18.6.2009: Oded's final proof of Lemma 2.2 is now online. Schedule is also updated, apparently it is more of a "what we had" rather than "what is coming" schedule.
13.5.2009: Oded's notes have been updated.
27.4.2009: Oded's lecture notes are now available online (with more to follow).
23.2.2009: Reading material and lecturers have been updated. From now on this will be done every week without notification here.
18.3.2009: There is a permanant time and place change (by popular request). The seminar will be held on Sundays from 13:30 to 15:30, in Room 201.
15.3.2009: Reading assignments are now in. Make sure you make progress. There is also the beginning a list of expositions.
12.3.2009: Added resources, including what will likely be the first paper that we go over.
5.3.2009: I just sent an email to those of you that sent in your forms. It give my currently preferred paper choices, which are Wigderson et al's work about direct product testers, and Dinur's well known combinatorial PCP construction. If you did not receive an email, send your form :-)
14.1.2009: Welcome to the course homepage. Please 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 conference or a journal publication, but a brand new technical report is also possible). The publication (or publications) 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 and understand their assigned manuscript. 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 his class fellows, 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 which are not so easily seen, and sometimes going to a cited reference where a method there is used in a way that cannot be understood without reading the original. It is my hope to put the submitted written presentations on this site, for the benefit to 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 will have 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 will select a paper that best matches your prior experience and interests. Submit too late and you will lose your influence.
I will aim for the following:
As an example, here are some topics that I may consider to be new and difficult enough. Note that the actual selection may or may not intersect the following list.
The seminar is intended for graduate students and advanced undergraduates. It is best to have some prior reading experience, e.g. to have attended an undergraduate seminar. Also some advanced theory courses are necessary background.
The questioner form mentioned above also 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 I found out that determination can sometimes be a good replacement to experience.
Here it is — (no longer relevant for this semester).
Russel Impagliazzo, Valentine Kabanets and Avi Wigderson, New direct-product testers and 2-query PCPs: This paper was the topic of Avi Wigderson's talk at our faculty in March. It is a new construction of "Property Testers" for one of the most straight-forward codes thinkable, the code that just provides f(x1)...f(xk) for every k-tuple x1...xk. Here property testing is not exactly what some of you may remember from the seminar, but something adapted for Probabilistically Checkable Proofs. Namely, it must be that a rather small acceptance probability still indicates some maximal distance from a code-word, and the correlation between the two is very important.
Here is Avi Wigderson's homepage and here is a direct link to the paper.
Property Testing: Although the paper is about property testing as some of you may know it, it is still a good idea to take a look at my survey of the topic.
Probabilistically Checkable Proofs: You certainly need to know about those. A relatively gentle introduction is the one by Hougardy, Prömel and Steger. You can find it on an old homepage of Prömel. It is somewhat outdated (especially that more recent proofs no longer use algebra of polynomials) but try it.
Locally Decodable Codes: I hope to post a survey on it in the course. These are the main engine of Probabilistically Checkable Proofs, and the main connection with Property Testing.
Week 1: For background on PCP, read at least up to Sections 2 in the old survey by Hougardy et al. For further background on traditional Property Testing, read from my survey until you are satisfied. From our main discussion paper (by Impagliazzo et al), read the abstract and the introduction at least up to 1.3.
Week 2: During this week you should finish with Section 3 of the PCP survey and the whole introduction of our discussion paper. Also, read the combinatorial proof of linearity being testable. Go to Eli Ben-Sasson's 2005 course page and read from lecture 2 - the proof itself (with somewhat different notation) is in 2.2 (thanks to Anath for this pointer). Have your questions ready, it is not the job of the explainer to reread the proofs to you, just to explain their harder points.
Week 3: During this week you should read Section 2 of the main paper. Note that this "week" is actually three weeks long, so finish up all previous reading assignments. To help with this reading and the rest of the course, you should know some basic probabilistic methods. You can do so by heading to my Probabilistic Methods course homepage; read from the lecture notes up to the middle of Page 11 (you can skip the chapters about corrections and about the isolating lemma), and read and understand the solutions to Assignment Zero.
Week of 26.4: In the previous weeks (including the vacation time) you were supposed to finish up all pending reading assignments. For this week it is recommended to read Oded's lecture notes, and look for updates (a writeup of the proof of Lemma 2.2 is upcoming).
From 10.5: Read the updated Oded's lecture notes. Also, as we are starting on Section 3, it is a very good idea to read it (there is Matkonet on 17.5 so you have some time).
From 14.6: Start Chapter 4 if you haven't already. Also read Oded's writeup of Lemma 2.2.
Finally: Read Karin's lecture notes, see if you can understand the parts we did not get to in class. It is also a good time to reread the motivational parts in the article.
| Date | Person | Topic | Comments |
| 15.3 | me | Introduction and Property Testing primer | |
| 22.3 | Anath | PCP primer | Course hour permanently changed |
| 29.3 | Anath | More PCP | |
| Daniel | Linearity test, start on the paper's introduction | ||
| 19.3 | Daniel | The introduction | |
| 26.4 | Oded | Preliminaries, Part I | |
| 3.5 | Oded | Preliminaries, Part II | |
| 10.5 | Karin | Lemma 2.2 progress report (with Daniel, Oded) | |
| Tomer | Proof of the main test Part I | ||
| 24.5 | Tomer | Proof Part II | |
| 31.5 | Tomer | Proof Part III | Beginning the harder Section 3.2 |
| 7.6 | Tomer | Part IV | |
| Oded | Lemma 2.2 - the end | Joint work with Daniel and Karin | |
| 14.6 | Tomer | Part V - the main proof concluded | |
| Karin | Proof of the "derandomized" test Part I | ||
| 21.6 | Karin | Derandomized part II | |
| 28.6 | Karin | Derandomized part III | |
| 28.6 | Karin | Derandomized part IV the unfinished | |
| Conclusion |