Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl

PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2014 | 137 | 2 | 253-261

Tytuł artykułu

FKN Theorem on the biased cube

Autorzy

Treść / Zawartość

Języki publikacji

EN

Abstrakty

EN
We consider Boolean functions defined on the discrete cube ${-γ, γ^{-1}}ⁿ$ equipped with a product probability measure $μ^{⊗ n}$, where $μ = βδ_{-γ} + αδ_{γ^{-1}}$ and γ = √(α/β). This normalization ensures that the coordinate functions $(x_i)_{i=1,...,n}$ are orthonormal in $L₂({-γ,γ^{-1}}ⁿ,μ^{⊗ 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 α = β = 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.

Twórcy

autor
  • Institute of Mathematics, University of Warsaw, Banacha 2, 02-097 Warszawa, Poland
  • 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.

Identyfikatory

Identyfikator YADDA

bwmeta1.element.bwnjournal-article-doi-10_4064-cm137-2-9