Section outline

  • 14) Δευτέρα 24 Νοεμβρίου

    • Interactive Proofs: Deterministic verifiers, probabilistic verifiers and the class IP, public and private coins, Arthur-Merlin Games, the class AM and its properties

    15) Πέμπτη 27 Νοεμβρίου

    • Interactive Proofs: Shamir's Theorem (IP=PSPACE), Probabilistically Checkable Proofs, The Class PCP[r(n),q(n)].
    • Derandomization of Complexity Classes: The general derandomization paradigm, Pseudorandom Generators.

    Μπορείτε να διαβάσετε:
    • Sections 8.1-8.4 from [2]
    • Section 20.1, 20.2 from [2]