Theory Reading Group

Fall 2005 Schedule

Date Information
Monday
December 12, 2005		 Topic: Quantum computing.
Links: TBD.
Presenter: Bess Berg.
3:30 pm, 4331 CS.
Monday
December 5, 2005		 Topic: Pseudorandom Generators.
Links: Derandomizing BPP and Pseudorandomness - A Survey by Wigderson and Dinur,
Derandomization: A Brief Overview by Kabanets.
Presenter: Jeff Kinne.
3:30 pm, 4331 CS.
Monday
November 21, 2005		 Topic: Division/Iterated multiplication with small depth circuits.
Links: Division in logspace-uniform NC1 by Andrew Chiu et al.
Presenter: Eric Skaug.
3:30 pm, 4331 CS.
Monday
November 14, 2005		 Topic: Time-space lower bounds for SAT.
Links: Time-Space Lower Bounds for Satisfiability by Fortnow et al.,
Better Time-Space Lower bounds for SAT and Related problems by Williams,
Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines by Diehl, van Melkebeek.
Presenter: Scott Diehl.
3:30 pm, 4331 CS.
Monday
November 7, 2005		 Topic: BPtime hierarchy results and discussion.
Presenter: Jeff Kinne.
3:30 pm, 4331 CS.
Monday
October 31, 2005		 Topic: Sum-product estimate for subsets of a finite field.
Links:A Sum-Product Estimate in Finite Fields, and Applications by Bourgain et al.
A sum-product estimate in fields of prime order by Konyagin.
Presenter: Anand Sinha.
3:30 pm, 4331 CS.
Monday
October 24, 2005		 Student Summer RA talks - no meeting.
Vinay and Anand will be giving their "Summer RA" talks at 4pm in 1221 CS.
Monday
October 17, 2005		 Topic: Is P vs NP Formally Independent?
Links: Is P Versus NP Formally Independent by Scott Aaronson.
Jurgen Van Gael will present.
3:30pm, 4331 CS.
Monday
October 10, 2005		 Topic: Time Hierarchy for BPP with advice.
Links: A Generic Time Hierarchy for Semantic Models with One Bit of Advice by Melkebeek and Pervyshev.
Jeff Kinne will present.
3:30pm, 4331 CS.
Monday
October 3, 2005		 Topic: Approximating Unique Games.
Links: Approximation ALgorithms for Unique Games by Luca Trevisan.
Anand Sinha will present.
3:30pm, 4331 CS.
Monday
September 26, 2005		 Topic: discuss Qual problems.
3:30pm, 4331 CS.
Monday
September 19, 2005		 Topic: Hierarchy Theorems.
Links: Jin-Yi Cai's complexity notes, Lecture on Nondeterministic Time Hierarchy, Time Hierarchy for Semantic Models (e.g. BPP) with 1 bit of advice
3:30pm, 4331 CS.
Monday
September 12, 2005		 Topic: Review of Complexity classes.
Links: Jin-Yi Cai's complexity notes, The Complexity Zoo A Complexity Map.
3:30pm, 4310 CS.