PDF files of articles are only available for institutions which have paid for the online version upon signing an Institutional User License.

FKN Theorem on the biased cube

Volume 137 / 2014

Piotr Nayar Colloquium Mathematicum 137 (2014), 253-261 MSC: Primary 42C10; Secondary 60E15. DOI: 10.4064/cm137-2-9

Abstract

We consider Boolean functions defined on the discrete cube $\{-\gamma ,\gamma ^{-1}\}^n$ equipped with a product probability measure $\mu ^{\otimes n}$, where $\mu =\beta \delta _{-\gamma }+\alpha \delta _{ \gamma ^{-1} }$ and $\gamma =\sqrt {\alpha / \beta }$. This normalization ensures that the coordinate functions $(x_i)_{i=1,\ldots ,n}$ are orthonormal in $L_2(\{-\gamma ,\gamma ^{-1}\}^n,\mu ^{\otimes n})$. We prove that if the spectrum of a Boolean function is concentrated on the first two Fourier levels, then the function is close to a certain function of one variable. Our theorem strengthens the non-symmetric FKN Theorem due to Jendrej, Oleszkiewicz and Wojtaszczyk.

Moreover, in the symmetric case $\alpha =\beta =1/2$ we prove that if a $[-1,1]$-valued function defined on the discrete cube is close to a certain affine function, then it is also close to a $[-1,1]$-valued affine function.

Authors

  • Piotr NayarInstitute of Mathematics
    University of Warsaw
    Banacha 2
    02-097 Warszawa, Poland
    and
    Institute for Mathematics and its Applications
    College of Science and Engineering
    University of Minnesota
    207 Church Street SE
    306 Lind Hall
    Minneapolis, MN 55455, U.S.A.
    e-mail

Search for IMPAN publications

Query phrase too short. Type at least 4 characters.

Rewrite code from the image

Reload image

Reload image