CSE 531: Computational Complexity I, Winter 2016

CSE Home

CSE 531 Home

About Us

Search

Contact Info

Email   Archive  Homework Assignments   Assignment 1   Assignment 2   Assignment 3 Readings   Chapter 1   Turing and Post on TMs   Chapter 2   Chapter 3   Section 6.5   Chapter 4   Chapter 5   Chapter 6   Chapter 7   Chapter 17   Chapter 13   Chapter 8 Administrative

Location Wednesdays 10-11:20 and Fridays 10:30-11:50    Mary Gates 254. Note that class will start a half hour earlier on Wednesdays than on Fridays. Instructor Paul Beame Office: CSE 668 Phone 206-543-5114 Office Hours: Mondays 2:30-3:20. Wednesdays 1:30-2:20 (not Feb 3, 17). Feel free to stop by whenever I am in my office and not in another meeting. Teaching Assistant Vincent Liew Office Hours: Tuesdays 2:30-320, Thursdays 1:30-2:20 Lectures Lecture 1: Jan 6 Course outline, Turing machine complexity, efficient universal TM Lecture 2: Jan 8 Circuit complexity, connections to Turing machines, NP Lecture 3: Jan 13 Nondeterminism and NP-completeness,Cook-Levin Theorem Lecture 4: Jan 15 More NP-completeness, NPsearch, coNP Lecture 5: Jan 20 Circuit Lower Bounds, Time Hierarchy Theorems Lecture 6: Jan 22 Oracle TMs and the Limitations of Diagonalization, Space Complexity Lecture 7: Jan 27 Space Hierarchy, PSPACE-completeness, Savitch's Theorem Lecture 8: Jan 29 L, NL, NL-completeness,NSPACE closed under complement Lecture 9: Feb 3 Polynomial-Time Hierarchy, Time-Space Tradeoffs for SAT Lecture 10: Feb 8 Circuit Complexity and the Polynomial-Time Hierarchy Lecture 11: Feb 10 Randomization and Complexity I Lecture 12: Feb 12 Randomization and Complexity II Lecture 13: Feb 17 #P and Counting Lecture 14: Feb 19 #P-complete and Approximation Lecture 15: Feb 29 Unique-SAT, Toda's Theorem, and Circuit Lower Bounds Lecture 16: Mar 2 Communication Complexity Lecture 17: Mar 4 SETH and Complexity within Polynomial Time Lecture 18: Mar 7 Interactive Proofs Textbook Much of the material in the course will be from Computational Complexity: A Modern Approach. by Sanjeev Arora and Boaz Barak, though there is much more material than we will be able to cover and there will be some new topics not covered in the text. An online pre-publication draft from 2007 is also available. Mailing List Course annoucements will be made on the class mailing list, cse531a_wi16. Grading Homework 50%, a take-home midterm 15-20%, in-class open-book final exam 30-35%, Extra Credit. Make-up classes There will be no class on Friday, Feb 5. Instead, the class will be on Monday, Feb 8, 1:30-2:50 pm in room CSE 503. There also will be no classes the week of Feb 22 and a make-up class on Monday, Feb 29, 1:30-2:50 on in room CSE 503. Final exam As agreed on via the class survey, the in-class final exam will be on Monday, March 14, 2016 at 2:30-4:20. At the moment I have CSE 303 reserved for this. It might be possible to use CSE 403 instead, if that is preferred. Portions of the CSE 531 Web may be reprinted or adapted for academic nonprofit purposes, providing the source is accurately quoted and duly credited. The CSE 531 Web: © 1993-2016, Department of Computer Science and Engineering, University of Washington.