CS7805: Theory of Computation

[Home] [Schedule]

Course Staff

Huy L. Nguyen (WVH 358)

Office Hours:
Tuesday 11:30-12:30 WVH 358.

Class Time: Tuesday & Friday 9:50 am – 11:30 am

Class Room: Forsyth Building 236

Discussion Forum: Piazza

Homework Submission Site: Gradescope (use code 9XJ7VR to sign up)

Overview

The course examines formal models of computation, notions of undecidability, and complexity theory.

For the first half of the course, we will go through the topics typically taught in an undergraduate theory of computation course, but will do so at an accelerated pace with some basic topics left to the students to read on their own while we go into more depth on other topics in class. Topics include:

Finite automata and regular languages
Context-free grammars and pushdown automata
Turing Machines and Decidability
Undecidability and Reductions
Time Complexity and P vs NP
NP-completeness, Cook-Levin Theorem

For the last half of the course, we will cover some advanced topics in complexity theory from among the following possibilities:

Probabilistic Computation
Polynomial Hierarchy and EXP
Oracle Seperations
Circuit Complexity
Space Complexity
Interactive Proofs
Cryptography

Grading

Grades will be based on homeworks and one presentation. Homeworks typically include optional problems, which do not affect grades but they serve as additional study materials for motivated students. The final portion of the course includes presentations by students in the class on advanced topics in complexity theory.

Policies

No late homework will be accepted.
Collaborating with other students in the class on homework problems is fine and encouraged, though we urge you to attempt working out all of the problems by yourself first. In any case, you must write up your solutions, in your own words. Furthermore, if you did collaborate on any problem, you must clearly list all of the collaborators in your submission.
Finding solutions to homework problems on the web, or by asking students not enrolled in the class is strictly prohibited.

Textbooks

The first half of the course is based on the book "Introduction to the Theory of Computation" by Sipser. The second half of the course is based on the book "Computational Complexity: A Modern Approach" by Arora and Barak.

Presentations

There are 4-5 classes reserved for presentations. In each class, a group of 2-3 students will deliver a lecture on one of the following topics:

Cryptography. Arora-Barak 9.1-9.2
Communication Complexity. Arora-Barak 13.1-13.2
Circuit lower bounds. Arora-Barak 14.1-14.2
PCP and hardness of approximation. Arora-Barak 11.1-11.2, 11.5. This might take 2 classes and 2 groups.
Hardness amplification. Arora-Barak 19.1-19.2.

LaTeX

You should prepare your homework solutions using LaTeX, and submit PDFs to Gradescope. LaTeX is a scientific document preparation system; most CS technical publications are prepared using this tool. Great editors exist on most platforms. Some recomend TexShop for Mac. TeXstudio is a good cross-platform editor.

The not so short introduction to Latex is a good reference to get you started.