Class 

Date 

Topics 

Primary

Lecture

Notes 

Secondary

Lecture

Notes 

Primary

Textbook

Readings 

Secondary Textbook

Readings 

0

Thurs Jan 9

By TA

Overview of Course

By TA

Detailed Description of Course Material: see Schedule

[T, Ch1]

[AB, Intro]

[AB, Ch 1]

[G, Ch1]

[HMU, Ch 8]

1

Tues

Jan 14

Homework #1 Assigned

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

Weds

Jan 15

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] 

3

Thurs

Jan 16

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 21

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]

5

Weds

Jan 22

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

Thurs

Jan 23

Oracles & Relativized Proof Techniques

Oracle Turing Machines
Relativized Proofs

Oracles & Relativized Proof Techniques

Oracle Turing Machines
Relativized Proofs

[Umans pdf]

[AB, Ch 4, p 88-92]

More on Oracles & Relativized Proof Techniques

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

7

Tues

Jan 28

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

Polynomial Hierarchy (PH):
Alternation

Properties of PH
Oracle Characterization of PH

PSPACE Complete Problems:

Quantified Boolean Logic

Complexity of 2 Player Games

PSPACE [Fu pdf]

Polynomial Hierarchy & PSPACE:

[Umans pdf]

[Arora]

PSPACE Complete Problems:

 [AB, Ch 3]

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]

[Beame]

[Spielman]

[Miltersen]

[Miltersen]

[Trevisan]

[Spielman]

Optional: Time-Space Tradeoffs [Beame] [Miltersen]

[AB, Ch 4]

8

Weds

Jan 29

Nondeterministic Space Complexity:
PSPACE Completeness

Savitch’s proof PSPACE=NPSPACE
NSPACE=coNSPACE 

L, NL, Logspace Reductions

Nondeterministic Log Space(NL):

IS Theorem: NL=coNL:

PSPACE [Fu pdf]

Polynomial Hierarchy & PSPACE:

[Umans pdf]

[Arora]

PSPACE Complete Problems:

 [AB, Ch 3]

Nondeterministic Space Complexity: [Umans pdf]

Nondeterministic Space: [Bulatov pdf] [Umans pdf]

[Arora]

Nondeterministic Log Space(NL): [Bulatov pdf] [Miltersen]

IS Theorem: NL=coNL:[Umans pdf]

Optional:

[Trevisan]

[Trevisan]

[Beame]

[Spielman]

[Miltersen]

[Miltersen]

[Trevisan]

[Spielman]

Optional: Time-Space Tradeoffs [Beame] [Miltersen]

[AB, Ch 4]

9

Thurs

Jan 28

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

Quiz 1

Proctored by TA

Tues Feb 4

Project Summary, Introduction, and Outline Due (3 pages)

Homework #1 Due

Homework #2 Assigned

Quiz 1 on Computability & Classical Complexity Theory:

- Diagonalization

- Undecidability

-Speedup Theorem

-Complexity Classes: P, NP, Polynomial Hierarchy, NL, PSPACE, EXP

-Reductions

-Completeness Proofs

11

Tues

Feb 11

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]

12

Wends

Feb 12

Basic Circuit Constructions:

[Miltersen]

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)

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

13

Thurs

Feb 13

Karp-Lipton Theorem on Circuits

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]

14

Tues

Feb 18

Homework #2 Due

Homework #3 Assigned

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]

         15

Wends

Feb 19

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

L Parallel Computing

[Fu pdf]

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]

16

Thurs Feb 20

Randomized Complexity:

RP, BPP, ZPP
Examples of Probabilistic TMs

Error Reduction

BPP in P/poly

Proof of the Schwartz-Zippel Lemma

Randomness [Fu pdf]

Randomized Complexity Classes & Error Reduction:

[Umans pdf]

 [Arora]  

Polynomial Identity Testing + Schwartz-Zippel:

[Umans pdf]

[Reif]

[Bulatov pdf] [Bulatov pdf] [Beame]

[Spielman]

[Miltersen]

[Miltersen]

[Miltersen]

[Miltersen]

[AB, Ch 7]

[AB, Ch 11]

 [AB, Ch 13]

[G, Ch6] [G, AppB]

[Pap, Ch11]

[HMU, Ch11]

[G, AppD] 

17

Quiz 2

Proctored by TA

Tues

Feb 25

Quiz 2

- Kolmogorov Complexity

-Parallel Complexity

-Circuit Lower Bounds

-Decision Tree Complexity

18

Tues

March 4

Homework #3 Due

Homework #4 Assigned

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] 

19

Weds

March 5

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]

20

Thurs

March 6

Pseudorandom Number Generation & Cryptography:

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

Complexity & Encryption [Fu pdf]

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]

Spring Break

March 11-17

21

Tues

March 18

Homework #4 Due

Homework #5 Assigned

Preliminary Draft Project Paper Due

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]

22

Wends

March 19

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]

        23

Thursday March 20

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]

24

Tues

April 1

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]

      25

Wends April 2

Intro to Quantum

Computation

Qubits

Unitary Operations & Projections

Quantum Circuits

Quantum Algorithms

Quantum intro lectures:

[Spielman]

[Arora]

Quantum Complexity Classes:

[Spielman]

 [AB, Ch 21]

26

Thurs April 3

Quantum

Computation,

Continued

 -Quantum Search

-Quantum Factoring

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]

27

Quiz 3

Proctored by TA

Tues April 8

Quiz 3

- Randomized Complexity

- Counting Complexity

- Pseudorandom Number Generation & Cryptography

-Interactive Proofs

- Quantum Computation

28

Tues

April 15

Homework #6 Due

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]

29

Wends

April 16

Independence in First Order Logics

Final Exam Review

[Fu pdf]

[Reif]

Independence in Logics:

[Aaronson]

[Aaronson Survey]

See Short Course Review: [Umans pdf]

Tues April 29

Final Project Paper Due: email pdf to jhreif@gmail.com

See Schedule of Final Exams

May 2

7:00PM – 9:00PM

Final Exam