# | When | Who | What |
1 | 10/3 | Etan Grundstein | Introduction Section 1 |
17/3 | NO CLASS | ||
2 | 24/3 | Adi Sela | Definitions Section 2 |
3 | 14/4 | Avishay Yifrach | A Complete Problem for Computable Ensembles: part Ⅰ Section 3 |
4 | 21/4 | Paz Dangur | A Complete Problem for Computable Ensembles: part Ⅱ Section 3 |
5 | 28/4 | Jonathan Zcharya | All Natural NPC Problems Have Average-Case Complete Versions
Paper by Noam Livne |
6 | 5/5 | Or danon and Eliraz Levi | Decision Versus Search and One-Way Functions Section 4 |
7 | 12/5 | Tal Kligman | Samplable Ensembles Section 5 |
8 | 19/5 | Kineret Segal | Hardness Amplification Section 6 |
9 | 26/5 | Guy Braude | Hardness amplification within NP Paper by Ryan O'Donnell |
10 | 2/6 | Uri Sharir | Worst-Case Versus Average-Case and Cryptography (without proof of Thm. 7.5) Section 7 |
11 | 9/6 | Tzion Sasson | On Worst-Case to Average-Case Reductions for NP Problems Paper by Andrej Bogdanov and Luca Trevisan |
12 | 16/6 | Gal Rotem | On the Power of Randomized Reductions and the Checkability of
SAT
Paper by Mohammad Mahmoody and David Xia |
13 | 21/6 Sunday | Coral Grichner | If NP Languages Are Hare On The
Worst-Case, Then It Is Easy to Find Their Hard Instances Paper by Dan Gutfreund, Ronen Shaltiel, and Amnon Ta-Shma |