Computability and Complexity
CSE 200 - Fall 2023

Place and Time:	DIB 121, TTh 11:00am-12:20pm
Instructor:	Daniel Grier (dgrier@ucsd.edu)
TA:	Anthony Ostuni (aostuni@ucsd.edu)
Resources:	Canvas, Gradescope, Piazza
Daniel's office hours:	Thursday 1pm-2pm and by appointment in CSE 4218
Anthony's office hours:	Tuesday 1pm-2pm, Friday 11am-11:55am outside CSE 4232

• Homework 1 - due October 18th at 11:59pm
• Homework 2 - due November 1st at 11:59pm
• Homework 3 - due November 15th at 11:59pm
• Homework 4 - due November 29th at 11:59pm
• Project - due December 8th at 11:59pm

This class is an introduction to computational complexity theory. This area aims to understand the various resources needed to solve computational problems. Such resources include the obvious ones, such as time and memory, but also possibly less obvious ones, such as randomization, interaction and non-uniformity. In addition, we will attempt to classify problems as "easy" or "hard", study relations between easy and hard problems, and understand why the "P vs NP" problem is possibly the most important open problem in computer science, mathematics and science at large.

Textbook: Computational Complexity: A Modern Approach, Sanjeev Arora and Boaz Barak
Prerequisites: Undergraduate exposure to algorithms and their analysis, boolean logic, formal language and automata theory, and, most importantly, the ability to read, recognize, and write a valid proof. If you have done well in CSE 105 (Theory of Computation), CSE 101 (Design and Analysis of Algorithms), and CSE 20 (Discrete Mathematics), or equivalent, you should have the necessary background for this course.

• Turing machines. Computable functions and robustness under different models.
• Universal TMs. Uncomputable functions. Time complexity. (Arora-Barak 1.4-1.6).
• Time and space complexity and hierarchy theorems. (Arora-Barak 3.1 and 4.1).
• NP and NP-completeness. (Arora-Barak 2.1-2.2, 2.5).
• NP-completeness: Cook-Levin theorem. (Arora-Barak 2.3).
• Beyond NP: the Polynomial Hierarchy. (Arora-Barak 2.6, 5.1-5.2).
• Space complexity: Logspace computation. NL completeness. (Arora-Barak 4.1).
• Space complexity: PSPACE completeness. Savitch theorem. (Arora-Barak 4.2-4.3).
• Space complexity: NL=coNL. Boolean circuits. (Arora-Barak 4.3, 6.1-6.2).
• Boolean circuits: Karp-Lipton, Meyer theorems. (Arora-Barak 6.3-6.5).
• Boolean circuits lower bounds: PARITY is not in AC^0 (Arora-Barak 14.1).
• Natural proofs (Arora-Barak 23).
• Randomness in computation (Arora-Barak 7.1).
• Randomness in computation (Arora-Barak 7.2-7.4).
• Randomness in computation (Arora-Barak 7.5).
• Interactive proofs (Arora-Barak 8.1-8.2).

1. Computational models
2. Time and space hierarchies
3. NP and NP completeness
4. Nondeterminism
5. Space complexity
6. Boolean circuits
7. Randomized algorithms
8. Circuit lower bounds
9. Interactive proofs

• Homework (70%): There will be 4 graded homework assignments throughout the course. Can be completed individually or in pairs.
• Project (20%): The final project will be a survey or original research on a topic in complexity theory and/or computability. Completed individually or in pairs. Due at end of quarter.
• Quizzes (10%): Weekly in-person quizzes. Graded for effort, but not correctness.

• Complexity Zoo Largest unified collection of complexity classes and their relationships
• Introduction to the Theory of Computation Sipser's canonical intro textbook. Used in CSE 105.

Students requesting accommodations for this course due to a disability must provide a current Authorization for Accommodation (AFA) letter issued by the Office for Students with Disabilities. Students are required to discuss accommodation arrangements with instructors and OSD liaisons in the department in advance of any exams or assignments.