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

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


Hung Ngo
(716) 645-3180 x 160
238 Bell Hall


Atri Rudra
(716) 645-3180 x 117
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.

Class Schedule

Here is a tentative schedule for the seminar:
  1. Introduction to the PCP theorem and connection to hardness of approximation.(3 lectures by Hung and Atri).
  2. Expanders (12 lectures by Hung).
  3. Student presentations on expanders (9 lectures).
  4. Property Testing (10 lectures by Atri).
  5. Student presentations on property testing (9 lectures).


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


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.