|Syllabus:||syllabus in pdf|
Office: GDC 4.508
Office Hours: Tu 3:30-4:15 and W 2:30-3:15.
Office Hours: Th 4-5 in GDC 1.302, Desk 4.
|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.|
Theory of Computing Blog Aggregator
P vs. NP page
List of many NP-complete problems
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
Complexity Theory: A Modern Approach, a graduate-level text by Arora and Barak.