Announcement
- <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.
About
- 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.