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