Seminar on Average-Case Complexity
 Id: 0368-4152-01


Iftach Haitner

Tuesdays: 10:00-12:00, Room: Schriber 008


The first part of the seminar we will follow the survey by Andrej Bogdanov and Luca Trevisan, and then move to more recent results

In each meeting one student will cover a single topic as listed below.

Prerequisites

This is an advanced seminar, so background in the theory of computation (Algorithm, Computability, Complexity) is required. Students with particularly strong math background are also welcome.

Presentations

Power Point presentations are acceptable, but white boards ones are preferable.
To do a good job one needs to read background material, see the reading section.
In addition, the speakers of the week will have to give me a practice talk a week before (right after the talk of that week).

Topics and schedule

# 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


Additional Reading