CSC 2429F: Approaches to the P versus NP Question and Related Complexity Questions
Winter, 2014

Students should consult this page at least once a week for important information.

**Posted Jan 6** See link below for choosing your topic for a research presentation. Your topic choice is due by Jan 20.

Lectures: Wednesday 12-2 BA B026

Instructor: Toniann Pitassi
Office: Sandford Fleming 2305A, 978-3695
Office Hours: by appointment

Course Information Sheet

RESEARCH PRESENTATION

OUTLINE AND LECTURE NOTES

  • Lecture 1 (Jan 15)
    Introduction. The random restriction method. Superpolynomial lower bounds for Resolution proofs of PHP.
  • Lecture 2 (Jan 22)
    Hastad's Switching Lemma, exponential lower bounds for AC0 circuits for parity, and lower bounds on correlation.
  • Lecture 3 (Jan 29)
    Applications of AC0 lower bounds: Fourier concentration for AC0 and PAC learning of AC0 (over uniform distribution), Pseudorandom generators for AC0, AC0-SAT algorithm, Compression algorithm for AC0, Compression games for AC0, Bounded-depth Frege lower bounds.
  • Lecture 4 (Feb 5)
    Formula size lower bounds, and average-case formula size lower bounds.
  • Lecture 5 (Feb 12)
    Communication Complexity approaches to Circuit Lower Bounds.
  • Lecture 6 (Feb 26)
    (Guest Speaker: Stephen Cook) The Tree Evaluation Problem and Towards Separating P from NL.
  • Lecture 7, Part I (Mar 5)
    (Guest Speaker: Josh Grochow) Algebraic circuit complexity. Lower Bounds via connected components. Intro to Mulmuley's lower bound in Algebraic PRAM model without bit operations.
  • Lecture 7, Part II (Mar 5)
    (Guest Speaker: Josh Grochow) Continuation of Mulmuley's lower bound.
  • Lecture 8 (Mar 12)
    (Guest Speaker: Josh Grochow)
  • Lecture 9 (Mar 19)
    (Guest Speaker: Mika Goos) Matrix Rigidity and Communication Complexity.
  • Lecture 10 (Mar 26)
    (Guest Speaker: Robert Robere) ACC is not in NEXP (Ryan Williams' result)
  • Lecture 11 (Apr 2)
    (Guest Speaker: David Liu) Barriers: Natural Proofs and Algebrization
    LINKS TO PAPERS