John H. Reif
Spring Semester, 2023
Class 
Date 
Topics 
Primary Lecture Notes 
Secondary Lecture Notes 
Primary Textbook Readings 
Secondary Textbook Readings 
1 
Thurs Jan 12 
Overview of
Course Brief Review
of Formal Language Theory Finite State Automata & Regular Expressions NonDeterminism in Automata Push Down Automata &
Context Free Languages Introduction
to TMs: Deterministic Turing Machines Turing
Machine Variations NonDeterministic TMs 
Turing Machines & Variations: 
Turing Machine Variations: [Busch pdf] [Arora] [Beame] [Spielman] [Trevisan] Mechanical Turing Machines 
[T, Ch1] [AB, Ch 1] [G, Ch1] 
[HMU, Ch 8] 
2 
Tues Jan 17 Homework #1 Assigned 
Universal
Turing Machines Countable and
Uncountable Sets Decidable and
Undecidable Languages Diagonalization
Proofs 
Decidability
Reductions: [Busch pdf] Universal
Turing Machine & Noncountable Sets: [Busch pdf] Undecidable Languages: [Busch pdf] 
Undecidability of Halting Problem: Undecidability Reductions: [Busch pdf] 


Recitation by
TA 
Weds Jan 18 





3 
Thurs Jan 19 
Time and Space
Complexity:  Complexity Classes Deterministic Time Space Complexity Constant Space Compression Constant Time Speedup Time and Space Hierarchy Theorems 
Intro to Time Complexity & Complexity Classes: [Umans pdf] Constant Time
Speedup: [Umans pdf] [T, Ch3, p1314] Constant Space
Compression: ([AB, Ch 4, p 8283]) 
More on Time Complexity: [Umans pdf] [Bulatov pdf] Constant Time
Speedup: More on Space
Compression: [Busch pdf] Tape Reduction & Time Hierarchy: 
[T, Ch2] [T, Ch3, p1314] [AB, Ch 4] [Pap,Ch7,8] [Pap, Ch14] 

4 
Tues, Jan 24 
Nondeterminism
and NP  NonDeterministic
TMs 
NonDeterministic Time Hierarchy  Ladner’s Thm: If P≠ NP then ∃ NP Language neither NP complete nor
in P Sparse Languages and NP 
Nondeterministic Complexity and NP: [Umans pdf] NonDeterministic Time Hierarchy: [Umans pdf]
[AB, Ch 4, p 8485] 
Ladner’s Thm:
a Problem in P not NPComplete [Umans pdf] [AB, Ch 4, p 8587] More on NonDeterministic Time Hierarchy: [Bulatov pdf] [Spielman] 
[T, Ch4] [G, Ch4] 

Recitation by
TA 
Weds Jan 25 





5 
Thurs Jan 26 
P and
NPCompleteness: Polytime Reductions Logspace Reductions Completeness P, NP, NPCompleteness NPCompleteness via Reductions 
Reduction
& Completeness Defined: [Umans pdf] [AB, Ch 2] 
More on NP Completeness of SAT: [Bulatov pdf] Further Reduction Proofs of NP Completeness: [T, Ch5] [T, Ch7] [T, Ch8] [Arora] [Spielman] 
[G, Ch2] 
[G, AppA] [GJ, Ch3,4] [HMU, Ch10] 
6 
Tues Jan 31 Homework #1 Due Homework #2 Assigned 
Oracles &
Relativized Proof Techniques Oracle Turing Machines 
Relativization: [AB, Ch 4, p 8892] 

[AB, Ch 4] 

Recitation by
TA 
Wends Feb 1 





7 
Thurs Feb 2 
Polynomial
Hierarchy (PH): Properties of PH PSPACE
Complete Problems: Quantified Boolean Logic Complexity of 2 Player Games 
Polynomial
Hierarchy & PSPACE: [Arora] PSPACE
Complete Problems: [AB, Ch 3] 
[Beame] [Spielman] 
[AB, Ch 5] [Pap, Sec16.2]

[T, Ch9] 
8 
Tues Feb 7 Project
Abstract (& Short List of References) Due (1 page) 
Nondeterministic
Space Complexity: Savitch’s proof PSPACE=NPSPACE L, NL, Logspace Reductions Nondeterministic
Log Space(NL): IS Theorem:
NL=coNL: 
Nondeterministic
Space Complexity: [Umans pdf] 
Space
Complexity: [Umans pdf] [Bulatov pdf] [Miltersen] Nondeterministic
Space: [Bulatov pdf] [Umans pdf] [Arora] Nondeterministic
Log Space(NL): [Bulatov pdf] [Miltersen] IS Theorem:
NL=coNL:[Umans pdf] Optional: [Trevisan] [Trevisan] [Trevisan] [Spielman] 
[AB, Ch 3] [G, Ch5] [Pap, Ch19] [G, Ch5] [Pap, Ch7,16] 
[T, Ch6] [T, Ch10] [HMU, Ch11] 
Recitation by
TA 
Wends Feb 8 





9 
Thurs Feb 9 
Kolmogorov
Complexity Definitions Incompressibility for lowerbounds 
Kolmogorov
Complexity (KC) Foundations
of KC: Lower
Bounds by Incompressibility Method: 
Averagecase
Analysis & Lower Bounds by Incompressibility Method: [Li] [Li, pdf] 


10 
Tues Feb 14 Homework #2 Due Homework #3 Assigned 
Parallel
Computational Complexity: Circuit
Complexity & NC: Can P/poly resolve P versus NP? PCompleteness and Linear Programming Logdepth Circuits, NC Examples of NC parallel algorithms 
Introduction
to Circuit Complexity: 
[Beame] [Spielman] 


Quiz 1 
Weds Feb 15 
Quiz on Formal
Language Theory and Recursion Theory:  Finite State Automata  Context Free Languages  Diagonalization  Undecidability 




11 
Thurs Feb 16 
Basic Circuit
Constructions: Circuit Lower
Bounds: Shannon’s Counting Argument, Formula lower bound on
Andreev function,

Size
Complexity of Circuits: [Trevisan] Shannon’s
Counting Argument: [Spielman] (last page) KarpLipton
Theorem 
[Beame] [Spielman] More on KarpLipton
Theorem [Arora] [Spielman] Formula
lower bound on Andreev function: [Umans pdf] 
[AB, Ch 6] [G, Ch3] [Pap, Ch11] 

12 
Tues Feb 21 
Decision Tree
Complexity: Decision Trees Adversaries Certificate Complexity Randomized Decision Trees Distributional Complexity Yao’s Lemma on Probabilistic Decision Trees 
Decision Tree
Complexity: [Arora] 
Branching
Programs 
[AB, Ch 6] [G, Ch3] [Pap, Ch11] 

Recitation by
TA 
Wends Feb 22 
Parallel
Computing 




13 
Thurs Feb 23 
Lower Bounds
for Poly Size Circuits with Unbounded Fanin and Constant Depth: Parity is not
in AC^{0}:  Simple Proof for depth 2  Hastad‘s proof for constant depth via switching lemma 
Switching
Lemma Proof that Parity is not in AC^{0}: [Trevisan] [Arora] Switching
Lemma Primer:[Beame] 13.1 in [AB, Ch 13]) 
Other Notes on Switching
Lemma Proof that Parity is not in AC^{0}: [Beame] Alternative
Polynomial Proof Parity is not in AC^{0}: [Trevisan] Majority Circuits
Razborov's
lower bound on monotone circuits for clique 
[Arora] [Beame] [Trevisan] 

14 
Tues Feb 28 Homework #3 Due Homework #4 Assigned Project Summary,
Introduction, and Outline Due (3 pages) 
Randomized
Complexity: RP, BPP, ZPP Error Reduction BPP in P/poly 
Randomized Complexity Classes &
Error Reduction: [Arora] 
[Bulatov pdf] [Bulatov pdf] [Beame] [Spielman] 
[G, AppB] [Pap, Ch11] 

Recitation by
TA 
Wends March 1 





15 
Thurs March 2 
Randomized
Complexity, Cont: Proof of the SchwartzZippel Lemma 
Polynomial Identity Testing + SchwartzZippel: [Reif] 

[AB, Ch 7] [G, Ch6] 
[HMU, Ch11] [G, AppD] 
16 
Tues March 7 
Randomized
Complexity, Cont: Unique Sat: The ValiantVazirani Theorem 
ValiantVazirani Theorem for NP Problems with Unique
solutions: [Spielman] 
More on ValiantVazirani Theorem: [Trevisan]

[G, Ch6] 
[HMU, Ch11] [G, AppD] 
Quiz 2 
Weds March 8 
Quiz on
Classical Complexity Theory: Speedup & Slowdown Thms Complexity Classes: P, NP, Polynomial Hierarchy, NL,
PSPACE, EXP Reductions Completeness Proofs





17 
Thurs March 9 
Counting
Complexity Classes: #P defined Counting Cycle Covers and Bipartite Matchings are #P Complete Permanent is #P complete 
#P
defined: #P completeness
of Counting Cycle Covers and Permanent: [Beame] [Arora] 
More on Toda’s
Theorem: [Spielman] [Beame] More on #P
completeness [Bulatov pdf] [Bulatov pdf] [Beame] [Spielman] [Trevisan] 
[AB, Ch 8] [G, Ch6] 

Spring
Break 
March 1118 





18 
Tues March 21 Homework #4 Due Homework #5 Assigned Preliminary
Draft Project Paper Due 
Pseudorandom
Number Generation & Cryptography:  One Way Functions 
BlumMicaliYao (BMY) Pseudorandom
generator: 
Impagliazzo’s
hardcore set theorem and Yao’s XOR Lemma [O'Donnell] [AB, Ch 18] GoldreichLevin
Hardcore Bit: [Arora] [Arora] NisanWigderson (NW)PseudoRandom Generator: [Trevisan] 
Cryptography
& Cryptography: Trapdoor Functions, Cryptography [Pap, Ch18] [AB, Ch 16] [G, Ch8] [Pap, Ch11] 
[G, AppC] 
Recitation by
TA 
Wends March 22 





19 
Thurs March 23 
Pseudorandom
Number Generation & Cryptography, Cont:  GoldreichLevin hard bit  Yao's Lemma 
BlumMicaliYao (BMY)Pseudorandom
generator using:  GoldreichLevin hard bit  Yao's Lemma 
Intro to
Hardness amplification & error correcting codes:: [Umans pdf]
Transforming worstcase
hardness into averagecase hardness  List decoding and its use for hardness amplification Randomness Extractors: 
[G, Ch7] [G, AppE] 

20 
Tues March 28 
Interactive
Proofs (IP): Interactive proofs of graph nonisomorphism AuthorMerlin Games Proof IP = PSPACE the classes MA and AM Derandomization of MA and
AM 
[Arora] 
[Beame] [Beame] [Beame] [Spielman] [Spielman] [Spielman] 
[AB, Ch 9] [G, Ch9] [Pap, Ch19] 

21 
Thurs March 30 
Probabilistically Checkable Proofs (PCP): Hardness of Approximation: Overview of Direct Proof of PCP Theorem: NP in
PCP(poly(n),1) 

[Beame] [Beame] [Beame] [Beame] [Spielman] [Spielman] [Spielman] [Spielman] 


22 
Tues April 4 Homework #5 Due Homework #6 Assigned 
Introduction to Communication
Complexity 
Deterministic and Randomized Communication
Complexity: More on Communication Complexity: [Woo] [Arora] 
Primality & OneWay 
[AB, Ch 12] 

Recitation by
TA 
Wends April 5 





23 
Thurs April 6 
Intro to Quantum Computation Qubits Unitary Operations & Projections Quantum Circuits Quantum Algorithms 
Quantum intro
lectures: [Spielman] [Arora] Quantum Complexity
Classes: [Spielman] 



24 
Tues April 11 
Quantum Computation, Continued Quantum Factoring Quantum Search 
Quantum Algorithms: Grover's Quantum Algorithm for NP
Search: Quantum Algorithms for Fourier Transform
& Discrete Log: [Spielman] 
Additional: More on Grover's Quantum Algorithm for
NP Search: [Spielman] [Wiki] Shor’s
Quantum Algorithm for integer factorization: [Wiki] [Arora] 


Quiz 3 
Wends April 12 
Quiz  Kolmogorov Complexity  Circuit Lower Bounds  Randomized Complexity  Hardness amplification 




25 
Thurs April 13 
Logic &
Proof in complexity theory: Why are complexity lower bounds so
difficult?  Natural proofs 
Natural
proofs: [Aaronson] 
More notes on
Natural proofs: [Arora] 

26 
Tues April 18 Homework #6 Due 
Independence
in First Order Logics 
Independence
in Logics: [Aaronson] 



Recitation by
TA 
Wends April 19 
Final Exam Review [Reif] 





Tues April 25 Final Project
Paper Due: email pdf to reif at
cs.duke.edu 





Thursday, May 4, 2 PM – 5 PM 
Final Exam 

Required Class Text Books: (digital text
books [AB] and [G] used by permission)
Additional
Readings in Complexity Theory: ([Tompa] used by
permission)
Lecture Notes
Credits: (all used by permission)
\