Pith. sign in

REVIEW 1 major objections 4 minor 50 references

Learning DNF through Generalized Fourier Representations

T0 review · 1 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper claims that Fourier-based learning of DNF, previously limited to product distributions, extends to non-product distributions by building an orthonormal basis from any distribution’s Bayesian-network representation, and proves…

desk verdict Strong new Fourier machinery for non-product distributions with correct-looking spectral-norm bounds for known tree BNs, but the unknown-distribution extension has a c-boundedness gap that needs fixing. read the letter →

arxiv 2506.01075 v2 pith:AQGRGKEK submitted 2025-06-01 cs.DS cs.ITcs.LGmath.IT

Mohsen Heidari , Roni Khardon This is my paper · ORCID
classification cs.DScs.ITcs.LGmath.IT MSC 68Q32
keywords generalizedFourierrepresentationBayesiannetworksDNFlearningmembershipqueriesspectralnormdifference-boundeddistributionsdecisiontreesagnostic
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper claims that the Boolean Fourier approach to learning DNF, previously limited to uniform and product distributions, can be extended to a broad family of non-product distributions. The key move is to build an orthonormal function basis from the Bayesian-network representation of any distribution, so each variable's basis function is its normalized deviation from its parent-conditioned mean. For distributions whose BN is a tree with bounded parent-to-child differences, the paper proves that the L1 spectral norm of every d-literal conjunction stays bounded by $((2-2\alpha)/(1-2\alpha))^{2d}$, and that matching lower bounds show the tree and boundedness assumptions are necessary. From that bound, the paper derives polynomial-time membership-query learnability of DNF and agnostic learnability of decision trees, and it removes the assumption that the distribution is given by learning difference-bounded tree BNs.

What carries the argument

The BN-induced Fourier basis defines $\phi_S(x) = \prod_{v\in S} (x_v - \mu_{v,x_{\mathrm{pa}(v)}})/\sigma_{v,x_{\mathrm{pa}(v)}}$, where $\mu$ and $\sigma$ are the parent-conditioned means and standard deviations. The basis is orthonormal but not sparse, so the paper's analysis tracks the exact Fourier coefficients of conjunctions through the recursive quantities $A_i$ and $D_i$, which separate hierarchical and difference contributions along chain segments (Lemma 22). The extended KM algorithm estimates heavy coefficients by median-of-means estimators computed via ancestral sampling, requiring only forward sampling from the BN; the spectral-norm bound then transfers to learnability of DNF and decision trees.

What would settle it

Take a chain BN with $n$ variables all sharing $D_\mu = 0.5$ and $D_\sigma > 0$ so that $D_\mu + D_\sigma > 1$, as in Corollary 37, and compute $L_1(f)$ for the conjunction $f = X_{n+1}$; Lemma 36 predicts growth $\Omega((D_\mu + D_\sigma)^n)$, so measuring that growth for, say, $n = 20$ would confirm the necessity of the boundedness condition. Alternatively, construct an $\alpha$-difference-bounded tree with $2\alpha \ge 1$ and check whether the claimed bound $((2-2\alpha)/(1-2\alpha))^{2d}$ still holds or fails.

Watch

Extended reading notes

Core claim

The central discovery is Theorem 33: under any $\alpha$-difference-bounded tree Bayesian network, the $L_1$ spectral norm of a conjunction with $d$ literals is at most $((2-2\alpha)/(1-2\alpha))^{2d}$. Because the extended KM algorithm recovers all heavy coefficients in any BN-induced basis using only forward sampling, this spectral bound plugs into the Fourier learning machinery of Feldman (2012) and Gopalan et al. (2008). The result: disjoint DNF and decision trees are PAC-learnable with membership queries in polynomial time under such distributions, DNF is learnable through PTFconstruct, and agnostic learning of decision trees achieves error $\mathrm{opt}_C + \epsilon$. The lower bounds of Sections 7.1 and 7.2 show the same bound fails exponentially for chains with $D_\mu + D_\sigma \ge 1$ and for general graphs even with bounded parameter differences, so the tree structure is load-bearing rather than incidental.

Load-bearing premise

The entire learnability result presupposes the sampling distribution is exactly (or well approximated by) an $\alpha$-difference-bounded tree Bayesian network; when the dependency structure has cycles or conditional parameter differences are too large, the $L_1$ spectral norm of even a single literal can grow exponentially.

Editorial extensions

If this is right

  • Polynomial-time PAC learning of DNF with membership queries under any $c$-bounded, $\alpha$-difference-bounded tree distribution (Corollary 47).
  • Agnostic learning of decision trees under the same distributions with error $\mathrm{opt}_C + \epsilon$ (Corollary 48).
  • When the distribution is unknown, both realizable and unrealizable cases are learnable, the latter with residual error $\sqrt{0.5\,\mathrm{opt}}$ via Pinsker's inequality (Corollaries 55 and 64).
  • The spectral-norm bound extends to $k$-junta distributions, where $L_1(f) \le 2^{(k+d)/2}$, giving another non-product family where the Fourier approach succeeds (Lemma 44).
  • For product distributions the paper obtains an exact spectral norm, $\prod_{i\in T_1}(\mu_i+\sigma_i)\prod_{j\in T_0}((1-\mu_j)+\sigma_j) \le 1.21^d$, tightening the previous $(\sqrt{2})^d$ bound (Proposition 30).

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the bound holds, one could try extending the same BN-basis analysis to low-degree algorithms: the paper's disjoint-DNF results indirectly imply low-degree success, but a clean degree-truncation statement for general DNF does not follow directly.
  • The dependence of the bound on $\alpha$ suggests a tradeoff between graph width and parameter boundedness; the lower bounds hint that allowing small cycles may require much stronger difference bounds, which could be tested by computing $L_1$ for small anti-trees.
  • The residual error $\sqrt{0.5\,\mathrm{opt}}$ in the unrealizable case suggests the framework degrades gracefully, and one could test empirically whether the achievable error tracks $\mathrm{opt}$ or its square root for distributions that are not tree-structured.
  • The exact product-case formula (Proposition 30) implies that the spectral norm of a conjunction depends only on the product of $\mu_i+\sigma_i$ terms, which could be used to design faster coefficient-estimation routines for product distributions.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 4 minor

Summary. The paper introduces a distribution-dependent Fourier basis for Boolean functions induced by a Bayesian network representation of the sampling distribution. It extends the Kushilevitz–Mansour heavy-coefficient algorithm to this basis via median-of-means estimation, analyzes the spectral norm of conjunctions under chain and tree difference-bounded BNs and under k-junta distributions, proves lower bounds showing that the boundedness and tree-structure assumptions are necessary, and derives membership-query learnability of DNF and agnostic learnability of decision trees under the bounded-spectral-norm assumption. A final section (Section 10) gives algorithms for learning difference-bounded tree distributions in the realizable and unrealizable cases, with a Pinsker-based transfer to the original distribution in Section 10.4. The central claims depend on the structural premise that the learner has access to, or can estimate, a difference-bounded tree BN with the parameters used in the spectral-norm analysis.

Significance. If the results are correct, this is a substantial advance: it provides a Fourier-analytic route to DNF learning beyond product distributions, with explicit spectral-norm bounds for a broad non-product class, matching lower bounds, and an extension to the unknown-distribution setting. The paper is technically rich and self-contained: it includes full proofs of orthonormality, the extended KM algorithm, the chain and tree spectral-norm bounds, the k-junta bound, and the lower-bound constructions. The exact product-distribution spectral-norm formula in Proposition 30 and the detailed sample-complexity analysis for tree distribution learning are concrete, reproducible contributions. The learnability claims, however, are conditional on the learned distribution being c-bounded in the sense of Definition 2, and that premise is not guaranteed by the Section 10.2 algorithm as written.

major comments (1)
  1. [Section 10.2, Corollary 55] The difference-restricted directed Chow-Liu algorithm filters edges only for (0.5−c/2)-difference boundedness, not for c/2-boundedness. Because the directed maximum spanning tree may choose either orientation of an edge with equal undirected weight, it can output the reverse of a true c-bounded edge. Concretely, let the true tree be X→Y with P(X=1)=c, P(Y=1|X=0)=0.5, and P(Y=1|X=1)=c. This is c-bounded and (0.5−c)-difference bounded, and the reverse orientation has P(X=1|Y=1)=c^2/(c^2+0.5(1−c))≈2c^2, which is far below c/2 for small c, while the reverse orientation still passes the difference filter. Hence the output distribution \hat P^+ is not guaranteed to be c/2-bounded. The subsequent transfer in Section 10.4 and the learning corollaries in Section 9 (Lemma 45 and the truncation d=log_{1−c}(...)) require c-boundedness of the distribution used for learning. Therefore the claimed learnability under unknown difference-bounded tree distributions is not established as stated. The fix is to include an explicit c/2-boundedness check in the edge filter, or to otherwise prove that the output distribution is c/2-bounded, and to adjust the sample-complexity argument accordingly.
minor comments (4)
  1. [Section 10.2, Lemma 54] The proof of Lemma 54 ends with the inequality wt_P(\hat T)≥wt_P(T*)+ϵ/2; the sign appears to be a typo. The preceding argument and the lemma statement require wt_P(\hat T)≥wt_P(T*)−ϵ/2.
  2. [Section 4, before Lemma 11] There is a typo: "In.a similar manner" should read "In a similar manner."
  3. [Section 10.2] The phrase "which is less strict" refers only to the difference-boundedness threshold; it would be clearer to state explicitly that the algorithm does not enforce the c/2-boundedness half of Definition 2, since that distinction is load-bearing for the downstream learning results.
  4. [Section 6, Theorem 33] The proof of Theorem 33 bounds the A′ terms by 1 without invoking c-boundedness, while the definition of difference-bounded tree BN includes c-boundedness; a brief remark clarifying that the spectral-norm bound itself does not require the lower bound c would help avoid confusion about where c-boundedness is used.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the BN Fourier basis, heavy-coefficient algorithm, spectral norm bounds, and learning corollaries are derived from stated assumptions and external algorithm analyses; self-citations are contextual only.

full rationale

The paper's derivation chain is self-contained. The BN-induced basis is defined from a given BN and orthonormality is proved directly in Lemma 4; coefficients are E_D[f(X)phi_S(X)], not fitted values. The extended KM algorithm is proven through Lemma 7 and median-of-means concentration (Lemma 10), with no reliance on the conclusion. The spectral norm bounds (Lemmas 22, 27, 31-33, 44) are derived from the explicit c-boundedness and alpha-difference-boundedness assumptions, and the lower bounds (Corollaries 37, 40, Theorem 43) construct concrete distributions rather than assuming the upper bounds. The learning corollaries (46-48) state L1(d) as a hypothesis and instantiate it with the proved bounds; the parameters d=log(epsilon/s), theta, and gamma follow standard Fourier learning analysis and are not fitted to the target labels. Section 10's difference-restricted Chow-Liu algorithm learns a distribution from samples and explicitly transfers the approximation error via Pinsker's inequality, including a stated residual sqrt(0.5*opt) in the unrealizable case; this is an acknowledged approximation loss, not a disguised fit. The only self-citations (Heidari et al. 2021, 2022) appear in related-work discussion contrasting those approaches and are not load-bearing. No equation reduces to its own input by definition, and no fitted parameter is renamed as a prediction.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

The central theorems state bounds for arbitrary constants c and alpha, which are distribution assumptions rather than fitted values. The paper contains no empirical fitting, and the lower-bound constructions use concrete constants only to instantiate distributions. The claims rest on standard mathematical facts, on the universal BN representation, and on the domain assumptions of c-bounded, alpha-difference-bounded tree BNs. No new particles, forces, dimensions, or similar entities are introduced.

assumptions (7)
  • standard math The BN-induced functions phi_S form an orthonormal basis of the space of functions on {0,1}^n.
    Proved in Corollary 5 from conditional variance properties, with all conditional variances assumed positive.
  • standard math Any probability distribution over {0,1}^n can be represented by a Bayesian network.
    Universal representation from Pearl and Koller-Friedman, used to define the basis for arbitrary distributions.
  • domain assumption The distribution is c-bounded: every conditional probability lies in [c,1-c] for c in (0,1/2).
    Used in Lemma 23 and Lemma 45 to bound basis values and literal probabilities.
  • domain assumption The distribution is alpha-difference-bounded: conditional means and standard deviations of each node differ by at most alpha across parent assignments.
    Core quantitative premise for the spectral norm bounds, introduced in Definition 2.
  • domain assumption The BN has chain or tree structure for the main learning theorems.
    Theorem 33 and Corollaries 46-48 require a difference-bounded tree; the lower bounds show neither tree structure nor boundedness can be dropped.
  • standard math The paper relies on external algorithmic guarantees: the KM algorithm, Feldman's PTFconstruct, Gopalan et al.'s agnostic learner, and Chow-Liu finite-sample guarantees from Bhattacharyya et al.
    These external results are cited and adapted; their full proofs are not repeated in this paper.
  • domain assumption The parameters satisfy D_mu + D_sigma < 1 and 2*alpha < 1.
    Needed to make the geometric sums in Theorems 27 and 33 converge; the lower bounds in Section 7 show such conditions are necessary.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Learning DNF through Generalized Fourier Representations." pith.science (2026). https://pith.science/paper/AQGRGKEK

@misc{pith2026250601075,
  author       = {Pith},
  title        = {Pith review of: Learning DNF through Generalized Fourier Representations},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/AQGRGKEK}},
  note         = {Machine review of arXiv:2506.01075}
}
abstract

The Boolean Fourier representation has been widely used in learning theory, particularly for learning Disjunctive Normal Form (DNF) under uniform and product distributions. Extending these results to non-product distributions has remained a longstanding open problem. We address this challenge by introducing a generalized Fourier representation that enables learning under a broad class of non-product distributions. Our approach represents any distribution $D$ as a Bayesian network (BN) and derives a corresponding Fourier expansion. We show that standard Fourier-based learning techniques using membership queries to identify heavy coefficients can be adapted to this generalized representation with minor modifications. We prove that the $L_1$ spectral norm of conjunctions remains bounded under this expansion for difference-bounded tree BNs, significantly generalizing the known result for uniform distributions; matching lower bounds demonstrate the necessity of these constraints. Using these results, we establish the learnability of DNF and the agnostic learnability of decision trees under such distributions. Finally, we present an algorithm for learning difference-bounded tree BN distributions, extending our results to settings where the distribution is unknown.

Figures

Figures reproduced from arXiv: 2506.01075 by the authors.

Figure 1
Figure 1. A generic branch inside a tree BN. The branch is the chain of the nodes [PITH_FULL_IMAGE:figures/full_fig_p030_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

50 extracted references · 50 canonical work pages

  1. [1]

    On learning read-k-satisfy-j DNF

    Howard Aizenstein, Avrim Blum, Roni Khardon, Eyal Kushilevitz, Leonard Pitt, and Dan Roth. On learning read-k-satisfy-j DNF . SIAM Journal on Computing, 27 0 (6): 0 1515--1530, 1998

    work page 1998

  2. [2]

    S. M. Ali and Samuel D. Silvey. A general class of coefficients of divergence of one distribution from another. Journal of the royal statistical society series b-methodological, 28: 0 131--142, 1966

    work page 1966

  3. [3]

    Learning and testing junta distributions

    Maryam Aliakbarpour, Eric Blais, and Ronitt Rubinfeld. Learning and testing junta distributions. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, Proceedings of the 29th Conference on Learning Theory, volume 49, pages 19--46, 2016

    work page 2016

  4. [4]

    When won't membership queries help? Journal of Computer and System Sciences, 50 0 (2): 0 336--355, 1995

    Dana Angluin and Michael Kharitonov. When won't membership queries help? Journal of Computer and System Sciences, 50 0 (2): 0 336--355, 1995

    work page 1995

  5. [5]

    M. Bellare. The spectral norm of finite functions. Technical report, MIT, USA, 1991

    work page 1991

  6. [6]

    Arnab Bhattacharyya, Sutanu Gayen, Eric Price, Vincent Y. F. Tan, and N. V. Vinodchandran. Near-optimal learning of tree-structured distributions by Chow and Liu . SIAM Journal of Comput. , 52 0 (3): 0 761--793, 2023

    work page 2023

  7. [7]

    Lifting uniform learners via distributional decomposition

    Guy Blanc, Jane Lange, Ali Malik, and Li - Yang Tan. Lifting uniform learners via distributional decomposition. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages 1755--1767. ACM , 2023

    work page 2023

  8. [8]

    Furst, Jeffrey C

    Avrim Blum, Merrick L. Furst, Jeffrey C. Jackson, Michael J. Kearns, Yishay Mansour, and Steven Rudich. Weakly learning DNF and characterizing statistical query learning using Fourier analysis. In Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing , pages 253--262. ACM , 1994

    work page 1994

Show all 50 references
  1. [9]

    Nader H. Bshouty. Exact learning boolean function via the monotone theory. Information and Computation, 123 0 (1): 0 146--153, 1995

    1995

  2. [10]

    Bshouty and Christino Tamon

    Nader H. Bshouty and Christino Tamon. On the Fourier spectrum of monotone functions. Journal of the ACM , 43 0 (4): 0 747--770, 1996

    1996

  3. [11]

    Bshouty, Jeffrey C

    Nader H. Bshouty, Jeffrey C. Jackson, and Christino Tamon. More efficient PAC -learning of DNF with membership queries under the uniform distribution. Journal of Computer and System Sciences, 68 0 (1): 0 205--234, 2004

    2004

  4. [12]

    Generalized Hoeffding-Sobol decomposition for dependent variables-application to sensitivity analysis

    Ga \"e lle Chastaing, Fabrice Gamboa, Cl \'e mentine Prieur, et al. Generalized Hoeffding-Sobol decomposition for dependent variables-application to sensitivity analysis. Electronic Journal of Statistics, 6: 0 2420--2448, 2012

    2012

  5. [13]

    Learning and testing junta distributions with sub cube conditioning

    Xi Chen, Rajesh Jayaram, Amit Levi, and Erik Waingarten. Learning and testing junta distributions with sub cube conditioning. In Mikhail Belkin and Samory Kpotufe, editors, Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 1060--1113....

    2021

  6. [14]

    Chow and C

    C. Chow and C. Liu. Approximating discrete probability distributions with dependence trees. IEEE Transactions on Information Theory, 14 0 (3): 0 462--467, May 1968

    1968

  7. [15]

    Chow and T

    C. Chow and T. Wagner. Consistency of an estimate of tree-dependent probability distributions (corresp.). IEEE Transactions on Information Theory, 19 0 (3): 0 369--371, May 1973

    1973

  8. [16]

    I. Csiszár. Eine informationstheoretische ungleichung und ihre anwendung auf den beweis der ergodizität on markoffschen ketten. Publ. Math. Inst. Hungar. Acad. Sci., 8: 0 84--108, 1963

    1963

  9. [17]

    The sample complexity of learning fixed-structure Bayesian networks

    Sanjoy Dasgupta. The sample complexity of learning fixed-structure Bayesian networks. Machine Learning, 29 0 (2-3): 0 165--180, 1997

    1997

  10. [18]

    J. Edmonds. Optimum branchings. Journal of Research of the National Bureau of Standards, Section B, 71: 0 233--240, 1967

    1967

  11. [19]

    Attribute-efficient and non-adaptive learning of parities and DNF expressions

    Vitaly Feldman. Attribute-efficient and non-adaptive learning of parities and DNF expressions. Journal of Machine Learning Research, 8: 0 1431--1460, 2007

    2007

  12. [20]

    Learning DNF expressions from Fourier spectrum

    Vitaly Feldman. Learning DNF expressions from Fourier spectrum. In Shie Mannor, Nathan Srebro, and Robert C. Williamson, editors, Proceedings of the 25th Annual Conference on Learning Theory, volume 23 of Proceedings of Machine Learning Research, pages 17.1--17.19, 2012

    2012

  13. [21]

    On agnostic learning of parities, monomials, and halfspaces

    Vitaly Feldman, Parikshit Gopalan, Subhash Khot, and Ashok Kumar Ponnuswami. On agnostic learning of parities, monomials, and halfspaces. SIAM Journal on Computing , 39 0 (2): 0 606--645, January 2009

    2009

  14. [22]

    Improved learning of AC ^0 functions

    Merrick L Furst, Jeffrey C Jackson, and Sean W Smith. Improved learning of AC ^0 functions. In Proceedings of the Annual Conference on Learning Theory (COLT), pages 317--325, 1991

    1991

  15. [23]

    Efficient algorithms for finding minimum spanning trees in undirected and directed graphs

    H N Gabow, Z Galil, T Spencer, and R E Tarjan. Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica, 6 0 (2): 0 109–122, 1986

    1986

  16. [24]

    Goldreich and L

    O. Goldreich and L. A. Levin. A hard-core predicate for all one-way functions. In Proceedings of the twenty-first annual ACM symposium on Theory of computing, pages 25--32. ACM Press, 1989

    1989

  17. [25]

    Finding relevant information via a discrete Fourier expansion

    Mohsen Heidari, Jithin Sreedharan, Gil I Shamir, and Wojciech Szpankowski. Finding relevant information via a discrete Fourier expansion. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of...

    2021

  18. [26]

    Sreedharan, Gil Shamir, and Wojciech Szpankowski

    Mohsen Heidari, Jithin K. Sreedharan, Gil Shamir, and Wojciech Szpankowski. Sufficiently informative and relevant features: An information-theoretic and Fourier -based characterization. IEEE Transactions on Information Theory, 68 0 (9): 0 6063--6077, September 2022

    2022

  19. [27]

    Servedio

    Lisa Hellerstein, Devorah Kletenik, Linda Sellie, and Rocco A. Servedio. Tight bounds on proper equivalence query learning of DNF . In The 25th Annual Conference on Learning Theory, pages 31.1--31.18, 2012

    2012

  20. [28]

    A class of statistics with asymptotically normal distribution

    Wassily Hoeffding. A class of statistics with asymptotically normal distribution. The Annals of Mathematical Statistics, 19 0 (3): 0 293--325, 1948

    1948

  21. [29]

    Learning and robust learning of product distributions

    Klaus - Uwe H \" o ffgen. Learning and robust learning of product distributions. In Lenny Pitt, editor, Proceedings of the Sixth Annual ACM Conference on Computational Learning Theory , pages 77--83. ACM , 1993

    1993

  22. [30]

    An efficient membership-query algorithm for learning DNF with respect to the uniform distribution

    Jeffrey C Jackson. An efficient membership-query algorithm for learning DNF with respect to the uniform distribution. Journal of Computer and System Sciences, 55 0 (3): 0 414--440, December 1997

    1997

  23. [31]

    Klivans, Yishay Mansour, and Rocco A

    Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour, and Rocco A. Servedio. Agnostically learning halfspaces. SIAM Journal on Computing , 37 0 (6): 0 1777--1805, January 2008

    2008

  24. [32]

    Learning and smoothed analysis

    Adam Tauman Kalai, Alex Samorodnitsky, and Shang-Hua Teng. Learning and smoothed analysis. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 395--404. IEEE, October 2009

    2009

  25. [33]

    Kearns, Robert E

    Michael J. Kearns, Robert E. Schapire, and Linda M. Sellie. Toward efficient agnostic learning. Machine Learning, 17 0 (2-3): 0 115--141, 1994

    1994

  26. [34]

    On using the Fourier transform to learn disjoint DNF

    Roni Khardon. On using the Fourier transform to learn disjoint DNF . Information Processing Letters, 49 0 (5): 0 219--222, 1994

    1994

  27. [35]

    Klivans and Rocco A

    Adam R. Klivans and Rocco A. Servedio. Learning DNF in time 2\( ^ \ o (n\( ^ 1/3 \)) \). Journal of Computer and System Sciences, 68 0 (2): 0 303--318, 2004

    2004

  28. [36]

    Probabilistic Graphical Models - Principles and Techniques

    Daphne Koller and Nir Friedman. Probabilistic Graphical Models - Principles and Techniques. MIT Press, 2009

    2009

  29. [37]

    A simple algorithm for learning O (log n)-term DNF

    Eyal Kushilevitz. A simple algorithm for learning O (log n)-term DNF . In Proceedings of the Ninth Annual Conference on Computational Learning Theory, pages 266--269, 1996

    1996

  30. [38]

    Learning decision trees using the Fourier spectrum

    Eyal Kushilevitz and Yishay Mansour. Learning decision trees using the Fourier spectrum. SIAM Journal on Computing, 22 0 (6): 0 1331--1348, December 1993

    1993

  31. [39]

    Constant depth circuits, F ourier transform, and learnability

    Nathan Linial, Yishay Mansour, and Noam Nisan. Constant depth circuits, F ourier transform, and learnability. J. ACM, 40 0 (3): 0 607--620, 1993

    1993

  32. [40]

    Y. Mansour. An O (n log log n) learning algorithm for DNF under the uniform distribution. Journal of Computer and System Sciences, 50 0 (3): 0 543--550, June 1995

    1995

  33. [41]

    Analysis of Boolean functions

    Ryan O'Donnell. Analysis of Boolean functions. Cambridge University Press, 2014

    2014

  34. [42]

    Probabilistic reasoning in intelligent systems - networks of plausible inference

    Judea Pearl. Probabilistic reasoning in intelligent systems - networks of plausible inference. Morgan Kaufmann series in representation and reasoning. Morgan Kaufmann, 1989

    1989

  35. [43]

    Learning monotone log-term DNF formulas under the uniform distribution

    Yoshifumi Sakai and Akira Maruoka. Learning monotone log-term DNF formulas under the uniform distribution. Theory of Computing Systems, 33 0 (1): 0 17--33, 2000

    2000

  36. [44]

    f -divergence inequalities

    Igal Sason and Sergio Verdú. f -divergence inequalities. IEEE Transactions on Information Theory, 62 0 (11): 0 5973--6006, November 2015

    2015

  37. [45]

    Servedio

    Rocco A. Servedio. On learning monotone DNF under product distributions. Information and Computation, 193 0 (1): 0 57--74, 2004

    2004

  38. [46]

    Sensitivity estimates for nonlinear mathematical models

    Ilya M Sobol. Sensitivity estimates for nonlinear mathematical models. Mathematical modelling and computational experiments, 1 0 (4): 0 407--414, 1993

    1993

  39. [47]

    L. G. Valiant. A theory of the learnable. Communications of the ACM , 27 0 (11): 0 1134--1142, November 1984

    1984

  40. [48]

    Leslie G. Valiant. Learning disjunction of conjunctions. In Proceedings of the 9th International Joint Conference on Artificial Intelligence, pages 560--566. Morgan Kaufmann, 1985

    1985

  41. [49]

    Verbeurgt

    Karsten A. Verbeurgt. Learning DNF under the uniform distribution in quasi-polynomial time. In Proceedings of the Third Annual Workshop on Computational Learning Theory, COLT , pages 314--326, 1990

    1990

  42. [50]

    A Brief Introduction to Fourier Analysis on the Boolean Cube

    Ronald de Wolf. A Brief Introduction to Fourier Analysis on the Boolean Cube . Number 1 in Graduate Surveys. Theory of Computing Library, 2008

    2008

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.