Section outline

  • Δευτέρα

    • Non-Uniform Complexity: Boolean circuits, the class P/poly and related results, Turing Machines with advice, Karp-Lipton Theorem, Algorithms for Circuits, Parallel computation (classes NC, RNC, AC, TC).

    Πέμπτη

    • Non-Uniform Complexity review.
    • Circuit Lower Bounds: Boolean Functions, Circuit Lower Bounds, Kannan's Lower Bound.


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