Expanders, Property Testing and the PCP theorem

Theory Seminar Talks

Posted in annoucements, presentations, spr09 by atri on February 6, 2009

We have two confirmed talks in the theory seminar for this semester. The first one is on March 2nd and the next one is on May 4th. For the latter please use the comments section to let me know what times work for you to attend the talk (it is the finals week).

Due to the March 2nd theory seminar, the first four student presentation dates have been moved up. I have updated the dates in the presentation schedule accordingly.

List of PCP-related papers

Posted in annoucements, presentations, spr09 by atri on January 14, 2009

The list of suggested papers for the first set of presentations is now up on the webpage. Some of them have some caveats, so read them carefully. These papers are probably much much harder than any you presented last semester, so we highly encourage you to start early on picking/preparing for your presentations.

Student Presentations

Posted in annoucements, presentations by atri on November 9, 2008

Here is the schedule of the student presentation (all of them start at 10:30am in Bell 224):

  1. Yang (Nov 17): Towards 3-query locally decodable codes of subexponential length (Yekhanin)
  2. Nathan+Swapnoneel (Nov 21+24): Bounds on 2-query codeword testing (Ben-Sasson, Goldreich, Sudan).
  3. Steve (Dec 1)
  4. Than (Dec 5): Approximating the Minimum Spanning Tree Weight in Sublinear Time (Chazelle, Rubinfeld, Trevisan).

Please let us know once you choose your paper and we will update the list above.

Schedule for rest of the semester

Posted in annoucements by atri on October 23, 2008

Below is the planned schedule for the rest of the semester (it is your responsibility to be aware of the meeting times even if we forget to mention them in the previous class):

  • Oct 24 (Fri): 10am-noon. Property Testing: Lecture 1 (Atri)
  • Oct 27 (Mon): No class.
  • Oct 31 (Fri): 11am-noon. Theory seminar (Muthu Venkitsubramaniam)
  • Nov 3 (Mon): 10am-noon. Property Testing: Lecture 2 (Atri)
  • Nov 7 (Fri): 10am-noon. Property Testing: Lecture 3 (Atri)
  • Nov 10 (Mon): 10am-noon. Property Testing: Lecture 4 (Atri)
  • Nov 14 (Fri): No class.
  • Nov 17 (Mon): 10:30am-noon. Student Presentation 1 (Yang)
  • Nov 21 (Fri): 10:30am-noon. Student Presentation 2 (Nathan)
  • Nov 24 (Mon): 10:30am-noon. Student Presentation 3 (Swapnoneel)
  • Nov 27 (Fri): No class.
  • Dec 1 (Mon): 10:30am-noon. Student Presentation 4 (Steve)
  • Dec 5 (Fri): 10:30am-noon. Student Presentation 5 (Than) Last meeting.

Some suggestions for presentations (all of which have to be on property testing) are now online. We very strongly recommend that you start looking at the papers ASAP and make your choice soon. (Almost all of the papers in the list will most probably turn out to be a harder read than most of the stuff you guys presented in the first half of the seminar.)

Change in meeting times

Posted in annoucements by atri on August 29, 2008

We will now meet 10:30am-noon on Mondays and Fridays in Bell 224.


Posted in annoucements by atri on July 28, 2008

This blog will be used to make all course related announcements for the CSE 704 in Fall 08 and Spring 09. In short, this will replace the usual class newsgroup. If you are attending classes, then it is your responsibility to check the blog regularly: you might want to think about subscribing to the RSS feeds. These announcements would include the ones that inform if and when classes/office hours are re-scheduled as well as notifications for the availability of online lecture notes.

Usually, Hung and Atri will be the only ones who will write the blog entries. There will be an entry for each lecture. You are encouraged to use the comments section to post questions and/or comments.

Sometimes, the blog may include side comments or stories that we feel are relevant to the course (but are not directly related to the lectures).

(The idea to use a blog for course announcements has been shamelessly stolen from Ryan O’Donnell)

Tagged with: