Source-linked AI summary
Bounded Relative Boundary Implies Narrow DNF Approximation
Chenghua Liu, Boning Meng
TL;DR
The paper addresses whether bounded relative boundary suffices for dimension- and bias-independent approximation of increasing Boolean functions by bounded-size positive witnesses. It combines Hatami’s adaptive pseudo-junta representation with bias-matched randomized shifting and forced refinements, proving narrow monotone-DNF approximation and thereby resolving Friedgut’s conjecture.
Problem
At p = 1/n, OR_n has bounded total resampling influence but stays a constant distance from every fixed-width junta, motivating Friedgut’s narrower positive-witness conjecture.
Method
The proof tracks Hatami’s increasing local activations, applies bias-matched randomized coordinate shifts, preserves measurability through forced activations, and extracts truncated positive certificates.
Results
For 0 < p ≤ 1/2, every increasing f with I_p(f) ≤ K is ε-close to a monotone DNF of width at most exp(O((K + 1)^2/ε^2)); a high-bias reduction completes the conjecture.
Takeaways & Limitations
Narrow monotone DNFs, rather than ordinary juntas, are the appropriate dimension-free approximating class for sparse product spaces.
Takeaways & Limitations
Hatami’s original approximator need not be increasing, and this defect cannot generally be repaired using the same adaptive partition.
Abstract
from arXiv · showhide
Friedgut conjectured that an increasing family in the $p$-biased discrete cube with bounded relative boundary can be approximated arbitrarily well by one whose minimal elements have bounded size, with a bound independent of the dimension and the bias (J. Amer. Math. Soc. 12 (1999)). We prove this conjecture by showing that, for $0<p\leq 1/2$, every increasing Boolean function with total resampling influence at most $K$ is $\varepsilon$-close under $μ_p^n$ to a monotone DNF of width $\exp(O((K+1)^2/\varepsilon^2))$. A separate high-bias argument completes the proof for all $p\in(0,1)$. Our proof builds on Hatami's pseudo-junta theorem (Ann. of Math. 176 (2012)). Tracking Hatami's construction isolates an adaptive representation with increasing local activations and dimension-free arity and multiplicity-counted load bounds. Our main new ingredient is a bias-matched randomized shifting procedure that converts the pseudo-junta approximator into an increasing function while retaining exact measurability with respect to a controlled forced refinement of its adaptive representation. From the resulting monotone adaptive representation, we extract positive certificates and truncate them to obtain the required narrow DNF.
1 Introduction
The paper proves Friedgut’s conjecture: bounded relative boundary in the p-biased cube yields approximation by narrow monotone DNFs with dimension- and bias-independent bounds. It resolves the obstruction in Hatami’s pseudo-junta theorem by monotonicizing the adaptive approximator while preserving controlled measurability.
- Motivation: At p = 1/n, OR_n has bounded total resampling influence but remains a constant distance from every fixed-width junta.A single positive coordinate nevertheless certifies that OR_n accepts, motivating bounded-size local witnesses rather than ordinary juntas.
- Problem: Friedgut’s conjecture asks whether every increasing family with bounded relative boundary can be approximated arbitrarily closely by one whose minimal elements have uniformly bounded Hamming weight.Monotone DNF width equals the maximum size of its positive minimal witnesses.
- Result: Theorem 1.2 gives, for 0 < p ≤ 1/2 and I_p(f) ≤ K, an ε-close monotone DNF of width at most exp(O((K + 1)^2/ε^2)).The bound is independent of the dimension n and the bias p in the low-bias regime; a high-bias reduction completes the all-bias result.
- Gap: Hatami’s representation has increasing local activations and approximates f, but its readout need not be increasing even when f is.The paper identifies this failure as the precise gap between Hatami’s pseudo-junta theorem and Friedgut’s conjecture.
- Proof architecture: Bias-matched randomized coordinate shifts make the approximator increasing, while forced activations preserve measurability with respect to a controlled adaptive refinement.Positive certificates are then extracted and truncated to produce the narrow monotone DNF.
- Adaptive structure: The proof tracks activation arity d = O((K + 1)/ε) and multiplicity-counted activation load at most exp(O((K + 1)^2/ε^2)).The load accounts for overlapping active sets with multiplicity.
2 Hatami’s pseudo-juntas
Hatami’s pseudo-junta representation approximates the target through increasing local activations with bounded arity and multiplicity-counted load. The approximator is measurable on the resulting adaptive partition, but these properties alone do not ensure it is increasing.
- Definitions: An M-pseudo-junta is measurable with respect to an activation family whose expected active-union size is at most M.The adaptive partition is generated by the activation information recorded at each input.
- Parameters: Multiplicity-counted load can exceed expected active-union size when active indexing sets overlap.This distinction motivates tracking load separately from the active union.
- Hatami’s construction: Hatami’s construction provides an approximator h with error at most a, arity at most d, and load at most L.The activations are increasing, and the bounds are dimension-independent in the stated parameters.
- Hatami’s construction: The activation family is built from significant Walsh components, with degree controlling arity and point-mass thresholds defining local activations.For p ≤1/2, point masses decrease coordinatewise, making each activation increasing.
3 Controlled monotonicization of adaptive structure
Randomized coordinate shifts convert the pseudo-junta approximator into an increasing function while preserving controlled measurability through forced activations. The construction tracks the bias change and activation load so the resulting adaptive representation remains quantitatively controlled.
- Randomized shifts: A one-coordinate randomized shift makes the processed function nondecreasing in that coordinate while preserving monotonicity in coordinates where the original function was nondecreasing.The shift acts only on the decreasing 10 fiber, replacing it by either 11 or 00.
- Randomized shifts: Applying independent shifts in a fixed order yields an increasing function H_D, with D distributed according to μ_p and an error controlled by iterated conditional expectation.The processing order may affect H_D; the argument does not require shifts to commute.
- Adaptive information after shifting: Forced activations record the active set at a shifted input while retaining the original labels of the coordinates in that set.This supplies the information needed to recover adaptive atoms after lower shifts.
- Adaptive information after shifting: Upper shifts preserve measurability on the old adaptive partition, whereas lower shifts require the forced refinement J^D.The asymmetry arises because raising a coordinate can create activations whose labels the lower atom does not record.
- Cost of forcing: Forcing coordinates changes the effective bias from p to p′ = 2p − p^2, and arity bounds control the resulting likelihood ratios and load transport.The load analysis uses activations supported on sets of size at most d and compares Λ_p with Λ_p′.
- Controlled monotonicization: Controlled monotonicization produces an increasing u that is measurable with respect to the forced activation system F_{J^D}.The theorem obtains this function by selecting one shift realization whose error and load satisfy the required bounds.
4 Certificates and completion of the proof
The proof converts an increasing adaptive representation into positive certificates, truncates those certificates to obtain a narrow monotone DNF, and then handles low and high bias separately to complete Friedgut’s conjecture.
- Increasing adaptive information yields positive certificates for the intermediate decoder, because active coordinates set to one force acceptance.
- Truncating certificates at width w produces a monotone DNF below u, with disagreement controlled by the probability that a certificate exceeds w.
- The proof starts from Hatami’s approximator and increasing activations, applies randomized shifting to obtain an increasing measurable function, and then extracts the DNF.
- For p bounded away from the endpoints, Friedgut’s biased junta theorem gives an increasing junta and hence a monotone DNF, while extreme high bias is handled by a width-zero constant.
- The result controls width but not the number of terms, is existential rather than algorithmic, and leaves optimal K- and ε-dependence open.
A Hatami’s construction with arity and load
The paper tracks Hatami’s Fourier-analytic construction to obtain an adaptive pseudo-junta representation with increasing activations, bounded arity, and controlled multiplicity-counted load while preserving approximation.
- The tracked construction preserves Hatami’s approximation guarantee while producing dimension-free arity and multiplicity-counted activation-load bounds.
- The activation family is built from the p-biased Walsh expansion, with Fourier coefficients and coordinate factors defining each activation.
- Parseval’s identity and the resampling definition of influence supply the analytic estimates used to control the construction.
- For p ≤1/2, the constructed activations are increasing, and every nonzero activation has arity at most k ≤d.
- The same construction satisfies the required multiplicity-counted activation-load estimate from Hatami’s displayed bound.
B Adaptive atoms under shifting and two obstructions
The shifting argument preserves adaptive measurability through controlled refinements, but the appendix shows that lower shifts may require a finer partition and that the bounded-influence statement is genuinely low-bias.
- Adaptive atoms under shifting: Lower shifts can require forced refinements because newly activated coordinates are not recorded by the lower atom.
- Adaptive atoms under shifting: Upper shifts remain measurable with respect to the original adaptive partition because increasing activations determine the relevant endpoint atoms.
- Adaptive atoms under shifting: The atom maps show that arbitrary interleavings of upper and lower shifts are handled by composing the corresponding coordinate transformations.
- Two obstructions: At p = 1/2, a three-variable example shows that the best increasing decoder on the original partition has strictly larger error than the unrestricted decoder.