Topics in Pseudorandomness (Reading Group)
General information
Organizers : Mrinal Kumar, Nutan Limaye, Srikanth Srinivasan
Email : first name AT cse DOT iitb DOT ac DOT in
Time : Tuesday, 11:45 am - 1:45 pm
Location : New CSE Building, Room 109
Description
The general idea of the reading group is to discuss some of the standard and some non-standard topics in pseudorandomness, (hopefully) including but not limited to pseudorandom generators, hitting set generators, hardness randomness tradeoffs, list decodable codes and randomness extractors.
Meetings
- Meeting 1 (Aug 20) : Pseudorandom generators : Nisan-Wigderson generator framework.
- Meeting 2 (Aug 27) : Nisan-Wigderson PRG continued, PRG for AC0. Hitting set generators: Kabanets-Impagliazzo generator definition.
- Meeting 3 (Sep 3) : Kabanets-Impagliazzo generator cont: analysis. Kaltofen's result on closure of arithmetic circuits under factorization.
What more can we ask for from the KI generator ?
- Meeting 4 (Sep 10) : Hitting set generators with constant seed length from arithmetic circuit lower bounds.
- Meeting 5 (Sep 17) : No meeting - Midterm week
- Meeting 6 (Sep 24) (Srikanth Srinivasan) : Pseudorandom objects and unconditional derandomization, k-wise independence, randomness extractors
- Meeting 7 (Oct 1) (Srikanth Srinivasan) : Trevisan's Extractors
- Meeting 8 (Oct 8) : No meeting - Dussehra holiday
- Meeting 9 (Oct 15) : No meeting - too many theory talks this week!
- Meeting 10 (Oct 22) (Rohit Gurjar) : Gabizon-Raz extractors for affine sources over large fields
- Meeting 11 (Nov 5) : Algorithms for decoding and list decoding Reed-Solomon codes
References