6.841/18.405  Advanced Complexity Theory

In the last lecture I'm going to highlight several open problems related to topics we discussed during the semester.
The problems were chosen so they are accessible - these are problems that you might be able to solve if you try.
Moreover, each problem will give me an oppurtunity to present an interesting research development, for instance:
using results proven for circuit lower bounds in the design of combinatorial algorithms and algebraization as a barrier for P vs. NP.

Boaz Barak will give a guest lecture tomorrow, Tuesday, 5/12/15.
He'll discuss the new breakthrough establishing an average case hierarchy for AC0.

Hello class,

If you have already graded/scribed before, then you can ignore this email.

For those who have not graded or scribed before, we have the following options for you,
- Grade PSet 6
- Grade PSet 7
- Scribe Lecture on Thursday, April 30
- Scribe Lecture on Tuesday, May 5

We are asking for scribing because the notes for these lectures are not available from previous years (especially because some of the results covered were proved only last year! :D). But to make it easier for you, we have two scriber spots available for each of the two lectures, so you can team up for scribing!

If you are still registered for the course, you should sign up on this spreadsheet. Note that this accounts for 20% of the grading, so you should not be missing out on this!

Thanks,
Pritish & Henry