# 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].