15-855: An Introduction to Computational Complexity Theory

(Dates each problem set might be handed out and be due; these are subject to change)

PS1: Sep 10-24
PS2: Sep 24-Oct 8
PS3: Oct 8-22
Take Home Midterm: Oct 22-27 (no collaboration allowed)
PS4: Oct 27-Nov 10
PS5: Nov 10-24 (note: no lecture on Nov 24)
PS6: Dec 1-10.

The following is a tentative list of topics we might cover in the course. The list is ambitious, so depending on time we might skip some of the topics, and delegate some of them to homeworks.

1. Basic models and complexity classes (6 lectures)
    
   • Big questions, themes, and reminder of basic model/classes.
     
     
   • Hierachy theorems; Cook-Levin theorem.
     
     
   • Polynomial hierarchy($\text{PH}$); Introducing $\text{P/poly}$.
     • ${\text{QSAT}}_i$ is complete for ${\mathrm{\Sigma }}_i$
     • $\text{P}=\text{NP}\Rightarrow \text{P}=\text{PH}$
     • $\text{NP}\subseteq \text{P/poly}\Rightarrow \text{PH}={\mathrm{\Sigma }}_2$
       
       
   • Randomized complexity classes
     • Sipser-Gacs-Lautemann theorem: $\text{BPP}\subseteq {\mathrm{\Sigma }}_2\cap {\mathrm{\Pi }}_2$
     • Valiant-Vazirani theorem
       
       
   • Counting complexity
     • Permanent is $\text{\#P}$-complete
     • Toda's theorem: $\text{PH}\subseteq {\text{BPP}}^{\oplus \text{P}}\subseteq {\text{P}}^{\text{\#P}}$
       
       
   • Circuits and non-uniform complexity classes
     • Branching programs and formulae
     • Uniform circuit classes ${\text{NC}}^i$, ${\text{NC}}^1\subseteq \text{L}\subseteq \text{NL}\subseteq {\text{AC}}^1\subseteq {\text{NC}}^2$
     • Non-uniform ${\text{NC}}^1$ corresponds to poly-sized formulae
     • Barrington's theorem: Non-uniform ${\text{NC}}^1$ is the class of languages with constant-width poly-sized branching programs
       
       
   • Space complexity
     • $\text{NL}\subseteq \text{P}$
     • Savitch's theorem
     • $\text{ST-CONN}$(s,t-connectivity problem) is $\text{NL}$-complete
     • $\text{TQBF}$(True qualified boolean formula) is $\text{PSPACE}$-complete
     • Immerman-szelepcsenyi theorem: $\text{NL}=\text{coNL}$
       
       
2. Interactive proofs (2 lectures)
   
   
   • "Game-theoretic" view of class $\text{PH}$; $\text{AM}$ and $\text{MA}$
     • Interactive proof of $\text{GNI}$(Graph-Non-Isomorphism)
     • $\text{NP}\subseteq \text{MA},\text{AM}\subseteq {\mathrm{\Pi }}_2,\text{BPP}\subseteq \text{MA}$
     • A public coin protocol for $\text{GNI}$
     • Boppana-Hastad-Zachos theorem: $\text{coNP}\subseteq \text{AM}\Rightarrow \text{PH}=\text{AM}={\mathrm{\Pi }}_2$
       
       
   • $\text{IP}=\text{PSPACE}$
     • $\text{IP}\subseteq \text{PSPACE}$
     • $\text{\#SAT}\in \text{IP}\Rightarrow \text{PH}\subseteq \text{IP}$
     • $\text{TQBF}\in \text{IP}\Rightarrow \text{PSPACE}\subseteq \text{IP}$
       
       
3. Pseudorandomness (6 lectures)
   
   
   • Pseudorandom generators and "Hardness vs Randomness"
     • Definitions, and PRGs $\Rightarrow$ derandomization
     • Nisan-Widgerson generator: Average-case hardness $\Rightarrow$ PRGs
     • Coding theory: Worst-case hardness $\Rightarrow$ some average-case hardness
     • Hardness amplification: Some average-case hardness $\Rightarrow$ lots of average-case hardness
     • Punchline: Circuit lower bounds $\Rightarrow$ derandomization
       
       
   • Expanders
     • Definitions
     • Basic properties: Expander mixing lemma, Chernoff bound
     • Reingold's theorem: $\text{UPATH}\in \text{L}$
       
       
   • Extractors
     • Definitions and leftover hash lemma
     • Random walks on a expander $\Rightarrow$ extractor
     • Trevisan's extractor
     • Nisan's PRG for $\text{BPL}$
       
       
   • Connections
     • List-decodable codes, connections to extractors, expanders and PRGs
       
       
4. Circuit lower bounds (5 lectures)
   
   
   • Parity is not in ${\text{AC}}^0$; Polynomial approximation method

     •  Small circuits are approximable by low-degree polynomials; Fourier transform

     •  Razborov-Smolensky polynomial-based proof: any polynomial that agrees a lot with $\text{PARITY}$ has big degree.

     •  Hastad's switching lemma
       
       

   • Natural proofs
     
     
   • Circuit lower bounds via subexponential time algorithms

     •  If $\mathcal{C}$-SAT for a circuit class $\mathcal{C}$ can be solved with smallish circuits in subexponential time, then $\text{NEXP}⊈\mathcal{C}$

     • $\text{NEXP}⊈{\text{ACC}}^0$
       
       
5. Introduction of PCP theorem (1 lecture)
   
   
6. Communication complexity (6 lectures)
   
   
   • Warm-up: One-way communication complexity and streaming lower bounds
     • ${\text{DISJ}}_n$ needs $n$ communication for deterministic one-way protocols

     • Randomized (public coin) one-way protocols; Yao's minimax lemma.

     • Indexing; ${\text{DISJ}}_n$ needs $\mathrm{\Omega }(n)$ communication for randomized one-way protocols

     • Application: streaming lower bounds.
       
       

   • Many-round communication complexity: deterministic communication complexity

     • Lower bound strategies: Tilings, fooling sets, discrepancy, rank bounds

     • Examples: $\text{EQ}$, $\text{DISJ}$, $\text{IP}$ require at least $n$ bits of communication; In contrast to one-way, $\text{INDEX}$ needs only $O(\log n)$.

     • Log rank conjecture
       
       
   • Randomized communication complexity
     • Newman's Lemma; $R(\text{EQ})=O(\log n)$ and $R^{\text{pub}}(\text{EQ})=3$.
     • Discrepancy; $R^{\text{pub}}({\text{IP}}_n)=\mathrm{\Omega }(n)$.
     • Corruption;  $R^{\text{pub}}({\text{DISJ}}_n)=\mathrm{\Omega }(n)$.
       
       
   • Some special topics
     • Multiparty commnunication complexity
     • Information complexity
     • Non-deterministic communication complexity and extended formulations
     • Recent progress about the log rank conjecture