| Logistics: | MW 2:00 - 3:30 GDC 6.202 Unique Number: 51370 Course web page: http://www.cs.utexas.edu/~diz/388T |
||||||||||||||||||||||||||
| Professor: | David Zuckerman Email: diz@cs.utexas.edu Office: GDC 4.508 Phone: 471-9729 Office Hours: T 2-3, Th 3:30-4:30. | ||||||||||||||||||||||||||
| TA: | Fu Li
Email: fuli.theory.research@gmail.com Office (for office hours): GDC 1.302, Desk 1 Office (for all other purposes): GDC 4.504D Office Hours: M 4-5, F 3:30-4:30. |
||||||||||||||||||||||||||
| Required Text: | Arora and Barak, Computational Complexity: A Modern Approach | ||||||||||||||||||||||||||
| Content: |
This graduate course is an introduction to computational complexity.
Computational complexity studies the limits and capabilities of efficient
computation, as well as tradeoffs between different computational resources.
The NP vs. P question is the central question in the area, and we
assume exposure to this at the undergraduate level.
We explore a variety of other fascinating issues, including for example the
surprising equivalence of probabilistically checkable proofs (PCPs) and
the hardness of approximating certain optimization problems.
This course assumes some knowledge of time and space complexity;
see the prerequisites.
A list of tentative topics follows.
|
||||||||||||||||||||||||||
| Prerequisites: | CS 353 or a basic undergraduate course covering complexity theory. In particular, I will assume knowledge of time and space complexity at the level of Chapters 7 and 8 of Sipser's text, or Chapters 1, 2, and 4 of the Arora-Barak text. In addition, I will assume some mathematical sophistication. | ||||||||||||||||||||||||||
| Grading: | 40%: Homework 50%: Final exam 10%: Participation |
||||||||||||||||||||||||||
| Final Exam: | The final exam will be cumulative and held on Wednesday, May 11 from 2-5pm. 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). | ||||||||||||||||||||||||||
| Homework: |
Most weeks a problem set will be assigned.
Collaboration policy: While you should first think about the problems on your own, you are encouraged to discuss the problems with your classmates. Please limit your collaborations on any particular homework to at most three other students. You must write up your own solutions. In particular, nobody should email partial or full solutions to anybody. You must acknowledge any collaboration by writing your collaborators' names on the front page of the assignment. You don't lose points by having collaborators. Citation policy: Try to solve the problems without reading any published literature or websites, besides the class text and links off of the class web page. If, however, you do use a solution or part of a solution that you found in the literature or on the web, you must cite it. Furthermore, you must write up the solution in your own words. You will get at most half credit for solutions found in the literature or on the web. Submission policy: Homeworks are due at the beginning of class. No late homeworks will be accepted. | ||||||||||||||||||||||||||
| Participation and Attendance: | Your participation grade is based on the quality and quantity of your participation. While attendance is not required, poor attendance will be reflected in your participation grade. | ||||||||||||||||||||||||||
| Laptops/Phones: | The use of laptops and mobile devices is generally prohibited; however, I will allow use of tablets if you sit in the first row and use them only for class-related purposes. Other exceptions may be made in unusual circumstances. All phones must be silenced. | ||||||||||||||||||||||||||
| 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. |