On 17.04.2014 at 12:20 in S6, there is the following noon lecture:
Fourier analysis and the minimal degree of polynomials for Boolean functions
Ronald de Wolf
CWI and University of Amsterdam
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.
Webmaster: kamweb.mff.cuni.cz Modified: 25. 02. 2019