Academics
  /  
Courses
  /  
Descriptions
COMP_SCI 396, 496: Analysis of Boolean Functions

Quarter Offered

Winter : 2-3:20 TuTh ; Rao

Prerequisites

COMP_SCI 212 or equivalent and linear algebra. COMP_SCI 335 or COMP_SCI 336 are strongly recommended.

Description

Boolean functions are functions that take in a string of 0's and 1's, and output a 0 or 1.
Thus in some sense computer science can be seen as a study of boolean functions.
In recent years, analytic tools, especially Fourier analysis, have seen many applications, including to social choice theory, pseudorandomness, and learning theory.
In this course, we'll both develop these analytic tools and investigate their applications.
This course will be taught using a flipped classroom model.

RECOMMENDED TEXTS: Analysis of Boolean Function by Ryan O'Donnell (http://www.contrib.andrew.cmu.edu/~ryanod/, https://www.amazon.com/Analysis-Boolean-Functions-Ryan-ODonnell/dp/1107038324)

Prerequisites: COMP_SCI 212 or equivalent and linear algebra.  COMP_SCI 335 or COMP_SCI 336 are strongly recommended.

INSTRUCTOR: Prof. Shravas Rao