Artykuły w formacie PDF dostępne są dla subskrybentów, którzy zapłacili za dostęp online, po podpisaniu licencji Licencja użytkownika instytucjonalnego. Czasopisma do 2009 są ogólnodostępne (bezpłatnie).

FKN Theorem on the biased cube

Tom 137 / 2014

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

Streszczenie

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.

Autorzy

  • 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

Przeszukaj wydawnictwa IMPAN

Zbyt krótkie zapytanie. Wpisz co najmniej 4 znaki.

Przepisz kod z obrazka

Odśwież obrazek

Odśwież obrazek