|
My UW
|
UW Search
Computer Science Home Page
Theory of Computing
People
Courses
Seminars
Student Lunch &
Reading Group
Qualifying Exam
|
 |
|
|
Theory Reading Group
Fall 2005 Schedule
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.
|
|
|
|
