Theory Reading Group

Spring 2006 Schedule

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