Schedule:
May 11, Aedan Maher, PP is closed under truth-table reductions by Fortnow and Reingold
May 14, Georgios Askalidis: Graph Isomorphism is in SPP by V. Arvind, Piyush P. Kurur
May 16, Darrell Hoy: Search via Quantum Walk, by Frédéric Magniez, Ashwin Nayak, Jérémie
Roland, Miklos Santha. Additional lecture notes
May 18, Geoff Hill: Relationships among PL, #L, and the determinant by Eric Allender
May 21: No class due to STOC conference
May 23, Greg Stoddard: Strengths and Weaknesses of Quantum Computing by Charles H. Bennett, Ethan Bernstein, Gilles Brassard, Umesh Vazirani
May 25, Prem Seetharaman: Complexity of combinatorial market makers by Yiling Chen, Lance Fortnow, Nicolas Lambert, David Pennock and Jenn Wortman.
No comments:
Post a Comment