Bounded Relative Boundary Implies Narrow DNF Approximation
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "Bounded Relative Boundary Implies Narrow DNF Approximation".
Jane: Here's the gist of the paper. Bounded relative boundary implies narrow DNF approximation is proven by showing that every increasing Boolean function with total resampling influence at most K is ε-close under µn p to a monotone DNF of width exp(O((K + 1)2/ε2)).
Tom: Proof Architecture The proof architecture proceeds through a sequence of transformations starting from f, moving to Hatami’s approximator h, then constructing an increasing adaptive approximator u, and finally extracting a monotone DNF g.
Jane: The function HD resulting from the sequence of shifts is shown to be increasing and FJ D-measurable, with the expected error bounded by ED Pp
f!= HD: ≤ Pp
f!= h: .
Tom: Certificate Extraction Once both the decoder and the activations are increasing, adaptive information turns into positive witnesses by a deterministic argument.
Title and authors: Tom: So we're looking at a paper called "Bounded Relative Boundary Implies Narrow DNF Approximation." Jane It sounds like it’s tackling that big conjecture from Friedgut about increasing functions in a biased cube. Tom Exactly, it’s about showing that if you have an increasing family with bounded relative boundary, you can actually approximate it really well using a monotone DNF.
Lu: The paper is building on Hatami's work on pseudo-juntas, which is interesting because it moves away from the standard junta idea. Tom Right, so instead of just saying "this function depends on K coordinates," they are looking at more complex structures that Hatami defined.
Meng: I wonder what the practical implication is here for deployment. If we can approximate a function with a monotone DNF, that’s good because DNFs are easier to reason about in many systems than arbitrary Boolean functions. Jane So basically, they are translating this theoretical boundary condition into something concrete we can use for approximation.
Lalam: I'm seeing that the core result is linking the total resampling influence of a function, which they call Ip of f, to the width of this DNF approximation. Tom That sounds like it connects two very different ways of measuring complexity.
The paper's summary: Jane: So what does the paper actually say about this relationship? It seems to establish a quantitative bound on how big that width of the monotone DNF needs to be, based on K and epsilon. Tom They show that for any increasing function f with total resampling influence at most K, you can find a monotone DNF g whose width is bounded by something like exp of C times K squared over epsilon squared.
Lu: That exponential dependence on epsilon suggests that getting closer to the true function requires exponentially more terms in the DNF when you want high accuracy. Tom Yeah, that's what they show for Theorem one point two, which gives this width bound for an approximation error of at most epsilon under mu n p <ref:2609.00240#pg3>.
Meng: But there’s a catch there, isn't there? They mention that this result only holds when the bias p is less than or equal to one-half. Jane That’s a big caveat because we know that high bias cases behave differently in these types of problems.
Lalam: The paper handles that by using a separate high-bias argument, which essentially takes the all-bias statement and reduces it back down to the low bias case when p is small. Tom So they’re covering both scenarios, which is important for a complete picture of what these functions look like.
The paper's improvements: Tom: I noticed they mention some specific improvements in their approach, like using a bias-matched randomized shifting procedure. Jane That sounds like they’re trying to bridge the gap between Hatami's pseudo-junta approximator and an increasing function representation. Lu That technique allows them to convert that pseudo-junta into something more useful—an increasing function with controlled local activations and dimensionfree arity bounds.
Meng: From a deployment standpoint, if we can get dimensionfree arity bounds, that means the complexity of our required components doesn't explode just because the input size n gets huge. Tom That’s key; it means the complexity is tied to K and epsilon instead of n itself.
Lalam: They also mentioned that they can certify that for increasing functions with total resampling influence at most K, there exists an increasing Boolean function B such that the distance between f and B under mu n p is small. Jane That’s a refinement because it says we don't just need an approximation; we can find a specific structure, B, that is close to f.
Conclusion: Tom: So to wrap up the paper "Bounded Relative Boundary Implies Narrow DNF Approximation," they prove Friedgut's conjecture by showing this explicit width bound on the monotone DNF g. Jane It really shows that for functions with bounded relative boundary, we get a narrow way to approximate them using a monotone DNF, and that width depends on K and epsilon.
Lu: The main thing I take away is how they proved it by tracking Hatami’s construction and using this bias-matched randomized shifting procedure. Tom And Meng, from an engineering view, the result suggests we can control the complexity of these sparse representations based on how much influence the function has, K.
Meng: Yeah, and since it's controlling width rather than just the number of terms in a DNF size bound, that's more useful for things like memory constraints. Lalam And I think it’s important to remember that this proof is conditional on p being less than or equal to one-half for the main theorem.
Tom: Right, so we have this explicit width bound related to K and epsilon, and we know how they handled the high bias cases separately. That's what they did with "Bounded Relative Boundary Implies Narrow DNF Approximation."
Chenghua Liu, Boning Meng
Institute of Software, Chinese Academy of Sciences · University of Regensburg
cs.CC, cs.DM
Submitted: 2026-08-31
Updated: 2026-11-06
Comments: 13 pages; proof and exposition revised, Lean repository linked
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 75/100
The gist: Bounded relative boundary implies narrow DNF approximation is proven by showing that every increasing Boolean function with total resampling influence at most K is ε-close under µn p to a monotone…
Key concepts
- Total Resampling Influence (Ip(f))
- This measures how much a function's output changes when a single input coordinate is randomly resampled. If this influence is small (at most K), it implies the function is relatively smooth or simple in terms of its dependence on individual variables, which allows for a compact approximation.
- Monotone DNF Width
- A monotone DNF is a sum of positive terms (disjunctions). The 'width' refers to the maximum number of literals in any single term. Bounding this width exponentially in 1/epsilon means we can find an approximation where every required 'witness' term is relatively short, leading to a narrow and efficient representation.
- Bounded Relative Boundary
- This is a condition on the function's behavior under specific probabilistic measures (like $\mu_n p$). The paper shows that meeting this boundary implies the existence of an increasing approximation. This boundary condition is key because it links the local sensitivity (K) to the global structure needed for a good DNF fit.
Terminology
Summary
Bounded relative boundary implies narrow DNF approximation is proven by showing that every increasing Boolean function with total resampling influence at most K is ε-close under µn p to a monotone DNF of width exp(O((K + 1)2/ε2)). p. 0
Proof Architecture
The proof architecture proceeds through a sequence of transformations starting from f, moving to Hatami’s approximator h, then constructing an increasing adaptive approximator u, and finally extracting a monotone DNF g. The function HD resulting from the sequence of shifts is shown to be increasing and FJ D-measurable, with the expected error bounded by ED Pp[f! p. 4= HD] ≤ Pp[f!= h].
Certificate Extraction
Once both the decoder and the activations are increasing, adaptive information turns into positive witnesses by a deterministic argument.
Relation to Prior Work
The work builds on Friedgut’s local-witness principle [Fri99, Conjecture 1.5] and Hatami’s structure theorem [Hat12, Section 6]. p. 2 This contrasts with Keller and Lifshitz work on the uniform cube, whose result controls DNF size rather than width. p. 3 The proof shows that the restriction p ≤ 1/2 in Theorem 1. p. 22 is genuine for the hypothesis Ip(f) = O(1). p. 9 p. 9 This confirms the required multiplicity-counted activation load. p. 2
Conjecture Proof Details
The proof of Conjecture 1.1 handles the case p > 1/2 by applying Friedgut’s biased junta theorem uniformly for p ∈ [λ, 1 − λ]. p. 8 The maximum of this bound and the low-bias bound proves the conjecture. p. 8
Limitations
The proof controls width, not the number of terms, and is existential rather than algorithmic. Determining the optimal dependence of the width on K and ε, or obtaining useful size and algorithmic bounds, remains open. p. 9 The proof of Theorem 1. p. 02 is conditional on p ≤ 1/2. p. 5
High Bias Case
The paper notes that the bounded-Ip(f) statement is false at high bias, providing an example where Ip(f) diverges, and the all-bias quantity is instead pEp[sensf (X)] = npn. This demonstrates the difference between Friedgut’s all-bias quantity and the relative boundary. p. 1 The example shows that for fixed w, no fixed-width monotone DNF can approximate f to sufficiently small constant error. p. 1
Conclusion
The paper successfully proves Friedgut’s conjecture by showing that bounded relative boundary implies narrow DNF approximation. The result provides an inner approximation to the intermediate monotone decoder u, not necessarily to the original function f. p. 9 The final bound on width is O((K + 1)2/ε 2). p. 2 The result controls width rather than DNF size. p. 4
References
[BHST14] Eric Blais, Johan Håstad, Rocco A. Servedio, and Li-Yang Tan. On DNF approximators for monotone Boolean functions. p. 4
[DFH24] Irit Dinur, Yuval Filmus, and Prahladh Harsha. p. 4 Sparse juntas on the biased hypercube. p. 2
[FK96] Ehud Friedgut and Gil Kalai. p. 3 Every monotone graph property has a sharp threshold. p. 8
[Fri98] Ehud Friedgut. p. 1 Boolean functions with low average sensitivity depend on few coordinates. p. 0
[Fri99] Ehud Friedgut, with an appendix by Jean Bourgain. p. 3 Sharp thresholds of graph properties, and the k-SAT problem. p. 0
[Hat12] Hamed Hatami. p. 2 A structure theorem for Boolean functions with small total influences. p. 0
[KKL88] Jeff Kahn, Gil Kalai, and Nathan Linial. p. 0 The influence of variables on Boolean functions. p. 0
[KL18] Nathan Keller and Noam Lifshitz. p. 3 Approximation of biased Boolean functions of small total influence by DNFs. p. 1
[Mar74] Grigory A. p. 1 Margulis. Probabilistic characteristics of graphs with large connectivity. p. 1
[O’D14] Ryan O’Donnell. p. 8 Analysis of Boolean Functions. p. 0
[Rus81] Lucio Russo. p. 1 On the critical percolation probabilities. p. 3
--- Page 1 ---
Bounded Relative Boundary Implies Narrow DNF Approximation Chenghua Liu and Boning Meng
--- Page 2 ---
f: n → n is increasing if x ≤ y coordinatewise implies f(x) ≤ f(y) If x ⊕i is obtained by flipping coordinate i, define sensf (x) = For X ∼ µn p, let X(i) be obtained by independently resampling coordinate i We use the total resampling influence Ip(f) = Xn i=1 Pp f(X)!= f(X(i)) (1)
--- Page 3 ---
A k-junta is a Boolean function that depends on at most k coordinates When p is bounded away from zero and one, Friedgut’s junta theorem states that bounded total influence implies approximation by a k-junta for some k independent of n [Fri98]. This conclusion is no longer appropriate when p tends to zero. p. 1 At p = 1/n, for example, the function ORn(x) = x1 ∨ · · · ∨ xn satisfies I1/n(ORn) = 2(1 − 1/n) n = O(1) but remains a constant distance under µn1/n from every k-junta with fixed k. p. 1 Yet one can certify that ORn(x) = 1 by revealing a single coordinate equal to one. p. 1 Sparse random graphs exhibit the same distinction
--- Page 5 ---
A monotone DNF is a disjunction of positive terms, and its width is the largest |T| among them. Each term is a local positive witness because setting its coordinates to one forces acceptance. p. 1 We use the usual conventions that the empty conjunction is one, the empty disjunction is zero, and both constant functions have width zero. p. 1
--- Page 8 ---
If u(x) = 1, then T(x) is a positive certificate for u: every y ∈ n satisfying yi = 1 for all i ∈ T(x) has u(y) = 1. Consequently, for every integer w ≥ 0, gw(y) = x∈n: u(x)=1 T(x≤w i∈T(x)yi (13) is a monotone DNF of width at most w, satisfies gw ≤ u, and obeys Pp[u! p. 7= gw] ≤ Pp[T(X) > w].
--- Page 9 ---
The proof of Theorem 1.2. If f is constant, use the corresponding width-zero DNF. p. 8 Otherwise put CK = ⌈K⌉, a = ε/4. p. 8 Since ⌈Ip(f)⌉ ≤ CK, Lemma 2. p. 81 gives an approximator h and increasing activations J such that Pp[f! p. 8= h] ≤ a, h is FJ-measurable, arity(J) ≤ d = 4000CK / ε. p. 8
--- Page 11 ---
The number bT is global and independent of y. Since p ≤ 1/2, the point mass µT p(y) is nonincreasing in y. p. 4 p. 4 Moreover, nonzero activations have arity at most k ≤ d. p. 9 p. 9
--- Page 14 ---
The number bT is global and independent of y. Since p ≤ 1/2, the point mass µT p(y) is nonincreasing in y. Moreover, nonzero activations have arity at most k ≤ d.
--- Page 15 ---
If Ip(f) > 0, then Cf ≥ 1, hence k = Cf /ε0 ≥ 1. Therefore, k 2/k + 1. p. 1 This proves the theorem. p. 7
--- Page 17 ---
The restriction p ≤ 1/2 in Theorem 1.2 is genuine for the hypothesis Ip(f) = O(1). Appendix B records the standard high-bias AND example. p. 9
--- Page 18 ---
The gap after Hatami. Hatami’s structure theorem replaces an ordinary junta by a pseudo-junta [Hat12]. p. 2 p. 2 p. 2 For S ⊆ [n], write xS for the restriction of x to S. p. 2 p. 2 p. 2 Hatami supplies a family J = (JS)S⊆[n] of local activation functions JS: n → n and an approximator h of f. p. 2 p. 2 p. 2 On input x, the activations determine the information AJ (x) = [S:JS(xS)=1 S, ΦJ (x) = AJ (x), xAJ(x). p. 2 Thus ΦJ (x) records the coordinates activated at x together with their values. p. 2 p. 2 p. 2
--- Page 17 ---
The gap after Hatami. Hatami’s structure theorem replaces an ordinary junta by a pseudo-junta [Hat12]. For S ⊆ [n], write xS for the restriction of x to S. Hatami supplies a family J = (JS)S⊆[n] of local activation functions JS: n → n and an approximator h of f. On input x, the activations determine the information AJ (x) = [S:JS(xS)=1 S, ΦJ (x) = AJ(x), xAJ(x). p. 2 p. 2 Thus ΦJ (x) records the coordinates activated at x together with their values.
--- Page 18 ---
The gap after Hatami. Hatami’s structure theorem replaces an ordinary junta by a pseudo-junta [Hat12]. For S ⊆ [n], write xS for the restriction of x to S. Hatami supplies a family J = (JS)S⊆[n] of local activation functions JS: n → n and an approximator h of f. On input x, the activations determine the information AJ (x) = [S:JS(xS)=1 S, ΦJ (x) = AJ(x), xAJ(x). Thus ΦJ (x) records the coordinates activated at x together with their values.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Bias-matched monotonicization improves approximation by converting Hatami’s pseudo-junta approximator into an increasing function while retaining exact measurability with respect to a controlled forced refinement of its adaptive representation. This allows for the extraction of positive certificates to obtain a narrow monotone DNF, which is the required approximation class for sparse product spaces.
-
The system can achieve an approximation error of at most epsilon under mu n p by constructing a monotone DNF g whose width is bounded by expC(K + 1)2/epsilon2, where K relates to the total resampling influence Ip(f). This provides a dimension-free and explicit bound on the complexity of sparse representations.
-
The improved system can certify that for increasing Boolean functions with total resampling influence at most K, there exists an increasing B such that mu n p (A △ B) is small, where minimal elements of B have bounded size k = k(c, epsilon). This directly addresses Friedgut’s conjecture by linking local sensitivity to the size of positive witnesses.
-
The system can handle varying biases p in the range (0, 1) by utilizing a bias-matched randomized shifting procedure and a high-bias reduction. This ensures that the approximation quality remains robust regardless of whether p is near zero or one, resolving the limitation where standard junta theorems fail.
-
The system can generate monotone DNFs whose width is controlled by log 1 over epsilon plus K plus 1 over epsilon plus (K + 1)2/epsilon2, specifically when approximating functions with total resampling influence at most K. This provides a quantitative measure of the complexity needed for approximation, controlling width rather than just the number of terms.
Related papers
- The Proof Analysis Problem for Constant-Depth Frege
- Hardness of Counting Orderings: Taking Gadget Amplification to the Limit
- Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth
- Parameterized Hardness of Zonotope Containment and Neural Network Verification
- From Block Orthogonality to Decidability in Complex-Weighted Counting CSP
- Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?