Section outline

  • ΔΕΥΤΕΡΑ

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

     

    ΠΕΜΠΤΗ

    • Interactive Proofs: The PCP Theorem ( NP=PCP[logn,1] ), Dinur's Proof (guest lecture by M. Zampetakis)