|
My UW
|
UW Search
Computer Science Home Page
Theory of Computing
People
Courses
Seminars
Student Lunch &
Reading Group
Qualifying Exam
|
 |
|
|
Theory Reading Group
Spring 2006 Schedule
Friday
April 14, 2006 |
Topic: Nisan's Pseudorandom Generator for Space-bounded computations.
Links:
Pseudorandom generators for space-bounded computations by Nisan.
On recycling the randomness of states in space bounded computation
by Raz and Reingold.
Pseudorandomness for Network Algorithms by Impagliazzo, Nisan, and Wigderson.
Presenter: Siddarth Barman.
2:00pm, 4331 CS.
|
Friday
April 7, 2006 |
Topic: List Decoding of Reed-Solomon codes.
Links:
lecture notes,
more lecture notes,
Decoding of Reed Solomon codes beyond the error-correction bound
by Sudan.
Presenter: Jurgen Van Gael.
2:00 pm, 4331 CS.
|
Friday
March 31, 2006 |
No meeting due to
Welcome Weekend
|
Friday
March 24, 2006 |
Topic: 880 project discussion.
Links: .
Presenter: .
2:00 pm, 4331 CS.
|
Friday
March 10, 2006 |
Topic: Shaltiel/Umans extractor/PRG
Links:
Recent developments in extractors by Shaltiel;
Simple extractors for all min-entropies and a new pseudorandom generator
by Shaltiel and Umans;
Pseudo-random Generators for All hardnesses by
Umans;
Pseudorandom Generators Without the XOR Lemma by Sudhan,
Trevisan, and Vadhan;
Derandomizing BPP - course by Wigderson, written by
Shaltiel.
Presenter: Jeff Kinne.
2:00 pm, 4331 CS.
|
Friday
March 3, 2006 |
Topic: The polynomial method for query lower bounds
Links:
Quantum Lower Bounds
by Polynomials by Beals et al.,
Complexity Measures and Decision Tree Complexity: A Survey
by Buhrman and de Wolf.
Presenters: Bess Berg, Jurgen Van Gael.
2:00 pm, 4331 CS.
|
Friday
February 24, 2006 |
Topic: (Cryptographic) pseudorandom generators
Links:
Chapter 3 of
Lecture Notes on Cryptography by Goldwasser and Bellare,
Lectures 16-23 of
CS225 Pseudorandomness taught by Vadhan,
Lectures 18-23 of
CS880 Advanced Complexity Theory
taught by Melkebeek.
Presenter: Jeff Kinne.
2:00 pm, 4331 CS.
|
Friday
February 17, 2006 |
Topic: Natural proofs
Links:
Natural Proofs by Razborov and Rudich,
Part III Chapter 24 of draft of book by Arora.
Presenter: Jurgen Van Gael.
2:00 pm, 4331 CS.
|
Friday
February 3, 2006 |
Topic: Basing one-way functions on NP-hardness.
Links:
On Basing One-Way Functions on NP-Hardness by Akavia, Goldreich, Goldwasser, and Moshkovitz.
Presenter: Jeff Kinne.
2:00 pm, 4331 CS.
|
Friday
January 27, 2006 |
Topic: Quantum computing - Grover's search algorithm.
Links:
Background on Quantum Computing,
Background on Grover's search algorithm.
Presenter: Jurgen Van Gael.
2:00 pm, 4331 CS.
|
|
|
|
