• Syllabus

Print View

Lecture 01Tue Nov 02, 2021 10:00 AM -  | 12:00 PM

  • administrative issues
  • introduction
    • goals and motivation of complexity theory
    • examples of interesting computational problems

Lecture 02Thu Nov 04, 2021 10:00 AM -  | 12:00 PM

  • computational model:
    • multi-tape Turing machine
    • facts from computability: undecidability, Church-Turing thesis, encoding of TMs, universal TM
  • complexity measures: time and space
  • linear speedup theorem

Lecture 03Tue Nov 09, 2021 10:00 AM -  | 12:00 PM

  • Linear Speedup Theorem
  • Time- and space-constructible functions
  • Time Hierarchy Theorem

Lecture 04Thu Nov 11, 2021 10:00 AM -  | 12:00 PM

  • time-hierarchy theorem (continued)
  • gap theorem (without proof)
  • some notable complexity classes: P, E, EXP, L, PSPACE
  • non-determinism
  • non-deterministic time-hierarchy theorem (without proof)
  • more notable complexity classes: NP, NE, NEXP, NL, NPSPACE

Lecture 05Tue Nov 16, 2021 10:00 AM -  | 12:00 PM

  • basic relationships between time and space complexity classes
  • the complexity class NP: definition and basic notions
  • Ladner's theorem: existence of NP-intermediate problems

Lecture 06Thu Nov 18, 2021 10:00 AM -  | 12:00 PM

  • proof of Ladner's theorem

Lecture 07Tue Nov 23, 2021 10:00 AM -  | 12:00 PM

  • proof of Ladner's theorem (conclusion)
  • coNP: definition and properties
  • NP intersect coNP

Lecture 08Thu Nov 25, 2021 10:00 AM -  | 12:00 PM

  • the complexity class DP
  • oracle Turing Machines
  • the relativization barrier by Baker-Gill-Solovay
  • there exists an oracle such that P != NP

Lecture 09Tue Nov 30, 2021 10:00 AM -  | 12:00 PM

  • Theorem of Baker-Gill-Solovay: Proof

Lecture 10Thu Dec 02, 2021 10:00 AM -  | 12:00 PM

  • Space Complexity
  • Configuration Graphs
  • Savitch's theorem
  • PSPACE = NPSCAPE
  • log-space reductions
  • NL-completeness

Lecture 11Tue Dec 07, 2021 10:00 AM -  | 12:00 PM

  • stPath is NL-complete
  • coNL
  • NL=coNL

Lecture 12Thu Dec 09, 2021 10:00 AM -  | 12:00 PM

  • NL=coNL: proof
  • PSPACE-completeness
  • TQBF

Lecture 13Tue Dec 14, 2021 10:00 AM -  | 12:00 PM

  • TQBF is PSPACE-complete

Lecture 14Thu Dec 16, 2021 10:00 AM -  | 12:00 PM

  • PSPACE and games
  • The polynomial hierarchy: motivation, definition, and first properties

Lecture 15Tue Jan 04, 2022 10:00 AM -  | 12:00 PM

  • Properties of PH, hierarchy collapse

Lecture 16Thu Jan 06, 2022 10:00 AM -  | 12:00 PM

  • alternative characterizations of PH: alternation, complexity class operators, complete problems, oracle definition

Lecture 17Tue Jan 11, 2022 10:00 AM -  | 12:00 PM

  • circuits: definitions and first properties

Lecture 18Thu Jan 13, 2022 10:00 AM -  | 12:00 PM

  • uniform circuit families
  • advice Turing Machines
  • the Karp-Lipton Theorem

Lecture 19Tue Jan 18, 2022 10:00 AM -  | 12:00 PM

  • circuit lower bounds
  • circuit hierarchy theorem: a general proof can be found here.
  • attempts of proving circuit lower bounds for NP-hard problems

Lecture 20Thu Jan 20, 2022 10:00 AM -  | 12:00 PM

  • more on circuit lower bounds 
  • the natural proof barrier
  • randomization

Lecture 21Tue Jan 25, 2022 10:00 AM -  | 12:00 PM

  • polynomial identity testing

Lecture 22Thu Jan 27, 2022 10:00 AM -  | 12:00 PM

  • polynomial identity testing
  • probabilistic Turing machines
  • RP, coRP, ZPP, and their properties

Lecture 23Tue Feb 01, 2022 10:00 AM -  | 12:00 PM

  • The complexity class BPP, definition and properties

Lecture 24Thu Feb 03, 2022 10:00 AM - Thu Feb 10, 2022 12:00 PM  | 

  • Chernoff bounds
  • BPP is in P/Poly (Adleman's theorem)
  • BPP is in the second level of PH (Sipser-Gacs-Lauteman theorem)

Lecture 25Tue Feb 08, 2022 10:00 AM -  | 12:00 PM

  • interactive proofs
  • the complexity class dIP
  • dIP = NP
  • the complexity classes IP[k] and IP
  • example of an interactive proof 

Lecture 26Thu Feb 10, 2022 10:00 AM -  | 12:00 PM

  • first properties of IP
  • serial repetition
  • GNI is in IP

Lecture 27Tue Feb 15, 2022 10:00 AM -  | 12:00 PM

  • GNI is in IP
  • public coin versus private coin
  • definition of AM
  • GNI is in AM: turning GNI into a counting problem

Lecture 28Thu Feb 17, 2022 10:00 AM -  | 12:00 PM

  • Goldwasser-Sipser set lowerbound protocol: estimating set sizes by random sampling

Lecture 29Tue Mar 01, 2022 10:00 AM -  | 12:00 PM

  • Goldwasser-Sipser Set lower bound protocol: use of pairwise independent hashing
  • #3SAT is in IP

Lecture 30Thu Mar 03, 2022 10:00 AM - Wed Mar 09, 2022 12:00 PM  | 

  • #3SAT is in IP: polynomial method
  • TQBF is in IP: IP = PSPACE

Lecture 31Thu Mar 10, 2022 10:00 AM -  | 12:00 PM

  • the PCP theorem