CSE696, Spring 2019

Computational Complexity

Instructor:

Dr. Kenneth W. Regan

326 Davis

645-4738

Office hours: TBA

email

Lectures:

TuTh 2:00--3:20pm

215 Clemens Hall

"Course Blog"

2015 Syllabus

Part of lecture notes for Thu. 2/5

Assignment 1, due Tue. 3/12.

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.

Some 2015 Assignments

Assignment 1

Take-Home Final, totaling 165 pts.