Caltech Logo

Caltech/UCLA Joint Analysis Seminar

Tuesday, April 20, 2021
10:00am to 10:50am
Add to Cal
Online Event
The mysteries of low-degree Boolean functions
Nathan Keller, Department of Mathematics, Bar Ilan University,


Analysis of Boolean functions studies functions on the discrete cube {-1,1}n, aiming at understanding what the structure of the (discrete) Fourier transform tells us about the function. In this talk we focus on the structure of low-degree functions on the discrete cube, namely, on functions whose Fourier coefficients are concentrated on low degrees. While such functions look very simple, we are surprisingly far from understanding them well, even in the most basic first-degree case.

We shall present several results on first-degree Boolean functions, including the recent proof of Tomaszewski's conjecture (1986) which asserts that any first-degree function (viewed as a random variable) lies within one standard deviation from its expectation with probability at least 1/2. Then we shall discuss several core open questions, which boil down to understanding, what does the knowledge that a low-degree function is bounded, or is two-valued, tell us about its structure.

Based on joint work with Ohad Klein

For more information, please contact Math Department by phone at 626-395-4335 or by email at [email protected].