Section outline

  • ΔΕΥΤΕΡΑ

    • Interactive Proofs: Shamir's Theorem (IP=PSPACE), Probabilistically Checkable Proofs, The Class PCP[r(n),q(n)].



    ΠΕΜΠΤΗ

    • Derandomization of Complexity Classes: Pseudorandom Generators, the Nisan-Wigderson Construction, Derandomization vs. Circuit Lower Bounds, The Easy Witness Lemma,
      Satisfiability vs Circuit Lower Bounds.



    Μπορείτε να διαβάσετε:
    -Sections 8.3, 8.4 from [2]
    - Chapter 20 from [2]