Approximation of biased Boolean functions of small total influence by DNFs

DOI10.1112/blms.12167zbMath1394.05138arXiv1703.10116OpenAlexW3125286862WikidataQ129769442 ScholiaQ129769442MaRDI QIDQ4583634

Noam Lifshitz, Nathan Keller

Publication date: 31 August 2018

Published in: Bulletin of the London Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

approximationBoolean functionsprobability measure

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Boolean functions (06E30) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Related Items (5)

Hypercontractivity for global functions and sharp thresholds ⋮ Isoperimetric stability in lattices ⋮ A stability result for the cube edge isoperimetric inequality ⋮ Stability for vertex isoperimetry in the cube ⋮ Criticality of regular formulas

This page was built for publication: Approximation of biased Boolean functions of small total influence by DNFs