CSE204, Lec 19: Basic of cryptography, from a complexity perspectiveJun 3, 2022 · C. Seshadhri▶Play+Watch later+Read later
CSE204, Lec 17: Proving the Sumcheck protocol for #SAT, a short discussion about MIPMay 31, 2022 · C. Seshadhri▶Play+Watch later+Read later
CSE204, Lec 18: The PCP theorem and hardness of approximationMay 30, 2022 · C. Seshadhri▶Play+Watch later+Read later
CSE204, Lec 16: Proving the set lower bound protocol, and starting the proof that IP = PSPACEMay 20, 2022 · C. Seshadhri▶Play+Watch later+Read later
CSE204, Lec 15: Arthur-Merlin protocols and the Goldwasser-Sipser set lower bound protocolMay 18, 2022 · C. Seshadhri▶Play+Watch later+Read later
CSE204, Lec 13: Relating BPP to other complexity classesMay 13, 2022 · C. Seshadhri▶Play+Watch later+Read later
CSE2014, Lec 12: Introduction to randomized complexity classes and BPPMay 13, 2022 · C. Seshadhri▶Play+Watch later+Read later
CSE204, Lec 14: Introduction to Interactive ProtocolsMay 13, 2022 · C. Seshadhri▶Play+Watch later+Read later
CSE 204, Lec 10, Part 1: Complete languages for the polynomial hierarchyApr 30, 2022 · C. Seshadhri▶Play+Watch later+Read later
CSE204, Lec 10, Part 2: Introduction to circuit complexityApr 30, 2022 · C. Seshadhri▶Play+Watch later+Read later
CSE204, Lec 9: Equivalences of definitions of the polynomial hierarchyApr 27, 2022 · C. Seshadhri▶Play+Watch later+Read later
CSE204, Lec 3: 3SAT is NP-complete, and the class co-NPApr 6, 2022 · C. Seshadhri▶Play+Watch later+Read later
CSE204, Lec 2: NP-completeness and the Cook-Levin TheoremApr 1, 2022 · C. Seshadhri▶Play+Watch later+Read later
