Friedgut-Kalai-Naor theorem for slices of the Boolean cube

DOI10.4086/CJTCS.2016.014MaRDI QIDQ3179336zbMATH OpenOpenAlexFDO

Authors Yuval Filmus

Publication date 21 December 2016

Published in Chicago Journal of Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1410.7834

zbMATH Keywords

stabilityJohnson schemesliceanalysis of Boolean functions

Mathematics Subject Classification ID

Convergence of probability measures (60B10) Combinatorial probability (60C05) Boolean functions (06E30) Measures and integrals in product spaces (28A35)

Abstract: The Friedgut--Kalai--Naor theorem states that if a Boolean function $fcolon{0,1}^{n}o0,1$ is close (in $L^2$-distance) to an affine function $ell(x_1,\mathrm{...},x_n)=c_0+su{m}_i{c}_i{x}_i$, then $f$ is close to a Boolean affine function (which necessarily depends on at most one coordinate). We prove a similar theorem for functions defined over $$.

Recommendations

• FKN theorem for the multislice, with applications
• FKN theorem on the biased cube
• A structure theorem for almost low-degree functions on the slice
• An orthogonal basis for functions over a slice of the Boolean hypercube
• Approximation of biased Boolean functions of small total influence by DNFs

Cites work

• A simple reduction from a biased measure on the discrete cube to the uniform measure
• Boolean functions with low average sensitivity depend on few coordinates
• FKN theorem on the biased cube
• On the measure of intersecting families, uniqueness and stability
• The diametric theorem in Hamming spaces---optimal anticodes

Cited in

(26)

• Analyzing Boolean functions on the biased hypercube via higher-dimensional agreement tests
• Boolean function analysis on high-dimensional expanders
• A structure theorem for almost low-degree functions on the slice
• Removal and stability for Erdős-Ko-Rado
• Stability of large rainbow intersecting families with product measure
• Weightwise perfectly balanced functions with high weightwise nonlinearity profile
• Log-Sobolev inequality for the multislice, with applications
• An orthogonal basis for functions over a slice of the Boolean hypercube
• Sparse juntas on the biased hypercube
• Structure and supersaturation for intersecting families
• Boolean degree 1 functions on some classical association schemes
• A family of weightwise (almost) perfectly balanced Boolean functions with optimal algebraic immunity
• Construction of weightwise perfectly balanced Boolean functions with high weightwise nonlinearity
• Boolean functions on \(S_n\) which are nearly linear
• FKN theorem for the multislice, with applications
• scientific article; zbMATH DE number 7559077 (Why is no real title available?)
• A simple removal lemma for large nearly-intersecting families
• Degree 2 Boolean functions on Grassmann graphs
• A new construction of weightwise perfectly balanced Boolean functions
• On non-optimally expanding sets in Grassmann graphs
• Robustness of Erdős-Ko-Rado theorems on permutations and perfect matchings
• Small-set expansion in the Johnson graph
• Equivalent definitions for (degree one) Cameron-Liebler classes of generators in finite classical polar spaces
• The classification of Boolean degree 1 functions in high-dimensional finite vector spaces
• FKN theorem on the biased cube
• Boolean function analysis on high-dimensional expanders

This page was built for publication: Friedgut-Kalai-Naor theorem for slices of the Boolean cube

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3179336)