FKN, first proof, rewritten

Authors Ehud Friedgut, Gil Kalai, Assaf Naor

Publication date 6 May 2021

Abstract: About twenty years ago we wrote a paper, "Boolean Functions whose Fourier Transform is Concentrated on the First Two Levels", cite{FKN}. In it we offered several proofs of the statement that Boolean functions

f (x_{1}, x_{2}, d o t s, x_{n})

, whose Fourier coefficients are concentrated on the lowest two levels are close to a constant function or to a function of the form

f = x_{k}

or

f = 1 - x_{k}

. Returning to the paper lately, we noticed that the presentation of the first proof is rather cumbersome, and includes several typos. In this note we rewrite that proof, as a service to the public.

This page was built for publication: FKN, first proof, rewritten

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6367080)