Boolean Circuits

08/28: Lecture 1

course overview, logistics, Boolean operation, (notes)
References: §0.2 in [Sipser].

08/30: Lecture 2

Boolean circuits, complexity, generic upper bound, (notes)
References: §9.3 in [Sipser], §6.1 in [Arora–Barak].

09/04: Lecture 3

existence of hard functions, straight-line programs, (notes)
References: §6.5 in [Arora–Barak].

Finite Automata

09/06: Lecture 4

deterministic finite automata, regular languages, (notes)
References: §1.1 in [Sipser].

09/09: Lecture 5

closure properties of regular languages, (notes)
References: §1.1 in [Sipser].

09/11: Lecture 6

non-deterministic finite automata, (notes)
References: §1.2 in [Sipser].

09/13: Lecture 7

non-deterministic vs. deterministic finite automata, (notes)
References: §1.2 in [Sipser].

09/16: Lecture 8

regular expressions vs. finite automata, (notes)
References: §1.3 in [Sipser].

09/18: Lecture 9

limitations of finite automata, (notes)
References: §1.4 in [Sipser].

09/20: Lecture 10

limitations of finite automata (continued), (notes)
References: §1.4 in [Sipser].

Turing Machines

09/23: Lecture 11

computation, deterministic Turing machines, (notes)
References: §3.1 and §3.3 in [Sipser].

09/25: Lecture 12

variants of Turing machines, Church–Turing hypothesis, (notes)
References: §3.2 in [Sipser].

09/27: Lecture 13

undecidable languages, diagonalization, (notes)
References: §4.2 in [Sipser].

09/30: Lecture 14

reductions, (notes)
References: §5.1, §5.3 in [Sipser].

10/2: Lecture 15

Rice’s theorem, (notes)
References: §5.1, §5.3 in [Sipser].

10/4: Lecture 16

Post’s correspondence problem
References: §5.2 in [Sipser].

10/7: Lecture 17

undecidability in logical theories
References: §6.2 in [Sipser].

Complexity Theory

10/11: Lecture 18

time complexity, extended Church–Turing Thesis, efficient computation
References: §7.1–7.2 in [Sipser].

10/16: Lecture 19

time hierarchy, polynomial-time verifiers, P vs NP
References: §7.3–7.4, §9.1 in [Sipser].

10/18: Lecture 20

SAT is NP-complete (Cook–Levin theorem); guest lecturer: Matvey Soloviev
References: §7.4 in [Sipser].

10/21: Lecture 21

NP-hardness reductions; guest lecturer: Matvey Soloviev
References: §7.5 in [Sipser].

10/23: Lecture 22

review time complexity
References: §7.1-7.4 in [Sipser].

10/25: Lecture 23

more NP-hardness reductions
References: §7.5 in [Sipser].

10/30: Lecture 24

proof systems, NP vs. coNP
References: §10.3 in [Sipser].

11/01: Lecture 25

good characterizations, NP∩coNP, factoring problem

11/04: Lecture 26

circuit complexity vs time complexity
References: §9.3 in [Sipser].

11/06: Lecture 27

probabilistic computation, error reduction
References: §10.2 in [Sipser].

11/11: Lecture 28

randomized algorithms vs circuits, polynomial identity testing, derandomization from hard functions

11/13: Lecture 29

checking matrix multiplication probabilistically in O(n²) time
References: Freivalds’ algorithm (Wikipedia)

11/15: Lecture 30

space complexity, logarithmic space vs polynomial time, graph search
References: §8.4 in [Sipser].

11/18: Lecture 31

directed connectivity in O(log n)² space, Savitch’s theorem
References: §8.1 in [Sipser].

11/20: Lecture 32

O(log n)-space random-walk algorithm for undirected connectivity
References: §7.7, §21.1 in [Arora–Barak].

11/22: Lecture 33

NL-completeness of directed connectivity; guest lecturer: Matvey Soloviev
References: §8.5 in [Sipser].

11/25: Lecture 34

cryptography, encryption, one-time pad, perfect secrecy
References: §9.1 in [Arora–Barak].

11/27: Lecture 35

computationally secure encryption, P vs NP and cryptography
References: §9.2 in [Arora–Barak].

12/02: Lecture 36

pseudorandom generators and one-way functions
References: §9.2 in [Arora–Barak].

12/04: Lecture 37

oracle machine, relativizing proofs, and P vs NP
References: §3.4 in [Arora–Barak].