CS395T Analysis of Boolean Functions
Spring 2023 Graduate Course

Prof. Anna Gal

TIME/PLACE: TTH: 12:30 - 2 pm, GDC 6.202
UNIQUE NUMBER: 52590

Course Description:

Boolean functions are among the most basic objects of study
in theoretical computer science, and they are also 
the fundamental objects underlying computer technology.
A Boolean function is simply a mapping between bit-strings,
and any such mapping can be implemented using simple
logical operations such as AND, OR and negation.
On the other hand, even the most complex computational
tasks can be expressed as Boolean functions.

This course is about the study of Boolean functions from a 
complexity theoretic perspective, with an emphasis 
on taking advantage of the Fourier representation of 
Boolean functions, expressing Boolean functions as polynomials.
The powerful techniques related to such representation have led to 
exciting results in various areas of theoretical computer science,
including circuit complexity, query complexity, pseudorandomness, 
learning theory, property testing and hardness of approximation.

BACKGROUND: The most important requirement is mathematical maturity,
with a solid understanding of discrete mathematics,
analysis of algorithms, basic combinatorics and probabilities.
No previous background in Fourier analysis is required for the class.

TEXTBOOK: We will rely on the excellent book 
"Analysis of Boolean functions" by Ryan O'Donnell,
but we will cover some additional material as well,
including recent research papers.

EVALUATION: There will be a few homework assignments and a course project,
which involves overview and presentation of a research paper or topic.