#  Date   lecture topic  reading  pset 
1  0822  T  Introduction
(pdf,
mp4 (2021)) 
Sipser §01.2, §3 

2  0824  R  Time complexity, def of P
(pdf,
mp4 (2021)) 
Sipser §7.17.2 
pset1 (tex/pdf) 
     
3  0829  T  Nondeterminism
(pdf,
mp4 (2021)) 
Sipser §7.3 

4  0831  R  Nondeterminism
(pdf,
mp4 (2021)) 
Sipser §7.4 

     
5  0905  T  Nondeterminism
(pdf,
mp4 (2021)) 
Sipser §7.4 

6  0907  R  Space
(pdf,
mp4 (2021)) 
Sipser §8.0 
pset1 due (soln). pset2 (tex/pdf) 
     
7  0912  T  Space
(pdf,
mp4 (2021)) 
Sipser §8.18.3 

8  0914  R  Space
(pdf,
mp4 (2021)) 
Sipser §8.38.4 

     
9  0919  T  Space
(pdf,
mp4 (2021)) 
Sipser §8.58.6 

10  0921  R  Intractability
(pdf,
mp4 (2021)) 
Sipser §9.1 
pset2 due (soln). pset3 (tex/pdf) 
     
11  0926  T  Intractability
(pdf,
mp4 (2021)) 
Sipser §9.2 

12  0928  R  Circuits
(pdf,
mp4 (2021)) 
Sipser §9.3, AB §6 

     
13  1003  T  Circuits
(pdf,
mp4 (2021)) 
AB §6 

14  1005  R  Alternation
(pdf,
mp4 (2021*)) 
Sipser §10.3, AB §5.05.3 
pset3 due (soln) 
     
15  1010  T  Alternation
(pdf,
mp4 (2021*)) 
AB §5.5,6.4 

16  1012  R  Randomness
(pdf,
mp4 (2021*) [same mp4 as for lecture15]) 
Sipser §10.2, AB §7 
pset4 (tex/pdf) 
     
17  1017  T  Randomness
(pdf,
mp4 (2021)) 
AB §7.5 

18  1019  R  Randomness
(pdf,
mp4 (2021)) 
Sipser §10.2 

     
19  1024  T  Counting
(pdf,
mp4 (2021)) 
AB §17 

20  1026  R  Counting
(pdf,
mp4 (2021)) 
AB §17 
pset4 due .
pset5 (tex/pdf) 
     
21  1031  T  Interaction
(pdf,
mp4 (2021*)) 
Sipser §10.4 

22  1102  R  Interaction
(pdf,
mp4 (2021*)) 
Sipser §10.4 

     
23  1107  T  Interaction
(pdf,
mp4 (2021*)) 
Sipser §10.4 

24  1109  R  Query Complexity
(pdf,
mp4 (2021)) 
AB §12 
pset6 (tex/pdf) 
     
25  1114  T  Communication Complexity
(pdf,
mp4 (2020)) 
AB §13 

26  1116  R  Circuit Complexity
(pdf,
mp4 (2020)) 
AB §14; pdf 
pset5 due 
     
27  1128  T  Circuit Complexity
(pdf,
mp4 (2020)) 
AB §14; pdf
 
28  1130  R  Natural Proofs
(pdf,
mp4 (2020)) 
AB §23 
pset6 due 
     
 1205  T  Project Presentations


