Section outline

  • Δευτέρα

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


      Πέμπτη

      • Circuit Lower Bounds: Håstad’s Switching Lemma and applications to lower bounds for parity, oracle worlds, computational learning and decision tree complexity. The polynomial approximation method.