Section outline

  • ΔΕΥΤΕΡΑ

    • Non-Uniform Complexity: Circuit Lower Bounds, Natural Proofs

     

    ΠΕΜΠΤΗ

    • Interactive Proofs: Deterministic verifiers, probabilistic verifiers and the class IP, Public and private coins, Arthur-Merlin Games

     

    Προτεινόμενη Μελέτη:

    • Ch 6: Sections 6.1-6.5 από το [2]
    • Ch 8: Section 8.1, 8.2 από το [2]