Syllabus: 
syllabus in pdf
less detailed syllabus in html 

Professor:  David Zuckerman Email: diz@cs.utexas.edu Phone: 4719729 Office: GDC 4.508 Office Hours: M 34, W 23 

TA: 
Subham Ghosh Email: subham.g@utexas.edu Office Hours: F 1112, 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.


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