Complexity Measures of Boolean Functions

Boolean functions are central to computer science. This presentation will focus on Boolean functions from the perspective of certain measures of complexity.

In the first part of the presentation, our focus will be two Fourier analytic complexity measures of Boolean functions: Fourier sparsity and Fourier dimension. We will present a near-optimal upper bound of Fourier dimension of Boolean functions in terms of Fourier sparsity.

The second part will concentrate on different query complexity measures of Boolean functions: deterministic, randomized zero-error and randomized bounded-error, and relationships amongst them. We will see explicit constructions of functions for which these measures are polynomially separated, and more widely than was known before our work.

We present a lower bound on the PTF-sparsity of the Inner product mod 2 function that is better than the previously known bound by a factor of 5/2.

Finally, we present an optimal hypercontractive inequality for Fourier-sparse real-valued functions on the Boolean hypercube.