0368.4155 On
the P vs. BPP problem
CS dept, TelAviv University, Fall
2017

Syllabus
(tentative)
Lecture Sunday, 14:0017:00, Shenkar (physics) 105 Instructor Amnon TaShma  Schreiber
127  5364 Open
for Undergrad
and grad students. Grading
policy 50% final takehome
assignment, the rest is exercises and based on participation in class. 

Textbooks
and links 
·
AroraBarak,
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 
Date 
Class Topic 
Lecture notes 
References 
Oct 30 
Class
overview. ECC. RS. Berlekamp’s decoding algorithm. 
[GRS]
Chapter 13. 

Nov 6 
RM
local decoding. RS list decoding. 
[GRS]
Chapter 13. The [AB] book. 

Nov 13 
RM
local list decoding. Worstcase to averagecase
reduction. 
The [STV]
paper. 

Nov 20 
Hadamard local list decoding. The NisanWigderson PRG. Conditional derandomization
of BPP. 


Nov 27 
Overview
of complexity classes. Nonuniform computation. Interactive proofs.
KarpLipton type theorems. Warmup claims for the IKW theorem. 


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

Dec 11 
If
NEXP is in P/poly then CSAT is extremely hard. 


Dec 18 
Natural
proofs 


Dec 30 
Promise
classes. Probabilistic diagonalizations. 


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. 


Jan 22 (Dean Doron) 
Toda's theorem – II. Deterministic
amplification via seeded extractors. 
