(Fall 2021) CS 581 - Theory of computation

Computational complexity


  • <2021-10-04 Mon> Future communications will be primarily via Slack. Check frequently “Schedule” page for reading materials, and Google Classroom for classwork.
  • <2021-09-27 Mon> The Fall term is officially here. Let’s get started!
  • <2021-09-09 Thu> This class is switched to Attend Anywhere mode in Fall’21. Stay tuned for more information.
  • <2021-09-06 Mon> Syllabus available. Schedule and resource pages are updated.
  • <2021-05-10 Mon> Welcome! Please stay tuned for updates.


  • Syllabus: PDF.
  • Instructor: Prof. Fang Song
  • Email: fsong “AT” pdx.edu. Start your email subject line with “f21-581-toc”.
  • Lectures: TR 14:00 - 15:15 @ CH 449
  • Office hours: TBD
  • TA: Pei Du. Office hours: TBD.
  • Google classroom: join with code t32slgn.
  • Overview: Computation is a familiar term to all computer scientists. But what is computation after all? What problems are computable (Computability), and how “efficient” can we compute them (Complexity)? This course, assuming a prior introductory exposure to the theory of computation, continues an in-depth exploration to these fundamental questions. The focus will be on computational complexity, including time, space, randomness complexity. We will also dive into selected advanced topics such as interactive proof systems and quantum computing.
  • Prerequisite: CS 311 or equivalent. You need to be familiar with the basics of computability theory, and be comfortable with reading and writing mathematical proofs.
  • Text: No required text. See Resource page for suggested texts and additional useful materials.