# CSE 200, Computability and Complexity, Fall 2021

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, as understand why the "P vs NP" problem is possibly the most important open problem in computer science, mathematics and science at large.

## Information:

• Class Times: Mon,Wed 5-6:20pm, Warren West outside classroom
• Instructor: Shachar Lovett, email: slovett@ucsd.edu, office hours: Wed 3-4pm, CSE 4234
• TAs:
• Jessica Sorrell, email: jlsorrel@eng.ucsd.edu, office hours: Fri 3-4pm, CSE 4217
• Rex Lei, email: rlei@eng.ucsd.edu, office hours: Mon 10:30-11:30am, zoom
• Piazza: http://piazza.com/ucsd/fall2021/cse200, used for online forums, Q&A and announcements
• Zoom: the lectures are live streamed on zoom, meeting id 96005335436, password csexxx (replace xxx with class number, 3 digits)
• Podcast: the lectures are recorded and can be viewed on podcast, typically a day after the lecture

## Textbook:

Computational Complexity: A Modern Approach, Sanjeev Arora and Boaz Barak, 1st edition, 2009. Online version (draft)

## Topics:

1. Models of computation: Turing Machines and variants, RAM model, Boolean circuits. Simulating one machine model with another. The Church-Turing thesis and versions for efficient computation (Chapters 1, 3, and 6)
2. Universal machines and diagonalization: Undecidability. Recursive enumerability. The Halting Problem. Time and Space Hierarchy Theorems. Reductions. (Chapter 3).
3. NP-completeness and the P vs NP question. Consequences of P = NP. The polynomial-time hierarchy. (Chapters 2 and 5)
4. Space Complexity (Chapter 4)
5. Randomized computing (Chapter 7)
6. Time permitting: Interactive proofs (Chapter 8), Quantum computation (Chapter 10)

## Evaluation:

4 homework sets and a final project, each worth 20%. Each homework can be done individually or in pairs, and should be submitted within two weeks.
1. Homework 1. Due Mon Oct 18th, 11:59pm
2. Homework 2. Due Mon Nov 1st, 11:59pm
3. Homework 3. Due Wed Nov 17th, 11:59pm (deadline extended)
4. Homework 4. Due Wed Dec 1st, 11:59pm

## Final project:

The final project should be a survey on an area of your choice, explaining its relation to complexity theory and what we studied in class. It could be a high level survey of an area, or a technical survey of a specific theorem or result. The goal is really for you to learn something new, and understand how complexity theory is prevalent in many areas of CS. The survey should be approximately 6-10 pages.

Examples:
• Quantum complexity theory
• Applications of complexity theory to cryptography
• The PCP theorem and hardness of approximation
• Proofs that we skipped in class, such as a randomized O(log n) space algorithm for undirected connectivity

The deadline for the final project is somewhat flexible. There is a soft deadline of Dec 7th. Projects turned in by this date will be graded in time for final grades to be submitted by Dec 14th. Alternatively, if you are attempting a more involved project and would like additional time, you can submit a status update on Dec 7th instead. This update should include:
• Project description, including paper(s) selected for survey
• Current progress (e.g. number of pages written so far)
• Estimated number of hours until first draft is done
• Estimated date for completion of final draft
Conditioned on submitting a status update by Dec 7th, the hard deadline for the project is Dec 31st. Projects submitted by this date will be graded sometime during the first few weeks of winter quarter.

## Notes:

Notes might change through the quarter as we revise them (we will make a note of that).

## Tentative schedule:

• Introduction. Turing machines. Computable functions and robustness under different models.
• Universal Turing machines. Uncomputable functions. Definition of 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 AC0 (see Arora-Barak 14.1 for a different proof).
• Boolean circuits lower bounds: PARITY is not in AC0 (contd), 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).