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

(23)

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

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)