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

DOI10.4086/CJTCS.2016.014zbMATH Open1401.06014arXiv1410.7834OpenAlexW4254238913MaRDI QIDQ3179336FDOQ3179336

Yuval Filmus

Publication date: 21 December 2016

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

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 $$.

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

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

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)

Cites Work

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

Cited In (21)

• A structure theorem for almost low-degree functions on the slice
• Removal and stability for Erdős-Ko-Rado
• 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
• FKN theorem for the multislice, with applications
• Title not available (Why is that?)
• A simple removal lemma for large nearly-intersecting families
• A new construction of weightwise perfectly balanced Boolean functions
• Degree 2 Boolean functions on Grassmann graphs
• On non-optimally expanding sets in Grassmann graphs
• 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
• Title not available (Why is that?)
• Boolean function analysis on high-dimensional expanders
• Boolean functions on $S_n$ which are nearly linear

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)