Section outline

  • ΔΕΥΤΕΡΑ

    • Circuit Lower Bounds: Håstad’s Switching Lemma and applications to lower bounds for parity, oracle worlds and computational learning.



    ΠΕΜΠΤΗ

    • Circuit Lower Bounds: Counting Circuits (ACC) and lower bounds, non-uniform lower bound for NEXP, Natural Proofs.


    Μπορείτε να διαβάσετε:
    - Chapter 14 from [2]