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

Non-Determinism in Automata

Push Down Automata &  Context Free Languages

Introduction to TMs:

Deterministic Turing Machines
Church Turing Hypothesis

Turing Machine Variations Non-Deterministic TMs

Turing Machines & Variations:

[Umans pdf]

[Bulatov pdf]

[Busch pdf]

Turing Machine Variations: [Busch pdf]

[Arora]

[Beame]

[Spielman]

[Trevisan]

Mechanical Turing Machines

-       Using electro-mechanics

-       Using wooden gears

[T, Ch1]

[AB, Intro]

[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:

[Umans pdf]

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, p13-14]

Constant Space Compression:

[Umans pdf]

 ([AB, Ch 4, p 82-83])

More on Time Complexity: [Umans pdf] [Bulatov pdf]

Constant Time Speedup:

Time Complexity

More on Space Compression: [Busch pdf]

[Miltersen]

Tape Reduction & Time Hierarchy:

[Miltersen]

[T, Ch2]

[T, Ch3, p13-14]

[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]

[Bulatov pdf]

NonDeterministic Time Hierarchy: [Umans pdf]

[AB, Ch 4, p 84-85]

Sparse Languages and NP: [Umans pdf]

Ladner’s Thm: a Problem in P not NP-Complete [Umans pdf]

[AB, Ch 4, p 85-87]

More on NonDeterministic Time Hierarchy: [Bulatov pdf]

[Arora], [Arora]

[Spielman]

[T, Ch4]

[G, Ch4]

Recitation by TA

Weds

Jan 25

5

Thurs

Jan 26

P and NP-Completeness:

Polytime Reductions

Logspace Reductions

Completeness

P, NP, NP-Completeness
Cook-Levin Theorem and 3SAT

NP-Completeness via Reductions
coNP, EXPTIME, NEXPTIME

Reduction & Completeness Defined: [Umans pdf] [AB, Ch 2]

P Completeness: [Umans pdf]

NP Completeness of SAT: [Busch pdf]

Reduction Proofs of NP Completeness: [Busch pdf]

More on NP Completeness of SAT: [Bulatov pdf]

Further  Reduction Proofs of NP Completeness: 

[Bulatov pdf]

[Bulatov pdf]

[Bulatov pdf]

[T, Ch5]

[T, Ch7]

[T, Ch8] 

[Arora]

[Spielman]

EXP Completeness: [Umans pdf]

[G, Ch2]
[Pap, Ch9]

[G, AppA]

[GJ, Ch3,4]

[HMU, Ch10]

6

Tues

Jan 31

Homework #1 Due

Homework #2 Assigned

Oracles & Relativized Proof Techniques

Oracle Turing Machines
Relativized Proofs

Relativization:

[Umans pdf]

[AB, Ch 4, p 88-92]

[Arora, p3-4] [Spielman, p1-2]

[AB, Ch 4]

Recitation by TA

Wends

Feb 1

Complexity & Encryption [Fu pdf]

7

Thurs

Feb 2

Polynomial Hierarchy (PH):
Alternation

Properties of PH
Oracle Characterization of PH

PSPACE Complete Problems:

Quantified Boolean Logic

Complexity of 2 Player Games

Polynomial Hierarchy & PSPACE:

[Umans pdf]

[Arora]

PSPACE Complete Problems:

 [AB, Ch 3]

[Beame]

[Spielman]

[Miltersen]

[Miltersen]

[AB, Ch 5]

[Pap, Sec16.2]
[CKS]

[T, Ch9]

8

Tues

Feb 7

Project Abstract (& Short List of References) Due (1 page)

Nondeterministic Space Complexity:
PSPACE Completeness

Savitch’s proof PSPACE=NPSPACE
NSPACE=coNSPACE 

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]

Time-Space Tradeoffs [Beame] [Miltersen]

[AB, Ch 3]

 [G, Ch5]

 [Pap, Ch19]

[AB, Ch 16]

[G, Ch5]

[Pap, Ch7,16]

 [T, Ch6]

[T, Ch10]

[HMU, Ch11]

Recitation by TA

Wends

Feb 8

PSPACE [Fu pdf]

9

Thurs Feb 9

Kolmogorov Complexity

Definitions

Incompressibility for lowerbounds

Kolmogorov Complexity (KC)

Foundations of KC:

Intro to KC: [Li, pdf]

Lower Bounds by Incompressibility Method:  

[Li, pdf]

Average-case Analysis & Lower Bounds by Incompressibility Method: [Li] [Li, pdf]

Conditional KC: [Li, pdf]

Prefix KC & Universal Input Dist: [Li, pdf]

10

Tues

Feb 14

Homework #2 Due

Homework #3 Assigned

Parallel Computational Complexity:

Circuit Complexity & NC:
P/poly, Logspace uniform classes

Can P/poly resolve P versus NP?

P-Completeness and Linear Programming

Log-depth Circuits, NC
Relation of NC to Parallel Computing

Examples of NC parallel algorithms

Introduction to Circuit Complexity:

[Bulatov pdf]

[Umans pdf]

[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:

[Miltersen]

Circuit Lower Bounds:

Shannon’s Counting Argument, Formula lower bound on Andreev function,

Karp-Lipton Theorem

Size Complexity of Circuits: [Trevisan]

Shannon’s Counting Argument:

[Spielman] (last page)

 [Umans pdf]

Karp-Lipton Theorem

[Umans pdf]

[Beame]

[Spielman]

More on Karp-Lipton 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

[Miltersen]

[AB, Ch 6]

[G, Ch3]

[Pap, Ch11]

Recitation by TA

Wends

Feb 22

Parallel Computing

[Fu pdf]

          13

Thurs Feb 23

Lower Bounds for Poly Size Circuits with Unbounded Fan-in and Constant Depth:

Parity is not in AC⁰:

- Simple Proof for depth 2

- Hastad‘s proof for constant depth via switching lemma

Switching Lemma Proof that Parity is not in AC⁰:

[Trevisan]

[Arora]

Switching Lemma Primer:[Beame]

13.1 in [AB, Ch 13])

Other Notes on Switching Lemma Proof that Parity is not in AC⁰:

[Beame]

Alternative Polynomial Proof  Parity is not in AC⁰: [Trevisan]

Majority Circuits

[Miltersen]

Razborov's lower bound on monotone circuits for clique

[Umans pdf]

[Miltersen]

[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
Examples of Probabilistic TMs

Error Reduction

BPP in P/poly

Randomized Complexity Classes & Error Reduction:

[Umans pdf]

 [Arora]  

[Bulatov pdf] [Bulatov pdf] [Beame]

[Spielman]

[Miltersen]

[Miltersen]

[Miltersen]

[Miltersen]

[AB, Ch 13]

[G, AppB]

[Pap, Ch11]

Recitation by TA

Wends

March 1

Randomness [Fu pdf]

15

Thurs March 2

Randomized Complexity, Cont:

Proof of the Schwartz-Zippel Lemma

Polynomial Identity Testing + Schwartz-Zippel:

[Umans pdf]

[Reif]

 [AB, Ch 7]

[AB, Ch 11]

[G, Ch6]

[HMU, Ch11]

[G, AppD] 

16

Tues

March 7

Randomized Complexity, Cont:

Unique Sat:

The Valiant-Vazirani Theorem

Valiant-Vazirani Theorem for NP Problems with Unique solutions:

[Umans pdf]

 [Spielman]

More on Valiant-Vazirani Theorem:

[Trevisan]

[AB, Ch 11]

[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:

 [Umans pdf]

#P completeness of Counting Cycle Covers and Permanent:

[Beame]

[Arora]

More on Toda’s Theorem:

[Spielman]

[Beame]

[Miltersen]

More on #P completeness

[Miltersen]

[Miltersen]

 [Bulatov pdf] [Bulatov pdf] [Beame]

 [Spielman]

[Trevisan]

 [AB, Ch 8]

[G, Ch6]

Spring Break

March 11-18

18

Tues

March 21

Homework #4 Due

Homework #5 Assigned

Preliminary Draft Project Paper Due

Pseudorandom Number Generation & Cryptography:

- One Way Functions
- Pseudorandom Number Generators
- Pseudorandom generation for BPP

Blum-Micali-Yao (BMY) Pseudorandom generator:

[Umans pdf]

[AB, Ch 10]

Impagliazzo’s hard-core set theorem and Yao’s XOR Lemma [O'Donnell] [AB, Ch 18]

Goldreich-Levin Hardcore Bit:

[Arora]

[Arora]

Nisan-Wigderson (NW)PseudoRandom Generator:

[Umans pdf]

[Trevisan]

[Miltersen]

[Miltersen]

[Miltersen]

Cryptography & Cryptography:

Trapdoor Functions, Cryptography
RSA and Discrete Log Cryptosystems

[Pap, Ch18] [AB, Ch 16]

 [G, Ch8]

[Pap, Ch11]

  [G, AppC]

Recitation by TA

Wends

March 22

Randomness [Fu pdf]

19

Thurs

March 23

Pseudorandom Number Generation & Cryptography, Cont:

- Goldreich-Levin hard bit

- Yao's Lemma

Blum-Micali-Yao (BMY)Pseudorandom generator using:

- Goldreich-Levin hard bit

- Yao's Lemma

[Umans pdf]

[AB, Ch 10]

 Intro to Hardness amplification & error correcting codes::  [Umans pdf]

-Transforming worst-case hardness into average-case hardness

- List decoding and its use for hardness

amplification

Randomness Extractors:

[Umans pdf]

[G, Ch7]

[G, AppE]

  20

Tues

March 28

Interactive Proofs (IP):
Brief Overview of Zero Knowledge Proofs

-Interactive proofs of graph non-isomorphism
-Applications to Program Checking

-Author-Merlin Games

Proof IP = PSPACE

the classes MA and AM

Derandomization of MA and AM

[Bulatov pdf]

[Arora]

[Umans pdf]

[Miltersen]

[Miltersen]

[Beame]

[Beame]

[Beame]

[Spielman]

[Spielman]

[Spielman]

[AB, Ch 9]

[G, Ch9]

[Pap, Ch19]

         21

Thurs

March 30

Probabilistically Checkable Proofs (PCP):

[Miltersen]

Hardness of Approximation:

Overview of Direct Proof of PCP Theorem:
Hardness of Approximating MAX-SAT

NP in PCP(poly(n),1)

[Umans pdf]

[Bulatov pdf]

[Umans pdf]

[Beame]

[Beame]

[Beame]

[Beame]

[Spielman]

[Spielman]

[Spielman]

[Spielman]

[Miltersen]

[Miltersen]

[Miltersen]

[AB, Ch 19]

[AB, Ch 20]

22

Tues

April 4

Homework #5 Due

Homework #6 Assigned

Introduction to

Communication Complexity

Deterministic and Randomized Communication Complexity:

[Umans pdf]

More on Communication Complexity:

[Woo]

[Arora]

Primality & One-Way

 Functions [Fu pdf]

[AB, Ch 12]
[Pap, Ch11]

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]

 [AB, Ch 21]

24

Tues

April 11

Quantum

Computation,

Continued

 -Quantum Factoring

 -Quantum Search

Quantum Algorithms:

Grover's Quantum Algorithm for NP Search:

[Melkebeek]

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]

[AB, Ch 21]

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]

[Umans pdf]

 More notes on Natural proofs:

[Arora]

[AB, Ch 23]

 [AB, Ch 22]

26

Tues

April 18

Homework #6 Due

Independence in First Order Logics

Independence in Logics:

[Aaronson]

[Aaronson Survey]

Recitation by TA

Wends

April 19

Final Exam Review

[Fu pdf]

[Reif]

See Short Course Review: [Umans pdf]

Tues

April 25

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

See Schedule of Final Exams

Thursday, May 4,

2 PM – 5 PM

Final Exam