| 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.
|
