CS353 - Theory of Computation (Fall 2014)

Syllabus: syllabus in pdf
Logistics: MW 2:00-3:30
GDC 4.302
Unique Number: 53075
Course web page: http://www.cs.utexas.edu/~diz/353
Professor: David Zuckerman
Email: diz@cs.utexas.edu
Phone: 471-9729
Office: GDC 4.508
Office Hours: MTh 3:30-4:30.
TA: Eshan Chattopadhyay
Email: eshanc@cs.utexas.edu
Who should
take this?
Students interested in the science of computation, who like mathematics and proofs, and who like a challenge. Students who liked CS 341 or 341H, or CS 331 or 331H, or CS 357 or 357H should like this class. This course is excellent preparation for graduate school.
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. A list of topics and approximate times follows.

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

Prerequisites: The following coursework with a grade of at least C-: Computer Science 311 or 311H or 313K or 313H, 314 or 314H or 315 or 315H, 310 or 310H or 429 or 429H, 331 or 331H or 341 or 341H or 357 or 357H, and Mathematics 408C, 408K, or 408N. Naturally, you will also need the prerequisites of these prerequisites, especially Probability (SSC 321 or M 362K). While Automata Theory (CS 341) is not required, it is highly recommended.
Canvas: We will use Canvas, which contains Piazza. Homeworks and grades will be posted on Canvas. We will use Piazza for class discussion. Instead of emailing questions to the teaching staff, please post your question to Piazza.
Useful Pointers: Theory of Computing Blog Aggregator
P vs. NP page
List of many NP-complete problems
2SAT in P
Certificate definition of NL is Definition 4.17 (Chapter 4) in Arora & Barak's graduate-level textbook Computational Complexity: A Modern Approach.
Complexity of various games and puzzles
Scribe notes containing Shannon's counting argument for the existence of functions with large circuit complexity
Bit commitment overview
Salil Vadhan's course notes on cryptography, including zero knowledge
Complexity Theory: A Modern Approach, a graduate-level text by Arora and Barak.
Students with
Disabilites:
Any student with a documented disability (physical or cognitive) who requires academic accommodations should contact the Services for Students with Disabilities area of the Office of the Dean of Students at 471-6259 (voice) or 471-4641 (TTY for users who are deaf or hard of hearing) as soon as possible to request an official letter outlining authorized accommodations.
Last modified: November 26, 2014