642:587 Selected Topics in Discrete Mathematics: Analysis of Boolean Functions
Meeting Time/Place: Monday-Thursday 12:00-1:20 in Hill 525
Note: This replaces the originally announced topic, "Information Theoretic Methods in Theory of Computing and Discrete Mathematics"

Basic Course Information

Boolean functions are functions mapping {0,1}^n to {0,1}, Boolean functions provide a general framework for studying much of structural combinatorics such as hypergraphs, boolean relations, abstract simplicial complexes. Boolean functions can be viewed naturally from different mathematical viewpoints: combinatorial, algebraic, analytic and geometric, and these differing viewpoints provide a variety of techniques for studying them. Discrete fourier analysis is a key tool in this study. The mathematical theory of boolean functions focuses on various notions of variability and complexity including:

  • sensitivity, average sensitivty and influence are related measures of the extent to which the output of f is affeced by changing a single variable.
  • Controllability measures the extent to which a small subset of variables can control the value of the function.
  • noise stability of f measures the chance that the value of f changes if each variable is changed independently with a small probability
  • decision tree complexity measures the cost of evaluating f if each variable can be accessed at unit cost.
  • degree of f is the degree of the smallest n-variate real polynomial
  • certificate complexity which is the maximum over all inputs of the minimum number of variables that need to be revealed to determine the function value.


    While the focus of this course will be on this mathematical theory, we will also discuss applications within combinatorics (such as to the theory of random graphs), computer science (such as learning theory and hardness of approximation), and social choice theory. The course will be based on papers from the literature. Here is a preliminary bibliography. The course will also make use of notes for a similar course given at Carnegie-Mellon University by Ryan O'Donnell.

    There will be problem sets and no exams.

    Prerequisites: 642:582 (Combinatorics I) is adequate preparation for the course, though is not required. Others may take it with permission of the instructor. Students in computer science with a good background in theory of computing are generally encouraged to take the course but should talk to me to discuss whether they are mathematically prepared for the course.


    Written Assignments


    Please read and follow the guidelines for homework preparation

    Assignment Due Date Last revision pdf file latex file
    Assignment 1 Monday, October 10 October 5 pdf latex
    Assignment 2 Tuesday, November 22 November 20 pdf latex