CS 254: Computational Complexity

## General Information

Instructor:

CA: Emma Zhong (emmazjy@stanford.edu)

Classroom: Gates B12

Time: Mondays and Wednesdays, 4:30-5:50pm

Emma's OH: Tuesdays 1-3pm (Gates B26)

Li-Yang's OH: Fridays 4:15-6:15pm (Gates 466)

__Li-Yang Tan__(liyang@cs.stanford.edu)CA: Emma Zhong (emmazjy@stanford.edu)

Classroom: Gates B12

Time: Mondays and Wednesdays, 4:30-5:50pm

Emma's OH: Tuesdays 1-3pm (Gates B26)

Li-Yang's OH: Fridays 4:15-6:15pm (Gates 466)

## 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

...

## Schedule

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

- Jan 7: Course overview; the grand challenges of complexity theory
- Jan 9: CS154 recap
- Jan 14: Space complexity; Savitch's theorem
- Jan 16: Non-deterministic logspace; STCONN is NL-complete
__The complexity of graph connectivity__, Avi Wigderson

__Undirected connectivity in log-space__, Omer Reingold - Jan 23: Immerman-Szelepcsényi theorem
- Jan 28: NP, coNP, and NP ∩ coNP
Chapters
__3.5__and__6__of Wigderson's book

__Gödel's 1956 letter to von Neumann__

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

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

- Jan 30: The polynomial hierarchy
- Feb 4: P
^{SAT}and oracle Turing machines - Feb 6: The power of randomness in computation
__Chapter 7__of Wigderson's book

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

__Pseudorandomness__, monograph by Salil Vadhan - Feb 11: Randomized complexity. P versus BPP; NP versus BPP
- Feb 13: A glimpse of hardness vs randomness and explicit construction of Ramsey graphs
__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 20: Non-uniform computation and circuit complexity
__Chapter 5__of Wigderson's book

__P =? NP__, Scott Aaronson

__Some estimated likelihoods for computational complexity__, Ryan Williams

- Feb 25: Relating P/poly to BPP and NP: Adelman's theorem and the Karp-Lipton theorem
- Feb 27: Interactive proofs
__Chapter 10__of Wigderson's book

__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 4: Interative proof for #3SAT
- March 6: Arthur and Merlin
- March 11: Goldwasser-Sipser AM protocol for approximate counting
- March 13: Unique-SAT and the Valiant-Vazirani theorem

## Evaluation

• 4 problem sets (70%)

• Course project (30%)

☐ Interim progress report (5%)

☐ Final written report (15%)

☐ Your peer evaluation report (10%)

• In-class participation (+5%)

In-class discussions will be an important component of this course, and hence attendance will be expected.• Course project (30%)

☐ Interim progress report (5%)

☐ Final written report (15%)

☐ Your peer evaluation report (10%)

• In-class participation (+5%)

Problem set policies:

• 4 late days, at most 2 per pset

• Regrade requests must be submitted within 1 week

• Regrade requests must be submitted within 1 week

## A few project reports

The natural proofs barrier and P =? NP

On the computational intractability of cryptographic systems

Undirected connectivity is in L: an overview of the proof

Formal barriers to proving P ≠ NP: relativization and natural proofs

Fractional pseudorandom generators

Quantum computation and complexity

Pseudorandomness: applications to cryptography and derandomization

Derandomization from hardness

Hardness vs. randomness

Hitting set generators: a different lens into P vs. BPP

The oracle separation of BQP and PH

Computational complexity and philosophy

On the computational intractability of cryptographic systems

Undirected connectivity is in L: an overview of the proof

Formal barriers to proving P ≠ NP: relativization and natural proofs

Fractional pseudorandom generators

Quantum computation and complexity

Pseudorandomness: applications to cryptography and derandomization

Derandomization from hardness

Hardness vs. randomness

Hitting set generators: a different lens into P vs. BPP

The oracle separation of BQP and PH

Computational complexity and philosophy