JEDNOSTKA NAUKOWA KATEGORII A+

# Wydawnictwa / Czasopisma IMPAN / Colloquium Mathematicum / Wszystkie zeszyty

## FKN Theorem on the biased cube

### Tom 137 / 2014

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.

Odśwież obrazek