For the second half of the semester, we will cover black box separations, under two topics -- separations, and lower bounds. Below are two groups of papers for the two topics. In the first topic, the papers presented in class will be some subset of the papers (probably not RTV) -- the rest will be for reading. (we already have Mariana as a volunteer for next Thur paper GKMRV). For the second topic, I included a fairly exhaustive list (at least with respect to recent years). I have not yet decided which of these will be presented in class, and in fact we might not even have all of them as an actual recommended reading list. But I am including them all for the students in the class to see, get ready, maybe see if they want to volunteer to present one of these, or want to influence which will be presented in class / read.

A couple of the papers were marked as "counts as 2 papers" -- this means a student can read the paper over two weeks (but should make signficant progress - around half paper -- for the first week already). Papers that were not marked like this, cannot be counted twice, even if they appear on the reading list for two consecutive weeks (e.g., those who read RTV last time, cannot read it again now, and same for future).

People who should still speak in class include: Andrew, Homin, Rajesh, Iasonas (and Mariana but she will be next week). Whatever papers/lectures are not covered by these 4 people, will be covered by me or invited speakers (hoeteck? rosario?).

For next week, the reading list includes the 5 papers in the first list . The "survey" would include the last 4 (without the simon paper). However, I don't want more than two survey people (in general, for any class - so far this has taken care of itself without this as an explicit requirement).

Black Box Separations :

Black-Box Lower Bounds on Efficiency: check with Tal if you want to read a paper with a *