CS353 - Theory of Computation (Fall 2018)

Syllabus: syllabus in pdf
less detailed syllabus in html
Professor: David Zuckerman
Email: diz@cs.utexas.edu
Phone: 471-9729
Office: GDC 4.508
Office Hours: M 3-4, W 2-3
TA: Subham Ghosh
Email: subham.g@utexas.edu
Office Hours: F 11-12, GDC 1.302
Text: Michael Sipser, Introduction to the Theory of Computation
Course Overview: This undergraduate course develops a theoretical framework to understand computation. Perhaps the most important concept in the class is that there are limits to computation. Some languages are uncomputable; others are "complete" for certain hard classes, such as NP. Sometimes these limitations prove useful, as in the case of cryptography. We will also explore tradeoffs and relationships between different computational resources, such as time and space. The course should be similar to the 2016 version. A list of topics and approximate times follows.

Topic Chapter(s) Approximate Time
Regular Languages 1 1-2 weeks
Decidability 3-4 1-2 weeks
Reducibility 5 1 week
Time Complexity 7 3-4 weeks
Space Complexity 8 1-2 weeks
Intractibility 9 1 week
Parallel Computation 10.5 1 lecture
Approximation & Randomization 10.1,10.2 1 week
Cryptography & Interactive Proofs 10.4, 10.6 1-2 weeks

Useful Pointers: Theory of Computing Blog Aggregator
P vs. NP page
List of many NP-complete problems
Certificate definition of NL is in Chapter 4 of Arora & Barak's graduate-level textbook Computational Complexity: A Modern Approach.
Winning strategies in two-player games
Complexity of various games and puzzles
Bit commitment overview
Salil Vadhan's course notes on cryptography, including zero knowledge

Last modified: December 6, 2018.