0368.4155      On the P vs. BPP problem

CS dept, Tel-Aviv University, Fall 2017

 

We meet at Shenkar 105.

 

Syllabus (tentative)

 

The Questions Pool for the assignments is here. You will find instructions within.

 

The Take-home exam is here, and the required statement is here. You will find instructions within.

There is also the mini-project we discussed in class.

 

 

 

Lecture              Sunday, 14:00-17:00, Shenkar (physics) 105

Instructor         Amnon Ta-Shma | Schreiber 127 | 5364

Open for           Undergrad and grad students.

Grading policy  50% final take-home assignment, the rest is exercises and based on participation in class.

 

Textbooks and links

 

·         Arora-Barak, Computational complexity – a modern approach. An online version.

·         Guruswami, Rudra, Sudan. Essential Coding Theory. An online version.

·         S. Vadhan: Psuedorandomness

·         M. Luby, A. Wigderson: Pairwise Independence and Derandomization

·         A. Wigderson: Derandomizing BPP - A survey (lecture notes) (Scribe: Irit Dinur, 2002).

·         A. Wigderson: Derandomizing BPP - Lecture notes of a Hebrew University course) (Scribe: Ronen Shaltiel, 1998).

·         A. Shpilka, A. Yehudayoff: Arithmetic Circuits: a survey of recent results and open questions.

·         R. Motwani, P. Raghavan: Randomized Algorithms

·         L. Lovasz: Random walks on graphs: A Survey

·         The complexity zoo

 

 

 

Date

Class Topic

Lecture notes

References

Oct 30

Class overview. ECC. RS. Berlekamp’s decoding algorithm.

Lecture 1

[GRS] Chapter 13.

Nov 6

RM local decoding. RS list decoding.

Lecture 2

[GRS] Chapter 13. The [AB] book.

Nov 13

RM local list decoding. Worst-case to average-case reduction.

Lecture 3a, Lecture 3b

The [STV] paper.

Nov 20

Hadamard local list decoding. The Nisan-Wigderson PRG. Conditional derandomization of BPP.

Lecture 4

 

Nov 27

Overview of complexity classes. Non-uniform computation. Interactive proofs. Karp-Lipton type theorems. Warm-up claims for the IKW theorem.

Lecture 5a, Lecture 5b

 

Dec 4

The IKW theorem. The IK theorem – derandomizing PIT implies lower bounds (either Boolean or arithmetic).

Lecture 6, Lecture 7

The [IKW] paper. The [IK] paper.

Dec 11

If NEXP is in P/poly then CSAT is extremely hard.
An algebraic NW generator.

Lecture 8, Lecture 9

 

Dec 18

Natural proofs

Lecture 10

 

Dec 30

Promise classes. Probabilistic diagonalizations.


Lecture 11, Lecture 12

 

Jan 1

Derandomization under uniform assumptions (IW).

 

Jan 8

The IW theorem revisited. Easily finding hard instances for SAT solvers. The Isolation Lemma.

 

Jan 12

(Dean Doron)

Toda's theorem - I.

Lecture 14a

 

Jan 22

(Dean Doron)

Toda's theorem – II. Deterministic amplification via seeded extractors.

Lecture 14b