Note: This webpage is still under consideration. More details will be added soon!

CSE 704: Expanders, Property Testing and the PCP Theorem - I

Instructor

Hung Ngo

Email:
Phone:	(716) 645-3180 x 160
Office:	238 Bell Hall

Instructor

Atri Rudra

Email:
Phone:	(716) 645-3180 x 117
Office:	123 Bell Hall

Class Meetings

Monday, Friday. 10:30am-noon

224 Bell Hall^*

Course Announcement

Course Blog

We will be using a blog for the course in lieu of a course newsgroup. All announcements will be made on the blog. If you are attending the course, you must check the blog regularly (and consider subscribing to the RSS feed).

Reference material

Not surprisingly, we will not follow any particular textbook. We will mostly follow papers. Here are some resources relevant to the seminar.

Lecture notes on the proof of the PCP theorem from a course by Venkatesan Guruswami and Ryan O'Donnell. The course was offered in Fall 2005 at the University of Washington.
A survey on expanders by Shlomo Hoory, Nati Linial and Avi Wigderson. This is perhaps the survey on expanders. The survey won the AMS Levi L. Conant Prize in 2008.
Two surveys on property testing: one by Eldar Fischer and another by Dana Ron. (Some more here.)

Class Schedule

Here is a tentative schedule for the seminar:

Introduction to the PCP theorem and connection to hardness of approximation.(3 lectures by Hung and Atri).
Expanders (12 lectures by Hung).
Student presentations on expanders (9 lectures).
Property Testing (10 lectures by Atri).
Student presentations on property testing (9 lectures).

Workload

The workload will be pretty light. Other than attending the lectures, students will have to do the following:

Present a paper (or two) related to the seminar. Here is a list to get started. Note that this list is just meant to be a starting point: by all means feel free to choose a paper related to what we cover in the lectures that is not there is the list (but do get approval from Hung or Atri). Students will pair up to present a paper. You are expected to choose your partner within the first week of lectures.
The students are expected to think about research problems related to the seminar. You are expected to submit a 1-2 page report at the end of the semester.

Grades

A grade of satisfactory/unsatisfactory will be assigned at the end of the course. If you want a letter grade, talk to the instructors about more details.

Academic Honesty

We have zero tolerance for cheating and will follow the CSE Department Policies on Academic Integrity.

^*The class on October 6, 2008 will be in 242 Bell.