FKN theorem on the biased cube
From MaRDI portal
Publication:2933573
DOI10.4064/CM137-2-9zbMATH Open1309.42040arXiv1311.3179OpenAlexW2054186157MaRDI QIDQ2933573FDOQ2933573
Authors: Piotr Nayar 
Publication date: 3 December 2014
Published in: Colloquium Mathematicum (Search for Journal in Brave)
Abstract: In this note we consider Boolean functions defined on the discrete cube equipped with a biased product probability measure. We prove that if the spectrum of such a function is concentrated on the first two Fourier levels, then the function is close to a certain function of one variable. Moreover, in the symmetric case 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.
Full work available at URL: https://arxiv.org/abs/1311.3179
Recommendations
- Friedgut-Kalai-Naor theorem for slices of the Boolean cube
- A simple reduction from a biased measure on the discrete cube to the uniform measure
- scientific article; zbMATH DE number 5062518
- Analyzing Boolean functions on the biased hypercube via higher-dimensional agreement tests
- FKN theorem for the multislice, with applications
Inequalities; stochastic orderings (60E15) Fourier series in special orthogonal functions (Legendre polynomials, Walsh functions, etc.) (42C10)
Cited In (7)
- A structure theorem for almost low-degree functions on the slice
- Boolean functions on \(S_n\) which are nearly linear
- FKN theorem for the multislice, with applications
- A simple reduction from a biased measure on the discrete cube to the uniform measure
- Stability versions of Erdős-Ko-Rado type theorems via isoperimetry
- Friedgut-Kalai-Naor theorem for slices of the Boolean cube
- Analyzing Boolean functions on the biased hypercube via higher-dimensional agreement tests
This page was built for publication: FKN theorem on the biased cube
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2933573)
