Approximation of biased Boolean functions of small total influence by DNFs

DOI10.1112/BLMS.12167MaRDI QIDQ4583634zbMATH OpenOpenAlexWikidataFDO

Authors Nathan Keller, Noam Lifshitz

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) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Boolean functions (06E30)

Abstract: The influence of the $k$'th coordinate on a Boolean function $f:{0,1}^{n}ightarrow0,1$ is the probability that flipping $x_k$ changes the value $f(x)$. The total influence $I(f)$ is the sum of influences of the coordinates. The well-known `Junta Theorem' of Friedgut (1998) asserts that if $I(f)leqM$, then $f$ can be $epsilon$-approximated by a function that depends on $O(2^{M/epsilon})$ coordinates. Friedgut's theorem has a wide variety of applications in mathematics and theoretical computer science. For a biased function with $E[f]=mu$, the edge isoperimetric inequality on the cube implies that $I(f)geq2mulog(1/mu)$. Kahn and Kalai (2006) asked, in the spirit of the Junta theorem, whether any $f$ such that $I(f)$ is within a constant factor of the minimum, can be $epsilonmu$-approximated by a DNF of a `small' size (i.e., a union of a small number of sub-cubes). We answer the question by proving the following structure theorem: If $I(f)leq2mu(log(1/mu)+M)$, then $f$ can be $epsilonmu$-approximated by a DNF of size $2^{2^{O(M/epsilon)}}$. The dependence on $M$ is sharp up to the constant factor in the double exponent.

Recommendations

• A structure theorem for Boolean functions with small total influences
• Approximation by DNF: Examples and Counterexamples
• Variable Influences in Conjunctive Normal Forms
• Decision Trees and Influences of Variables Over Product Probability Spaces
• Approximating the influence of monotone Boolean functions in \(O(\sqrt{n})\) query complexity

Cited in

(15)

• A stability result for the cube edge isoperimetric inequality
• Stability for vertex isoperimetry in the cube
• Approximating the influence of monotone Boolean functions in \(O(\sqrt{n})\) query complexity
• Approximating the influence of monotone Boolean functions in \(O(\sqrt{n})\) query complexity
• Friedgut-Kalai-Naor theorem for slices of the Boolean cube
• Variable Influences in Conjunctive Normal Forms
• A structure theorem for Boolean functions with small total influences
• Criticality of regular formulas
• Analyzing Boolean functions on the biased hypercube via higher-dimensional agreement tests
• Approximation by DNF: Examples and Counterexamples
• Hypercontractivity for global functions and sharp thresholds
• Isoperimetric stability in lattices
• The complexity of subcube partition relates to the additive structure of the support
• Approximation algorithm for DNF under distributions with limited independence
• Isoperimetric stability in lattices (extended abstract)

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

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