CS 254: Computational Complexity

## General Information

Instructor:

CAs: Tom Knowles (tknowles@stanford.edu)

Can Liu (canliu@stanford.edu)

Time: Mondays and Wednesdays, 4:00-5:20pm

Tom's OH: Saturdays 12-1pm

Can's OH: Tuesdays 7-9pm

Homework parties: Mondays 6-8pm

__Li-Yang Tan__(liyang@cs.stanford.edu)CAs: Tom Knowles (tknowles@stanford.edu)

Can Liu (canliu@stanford.edu)

Time: Mondays and Wednesdays, 4:00-5:20pm

Tom's OH: Saturdays 12-1pm

Can's OH: Tuesdays 7-9pm

Homework parties: Mondays 6-8pm

## Textbooks

__Computational Complexity: A Modern Approach__, by Sanjeev Arora and Boaz Barak.

__Mathematics and Computation__, by Avi Wigderson.

## List of Topics

- Space Complexity
ST-connectivity and its role in space complexity

Non-determinism in space complexity: Savitch's theorem

NL = coNL: Immerman-Szelepcsényi theorem

- Polynomial Hierarchy
P, NP, coNP, and friends

NP ∩ coNP ≈ having a good characterization

Efficient computation in a world where P = NP - Randomized Complexity
Randomness as a resource. Does P = BPP?

Randomness versus non-determinism

Unique-SAT: Valiant-Vazirani theorem - Non-Uniform Computation
Circuit complexity

Randomness versus non-uniformity: Adelman's theorem

Small circuits for NP? Karp-Lipton theorem

- Interactive Proofs
Arthur and Merlin, and generalizations of NP

Approximate counting: Goldwasser-Sipser theorem

IP = PSPACE - If time permits:
Beyond worst-case complexity

Hardness within P

Circuit lower bounds

Hardness versus randomness

Barriers to P versus NP

...

## Lecture schedule

(Will be updated as the quarter progresses. Supplementary material listed in gray.)

- Jan 11: Course overview; the grand challenges of complexity theory
- Jan 13: CS154 recap
- Jan 20: Space complexity; Savitchâ€™s theorem (AB §4.1-4.3)
- Jan 25: Nondeterministic space and NL-completeness of STCONN (AB §4.4)
__The complexity of graph connectivity__, Avi Wigderson

__Undirected connectivity in log-space__, Omer Reingold - Jan 27: Immerman-Szelepcsényi theorem (AB §4.4)
- Feb 1: NP, coNP, and NP ∩ coNP (AB §2.6-2.7)
Chapter
__3.5__of Wigderson's book: The class coNP, the NP versus coNP question, and efficient characterization

Chapter__6__of Wigderson's book: Proof complexity

__Propositional proof complexity: past, present, and future__, Paul Beame and Toniann Pitassi

__The limits of proof__, video of a talk by Paul Beame

__Proof complexity 2020__, video of a talk by Paul Beame

- Feb 3: The polynomial hierarchy (AB §5)
__Completeness in the polynomial-time hierarchy__, Marcus Schaefer and Chris Umans - Feb 8: P
^{SAT}and oracle Turing machines (AB §5) - Feb 10: The power of randomness in computation (AB §7)
__Chapter 7__of Wigderson's book: Randomness in computation

__Finding hay in haystacks: the power and limits of randomness__, video of a talk by Avi Wigderson

__Pseudorandomness__, monograph by Salil Vadhan - Feb 17: Randomized complexity. P versus BPP; NP versus BPP (AB §7)
__Pure randomness extracted from two poor sources__, Don Monroe

__How random is your randomness, and why does it matter__, Eshan Chattopadhyay and David Zuckerman

__Research Vignette: Ramsey graphs and the error of explicit 2-source extractors__, Amnon Ta-Shma

- Feb 22: Non-uniform computation and circuit complexity (AB §6)
__Chapter 5__of Wigderson's book: Lower bounds, boolean circuits, and attacks on P vs. NP

__P =? NP__, Scott Aaronson

__Some estimated likelihoods for computational complexity__, Ryan Williams

- Feb 24: Relating P/poly to BPP and NP: Adelman's theorem and the Karp-Lipton theorem (AB §6)
- March 1: Interactive proofs (AB §8)
__Chapter 10__of Wigderson's book: Randomness in proofs

__Proofs, Knowledge, and Computation__, video of a talk by Silvio Micali

__A history of the PCP theorem__, Ryan O'Donnell

__E-mail and the unexpected power of interaction__, László Babai

__1993 Gödel prize citation__, for Babai-Moran and Goldwasser-Micali-Rackoff - March 3: Interactive proof for #3SAT (AB §8)

## Evaluation

• 4 problem sets (70%, weighted by total score per set)

• Course project (30%)

☐ Interim progress report (5%)

☐ Final written report (15%)

☐ Your peer evaluation report (10%)

• CR: ≥ 70% on 2 psets or ≥ 70% on Course project

Problem set policies:
• Course project (30%)

☐ Interim progress report (5%)

☐ Final written report (15%)

☐ Your peer evaluation report (10%)

• CR: ≥ 70% on 2 psets or ≥ 70% on Course project

• 4 late days, at most 2 per pset

• Late days can only be used for psets, not the project

• Regrade requests must be submitted within 1 week

• Late days can only be used for psets, not the project

• Regrade requests must be submitted within 1 week

## Coursework schedule

(Tentative; subject to change.)

• Pset 1: Jan 27

• Pset 2: Feb 10

• Pset 3: Feb 24

• Pset 4: Mar 8

• Course project

☐ Decide on project topic: Feb 17

☐ Interim progress report: Mar 3

☐ Final written report: Mar 15

☐ Your peer evaluation report: Mar 19

• Pset 2: Feb 10

• Pset 3: Feb 24

• Pset 4: Mar 8

• Course project

☐ Decide on project topic: Feb 17

☐ Interim progress report: Mar 3

☐ Final written report: Mar 15

☐ Your peer evaluation report: Mar 19