Department of
Applied
Mathematics

Fourier analysis and the minimal degree of polynomials for Boolean functions

Ronald de Wolf

CWI and University of Amsterdam

Abstract

Fourier analysis on the Boolean cube (a.k.a. the analysis of Boolean functions) has become a very prominent tool in theoretical computer science over the last decades. This talk will start by giving a brief introduction to these techniques, as well as some applications. It will then focus on the minimal Fourier degree that's needed to represent or approximate Boolean functions. Our main result is a lower bound of Omega(log(n) / loglog(n)) on the degree needed for approximating any Boolean function that depends on n variables. We also use tools from quantum algorithms to design specific Boolean functions where this lower bound is tight. This is joint work with Andris Ambainis which appeared in CCC'13.