Theory Reading Group

Fall 2007 Schedule

Date Information
Wednesday, December 12 2007 Topic: Natural Proofs
Links: Natural Proofs by Alexander Razborov and Steven Rudich
Presenter: Scott Diehl
4:00pm, 4310 CS.
Wednesday, November 14 2007 Topic: Unambiguous Log-Space
Links:
Making Nondeterminism Unambiguous by Eric Allender, Klaus Reinhardt, and Shiyu Zhou,
Directed planar reachability is in unambiguous log-space by Chris Bourke, Raghunath Tewari, and N. V. Vinodchandran
Presenter: Jeff Kinne
4:00pm, 4310 CS.
Wednesday, November 7 2007 Topic: Ideal Membership and Polynomial Identity Testing
Links: The Ideal Membership Problem and Polynomial Identity Testing by Vikraman Arvind and Partha Mukhopadhyay
Presenter: Matt Anderson
4:00pm, 4310 CS.
Wednesday, October 24 2007 Topic: Instance Compression of NP languages
Links: Infeasibility of Instance Compression and Succinct PCPs for NP by Lance Fortnow and Rahul Santhanam
Presenter: Jeff Kinne
4:00pm, 4310 CS.
Wednesday, October 10 2007 Topic:Time-Space lower bounds
Links:Time-Space Tradeoffs for Counting NP Solutions Modulo Integers
Presenter:Scott Diehl
4:00pm, 4310 CS.