Time: Wed 1:00-2:30pm
Location: TTI-C Conference Room
Organizer :
Homepage:
http://ttic.uchicago.edu/~prahladh/teaching/fall05/
Starting this Wednesday (September 28, 2005), we will be resuming the quarterly THEORY READING GROUP. The reading group will be held every Wednesday from 1-2:30pm in the TTI Conference Room. The typical length of each meeting will be about 1 hour. The extra half an hour is a buffer to allow for any discussion that might follow the presentation.
The topic for this quarter's reading group will be PCPs and INAPPROXIMABILTY (with special emphasis on the UNIQUE GAMES CONJECTURE). Starting from some of the initial results in the area (such as the optimal inapproximability results for 3SAT), we intend to cover some of the more recent results on hardness of MAXCUT, min-bisection, sparsest cut etc. In our first meeting, I will outline some of the essential ingrediants in these results - PCP Theorem, Parallel Repetition Theorem, etc. Following this, we will discuss some of the papers we plan to cover in the course of the reading group. Theory Students from both TTI-C and UChicago are encouraged to participate in these reading groups and volunteer to present a paper each.
The reading group immediately follows Lance's Complexity course giving just enough time to walk to TTI. So, feel free to get your lunch to the meetings.
| Prahladh Harsha |
|