Section outline

  • 11) Δευτέρα 10 Νοεμβρίου

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

     

    12) Πέμπτη 13 Νοεμβρίου

    • Non-Uniform Complexity: Lower bounds for AC0: Random restrictions, Håstad's Switching Lemma and applications. Lower bounds from algorithms (NEXP vs ACC0).

    The Switching Lemma (Ryan O' Donnell)
     
    • Μπορείτε να διαβάσετε:
      • Sections 14.1-14.2 from [2]