EdusalsaDiscover Your Stanford

CS 252

Analysis of Boolean Functions

  • autumn
  • 2018-2019

3 units

Letter or Credit/No Credit

Boolean functions are among the most basic objects of study in theoretical computer science. This course is about the study of boolean functions from a complexity-theoretic perspective, with an emphasis on analytic methods. We will cover fundamental concepts and techniques in this area, including influence and noise sensitivity, polynomial approximation, hypercontractivity, probabilistic invariance principles, and Gaussian analysis. We will see connections to various areas of theoretical computer science, including circuit complexity, pseudorandomness, classical and quantum query complexity, learning theory, and property testing. Prerequisites: CS 103 and CS 109 or equivalents. CS 154 and CS 161 recommended.

Course Prequisites

Sections

autumn
  • LEC

    • Monday Wednesday 4:30:00 PM - 5:50:00 PM @ Hewlett Teaching Center 103 with Li-Yang Tan

Sign Up

To save CS 252 to your course bucketlist

Already Have An Account? Log In