Bounded Relative Boundary Implies Narrow DNF Approximation
Friedgut conjectured in 1999 that every increasing family in the p-biased discrete cube with bounded relative boundary can be approximated by a family whose minimal elements have size bounded independently of the dimension and the bias. Hatami's pseudo-junta theorem gives an adaptive approximation, but its approximator need not be increasing.
Starting from Hatami's construction, made explicit with arity and activation-load bounds, the authors apply randomized bias-matched coordinate shifts. These choose an upper or lower shift with probabilities 1-p and p, which makes the approximator increasing without increasing the expected error. The result stays measurable with respect to a controlled refinement of Hatami's adaptive partition. Active 1-coordinates then form positive certificates, and keeping only the short certificates gives a monotone DNF. The proofs were formalized in Lean.
For 0<p≤1/2, every increasing Boolean function with total resampling influence at most K is ε-close under μ_p^n to a monotone DNF of width exp(O((K+1)^2/ε^2)). The full Friedgut conjecture follows for all p in (0,1).
