Section outline

  • Δευτέρα 27 Νοεμβρίου

    • Non-Uniform Complexity: Lower bounds for ACC0, lower bounds from algorithms (NEXP vs ACC0), Algorithms from lower bounds techniques. Monotone functions and circuit lower bounds. Natural proofs: the Circuit Complexity Barrier.


    Πέμπτη 30 Νοεμβρίου

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

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