Section outline

  • Δευτέρα 9 Δεκεμβρίου

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


    Πέμπτη 12 Δεκεμβρίου

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


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