CSE696, Spring 2021

Computational Complexity

Instructor:

Dr. Kenneth W. Regan

326 Davis

645-4738

Office hours: TBA

email

Lectures:

MoWe 3:00--4:20pm

Online Only

"Course Blog"

2015 Syllabus

Texts

  1. Excerpts from Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak. (Freely available; selections will be specified.)
  2. Quantum Algorithms Via Linear Algebra, by Richard J. Lipton and Kenneth W. Regan. (Cambridge, MA: MIT Press, 2014)
  3. Book Chapters on Computational Complexity for the CRC Handbook on Algorithms and Theoretical Computer Science: Complexity Classes, Reducibility and Completeness, Other Complexity Classes and Measures. These open as 2-column PDF files. (Parts of the first two chapters were used in CSE596, but Chapter 29 and other parts were not.)

Supplementary Notes

  1. Handout, "Oracle Turing Machines and the Arithmetical Hierarchy", which parallels material sometimes included in CSE596. In my initial lectures I have decided to approach the hierarchies by logic first and machines later, and the expanded undecidability material here will not be emphasized. But this might help as a technical source.

Approximate Course Calendar: Two weeks on the polynomial hierarchy and oracles, then four weeks on probabilistic and counting classes, four weeks on quantum, and four weeks on interactive proof systems and other advanced topics.



Lecture Notes (will be accumulated here)

  1. Week 1: Mon. Wed.
  2. Week 2
  3. Week 3
  4. Week 4
  5. Week 5 plus HW-solving examples
  6. Week 6

Assignments (will be posted here)

Assignment 1, due Fri. 2/26

Assignment 2, due Mon. 3/15

Assignment 3, due Mon. 4/26

Assignment 4, due Mon. 5/10


Some Assignments From 2019

Spr'19 Assignment 1

Spr'19 Assignment 2

Spr'19 Assignment 3