Section outline

  • ΔΕΥΤΕΡΑ

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


    ΠΕΜΠΤΗ

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