| Syllabus: | Syllabus |
| Professor: | David Zuckerman Email: diz@cs.utexas.edu Phone: 471-9729 Office: TAY 3.134 Office Hours: TTh 3:30-4:30 |
| TA: | Raghu Meka Email: raghu@cs.utexas.edu Phone: 471-9520 Office: TAY 3.108 Office Hour: M 3-4 |
| Useful Pointers: |
Last year's CS 353 P vs. NP poll List of many NP-complete problems Complexity of various games and puzzles Manuel Blum's lecture notes (pages 3 and 4) contain a counting argument showing the existence of functions with exponential circuit complexity. Note that he allows arbitrary gates on 2 inputs, whereas we allow only AND, OR, and NOT. Bit commitment overview Slides 3-5 of this talk summarize our discussion of digital signatures. Complexity Theory: A Modern Approach, a graduate-level text by Arora and Barak. Theory of Computing Blog Aggregator |
| Problem Sets: |
Problem Set #1
Solutions
Problem Set #2 Solutions Problem Set #3 Solutions Problem Set #4 Solutions Problem Set #5 Solutions Problem Set #6 Solutions Problem Set #7 Solutions Problem Set #8 Solutions |
| Exams: | The final exam will be held on Tuesday, May 13, from 2-5pm in UTC 3.110. No make-up exams will be given, so plan accordingly. You may bring a single, 8.5x11 inch, handwritten sheet of paper (you may use both sides). No calculators are allowed (they won't be necessary). |