Complexity Theory Reading Group

Time: Wednesday 4pm
Location: Soda 751
Will start by reading results on Pseudorandom Extractors of Multiple independent sources:

Week 1 (January 31):

Grant presents
"Extractors for a Constant Number of Polynomially Small Min-Entropy Independent Sources"
Anup Rao
http://www.cs.utexas.edu/~arao/pubs/abstracts.html#indep

Week 2 (February 7):

Madhur presents
"Extracting Randomness Using Few Independent Sources"
Boaz Barak, Russell Impagliazzo and Avi Wigderson
www.cs.princeton.edu/~boaz/Papers/msamples.ps

Week 3 (January 14):

Grant presents
"Tight integrality gaps for Vertex Cover SDPs in the Lovasz-Schrijver hierarchy "
Konstantinos Georgiou, Avner Magen, Toniann Pitassi, Iannis Tourlakis
http://eccc.hpi-web.de/eccc-reports/2006/TR06-152/index.html