Abstract
We consider Boolean functions defined on the discrete cube {-γ, γ-1}n equipped with a product probability measure µ⊗n, where µ = βδ-γ + αδγ-1 and γ = α/β. This normalization ensures that the coordinate functions (xi)i=1,…,n are orthonor-mal in L2({-γ, γ-1}n, µ⊗n). We prove that if the spectrum of a Boolean function is con-centrated 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.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 253-261 |
| Number of pages | 9 |
| Journal | Colloquium Mathematicum |
| Volume | 137 |
| Issue number | 2 |
| DOIs | |
| State | Published - 2014 |
Bibliographical note
Publisher Copyright:© Instytut Matematyczny PAN, 2014.
Keywords
- Boolean functions
- FKN theorem
- Walsh-fourier expansion
Fingerprint
Dive into the research topics of 'FKN theorem on the biased cube'. Together they form a unique fingerprint.Cite this
- APA
- Standard
- Harvard
- Vancouver
- Author
- BIBTEX
- RIS