Video feed

CSE104, Fall 2020: Computational Complexity

Subscribe:.rss.atom.json.md

Dormant Last read 1 day ago · last published 6 years ago · next check scheduled
Read 1 day ago and current, but nothing has been published for 6 years.

Latest videos

CSE104, Lec 16: Introduction to circuit complexity

Dec 2, 2020 · C. Seshadhri

▶Play

+Watch later

+Read later

CSE104, Lec 15: More on the polynomial hierarchy

Nov 26, 2020 · C. Seshadhri

▶Play

+Watch later

+Read later

CSE104, Lec 14: The polynomial hierarchy

Nov 24, 2020 · C. Seshadhri

▶Play

+Watch later

+Read later

CSE104, Lec 13: NL = co-NL, the Immerman-Szelepcsenyi theorem

Nov 20, 2020 · C. Seshadhri

▶Play

+Watch later

+Read later

CSE104, Lec 11: Logspace reductions and NL-completeness

Nov 18, 2020 · C. Seshadhri

▶Play

+Watch later

+Read later

CSE104, Lec 12: Read-once certificates for NL, starting NL=co-NL

Nov 18, 2020 · C. Seshadhri

▶Play

+Watch later

+Read later

CSE104, Lec 10: QBF is PSPACE-complete, the notion of logspace reductions

Nov 5, 2020 · C. Seshadhri

▶Play

+Watch later

+Read later

CSE104, Lec 9: Savitch's theorem, PSPACE = NPSPACE

Nov 4, 2020 · C. Seshadhri

▶Play

+Watch later

+Read later

CSE104, Lec 8: EXP vs NEXP and the time hierarchy theorem

Oct 29, 2020 · C. Seshadhri

▶Play

+Watch later

+Read later

CSE104, Lec 7: co-NP and the factoring problem

Oct 27, 2020 · C. Seshadhri

▶Play

+Watch later

+Read later

CSE104, Lec 5: The proof of the Cook-Levin theorem and the NP-completeness of 3SAT

Oct 20, 2020 · C. Seshadhri

▶Play

+Watch later

+Read later

CSE104: Lec 4, NP-completeness, the Cook-Levin Theorem

Oct 15, 2020 · C. Seshadhri

▶Play

+Watch later

+Read later

CSE104: Lec 3, the definitions of P and NP

Oct 13, 2020 · C. Seshadhri

▶Play

+Watch later

+Read later

CSE104, Lec 2: Turing machine simulations

Oct 8, 2020 · C. Seshadhri

▶Play

+Watch later

+Read later

CSE104, Computational Complexity: Lec 1, Cantor's diagonalization

Oct 6, 2020 · C. Seshadhri

▶Play

+Watch later

+Read later