DNF Learning via Locally Mixing Random Walks

Josh Alman; Rocco A. Servedio; Shivam Nadimpalli; Shyamal Patel

REVIEW 3 major objections 4 minor 47 references

DNF Learning via Locally Mixing Random Walks

T0 review · 3 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 Locally mixing random walks yield the first quasipolynomial-time distribution-free algorithms for list-decoding DNF terms and for learning equal-length-term DNFs.

desk verdict Local mixing theorem is a promising new tool; the exact-DNF proof has a real gap in Find-Far-Point. read the letter →

arxiv 2505.18839 v1 pith:UC3OMTLP submitted 2025-05-24 cs.DS

Josh Alman , Shivam Nadimpalli , Shyamal Patel , Rocco A. Servedio This is my paper

classification cs.DS MSC 68Q3205C81

keywords DNFlearningdistribution-freePACmembershipquerieslocallymixingrandomwalksexpandergraphshigher-orderCheegerinequalitylist-decodingexact-DNF

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 tries to break distribution-free PAC learning of DNF formulas, Boolean formulas that are ORs of ANDs of literals, a problem that has resisted efficient algorithms since the PAC model was formulated, with the best known runtimes exponential in the number of terms or in $n^{1/3}$. Its route is a new graph-theoretic fact: although the graph whose vertices are the satisfying assignments of a DNF may be disconnected and globally non-mixing, a random walk from any satisfying input has a non-negligible (quasipolynomially small) chance of quickly becoming nearly uniform on the satisfying assignments of a single term. That locally mixing random walk theorem powers a quasipolynomial-time algorithm, running in about $1/p + (ns)^{O(\log(ns))}$ steps, that outputs a short list of candidate terms provably containing a true term of any unknown DNF under any distribution, and a second algorithm, running in $\exp(\log^{O(1)}(ns)) \cdot \mathrm{poly}(1/\varepsilon)$, that fully learns DNFs in which every term has the same number of literals, using a DNF hypothesis of size $O(s\log(1/\varepsilon))$. If the paper is right, these are the first quasipolynomial-time results for understanding arbitrary DNF terms and for learning equal-length-term DNFs in the distribution-free membership-query model.

What carries the argument

The load-bearing object is the $(p,\varepsilon)$-local mixing time (Definition 23 in the text), the smallest $t$ such that a $t$-step random walk from a given vertex has an event of probability at least $p$ after which its endpoint is within $\varepsilon$ total variation distance of uniform on some single cover set $A_i$. The Local Mixing Theorem (Definition 24) bounds this time by $(s\,d_{\max}\log|V|\log(1/\varepsilon)/\theta)^{O(\log s)}$ with $p=(s\,d_{\max}\log|V|\log(1/\varepsilon)/\theta)^{-\Omega(\log s)}$. The proof first reduces overlapping covers to disjoint ones via disjointification, then builds a hierarchy of merged thick components: at each level, cover sets joined by enough edges are merged, and a Fibonacci-type growth lemma (Lemma 45) shows the component containing the largest set grows exponentially in member-count as the thickness level rises, forcing termination after $O(\log s)$ levels. Higher-order Cheeger inequalities keep the expansion loss from squaring at each merge, and escape-probability estimates certify that most vertices of a low-conductance high-expansion set locally mix. In the learning applications this theorem generates the candidate-term lists; the exact-DNF algorithm additionally wraps it in a boosting loop with a prune step (deleting terms that fail random membership tests), an expand step (adding all width-$k$ terms within polylog distance), and a recursive far-point finder whose recursion tree provably has quasipolynomial size.

What would settle it

A concrete disproof would be a family of disjoint-cover graphs that violates the Fibonacci growth lemma: Lemma 45 asserts that the $\ell$-thick component containing the largest set in any disjoint $\theta$-cover contains at least $F_\ell$ sets, where $F_\ell$ is the $\ell$-th Fibonacci number. Build a cover, for instance a long path of equal-size expanders joined by threshold-weight edges, in which each merge level adds only one new set, so the component grows linearly instead of exponentially; that would break the $O(\log s)$ termination of the recursion, and with it the Local Mixing Theorem and both DNF learning theorems.

Watch

Extended reading notes

Core claim

The paper's central discovery is the Local Mixing Theorem: in any graph of maximum degree $d_{\max}$ whose vertices are covered by sets $A_1,\ldots,A_s$ with each induced subgraph $G[A_i]$ a $\theta$-expander, every starting vertex $v$ admits an event $E_v$ of probability at least $(s\,d_{\max}\log|V|\log(1/\varepsilon)/\theta)^{-O(\log s)}$ after which a lazy random walk of length $(s\,d_{\max}\log|V|\log(1/\varepsilon)/\theta)^{O(\log s)}$ starting at $v$ ends, conditioned on $E_v$, within total variation distance $\varepsilon$ of the uniform distribution on some single set $A_j$. The authors apply this to the subgraph of the Boolean hypercube induced by the satisfying assignments of an unknown $s$-term DNF $f$, where each term's satisfying assignments form a hypercube (hence an expander) and random walks can be simulated with membership queries. The first learning result, Theorem 1 (Definition 1 in the text), is a list-decoding algorithm that in $1/p + (ns)^{O(\log(ns))}$ time, for any distribution $D$, outputs a list of at most $(ns)^{O(\log(ns))}$ terms that contains a true term of $f$ with probability at least $0.99$. The second, Theorem 3 (Definition 56 in the text), learns any size-$s$ exact-DNF, meaning every term has exactly $k$ literals, to accuracy $\varepsilon$ in $\exp(\log^{O(1)}(ns))\cdot\mathrm{poly}(1/\varepsilon)$ time with a DNF hypothesis of $O(s\log(1/\varepsilon))$ terms, by repeatedly generating term lists, pruning implausible candidates, expanding the list to nearby terms, and hunting for far points that force discovery of a new true term.

Load-bearing premise

Both learning theorems rest entirely on the Local Mixing Theorem as a statement about arbitrary graphs: from every vertex of any graph covered by a small number of expanders, a lazy random walk of quasipolynomial length has probability at least $(s\,d_{\max}\log|V|\log(1/\varepsilon)/\theta)^{-O(\log s)}$ of ending nearly uniform on one single expander, and if that graph fact fails for any family of covered graphs, with much smaller event probabilities or exponentially long required walks, the DNF results collapse with it.

Editorial extensions

If this is right

A true term of any unknown $s$-term DNF can be found inside a list of at most $(ns)^{O(\log(ns))}$ candidates in $1/p + (ns)^{O(\log(ns))}$ time under an arbitrary unknown distribution using membership queries, with success probability at least $0.99$, which the paper describes as the first quasipolynomial-time nontrivial algorithm for general DNF in the distribution-free model.
Size-$s$ exact-DNF formulas become learnable to accuracy $\varepsilon$ in $\exp(\log^{O(1)}(ns))\cdot\mathrm{poly}(1/\varepsilon)$ time, with a DNF hypothesis of $O(s\log(1/\varepsilon))$ terms, improving on the previous best $\mathrm{poly}(n,2^s)$ and $2^{\widetilde{O}(n^{1/3}\log n\log s)}$ algorithms for this class.
The same theorem covers approximately exact DNFs, where term lengths differ by at most an additive polylog$(n,s)$.
The Local Mixing Theorem applies to arbitrary graphs, not just DNF-induced ones: any graph covered by $s$ expanders, even a disconnected one, has local mixing time $(s\,d_{\max}\log|V|\log(1/\varepsilon)/\theta)^{O(\log s)}$ from every starting vertex.

Reading between the lines

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

The list-then-prune template should transfer to other Boolean classes whose satisfying region is covered by few well-connected subgraphs, such as decision trees, read-once formulas, or threshold level sets, because the local mixing theorem needs only the cover structure; the paper's own far-point obstacle in Section 9.2 indicates why removing the equal-length assumption requires a genuinely new id
The proved exponent grows with the $O(\log s)$ layers of the thickness recursion, so compressing that recursion is a natural route toward runtimes like $2^{O(\log^2(ns))}$; conversely, the Fibonacci lemma supplies a concrete lower-bound target, namely families of covers whose thick components provably grow only polynomially.
A direct stress test would run the list-decoding algorithm on random $s$-term DNFs under skewed product distributions and compare the empirical probability of landing on a true term against the $(ns)^{-O(\log s)}$ event-probability bound, revealing whether the hidden constants in the local mixing analysis are tight.

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.

Desk Editor's Note

read the letter

Two quick takes. The local mixing theorem is the genuinely new thing here. It says a graph covered by s expanders has, from every vertex, a non-negligible probability of mixing on one of the expander sets in quasipolynomial time, and the proof via thick components, higher-order Cheeger, and Spielman–Teng is a real piece of work. I didn't find a hole in that part, and the single-term list-decoding result follows from it by a natural DDS14-style argument. If the local mixing theorem holds, that result is solid and worth having on its own.

The exact-DNF learning theorem is a different story. Its proof goes through Find-Far-Point, and there is a load-bearing gap in Section 9.4. The stress-test note is on target. In Lemma 69, the proof says each index in (T\T*)|_F has a probability of being set to falsify the corresponding literal in T, but item (iii) freezes z_F = y_F. That sentence is wrong. The conclusion might still be salvageable—frozen coordinates that differ from T* already falsify the term—but not by the argument in the paper. The bigger problem is Lemma 79. It applies Lemma 70 using only a bound on the difference between T and T* on A⊔S, while Lemma 70 requires a global bound on |T\T*|. These are not equivalent, especially when |S| is large, and the existence of super-popular coordinates outside A⊔S is not established. Since Find-Far-Point is what lets Exact-Learn make progress on missing terms, Theorem 56 is not proven as written. There are also smaller text issues: Algorithm 7's noise branch appears to keep y_i in both cases, and the 0.01ε per-iteration progress probability in the proof of Theorem 56 is asserted without derivation.

So: a serious paper, with an interesting and likely reusable tool, and a plausible but currently unproven second main theorem. I'd send it to a good referee, with instructions to check the Local Mixing Theorem carefully and to demand a fix for Section 9.4. I would not cite Theorem 56 as established, but the local mixing theorem is worth keeping in mind.

Referee Report

3 major / 4 minor

Summary. The paper develops a new graph-theoretic tool, a 'locally mixing random walk' theorem for graphs covered by expanders, and applies it to distribution-free PAC learning of DNF formulas with membership queries. The first application is a quasipolynomial-time algorithm that, given any satisfying assignment of an unknown s-term DNF, outputs a list of terms containing one true term of the DNF. The second, stronger application is a quasipolynomial-time PAC+MQ algorithm that learns s-term exact-DNF (all terms have the same number of literals) using a DNF hypothesis of size O(s log(1/ε)). The exact-DNF algorithm works by maintaining a list of candidate terms, expanding and pruning it, and using a routine Find-Far-Point to find satisfying assignments far from the current list when progress stalls. The locally mixing theorem is proved via higher-order Cheeger inequalities, a disjointification step, and a thick-component recursion.

Significance. If correct, the exact-DNF result would be the first quasipolynomial-time distribution-free PAC+MQ algorithm for a rich subclass of DNF formulas, and the term list-decoding result would be a novel distribution-free guarantee enabled by a new random-walk mixing notion. The locally mixing theorem itself, stated for arbitrary graphs covered by expanders, is a plausible standalone contribution and is supported by a substantial chain of lemmas. However, the correctness of the exact-DNF algorithm is not established: the proof of the central far-point routine contains a demonstrably false lemma and an invalid reduction, and these are load-bearing for Theorem 56. The local-mixing portion and the list-decoding application appear less affected, but the paper's headline learning claim requires major repair.

major comments (3)

[Section 9.4.1, Lemma 69 and Algorithm 7] Lemma 69 is false as stated. Item (iii) and Step 2(b) of Algorithm 7 freeze all coordinates in F, so the proof's assertion that an index in (T\T*)|_F has positive probability of being 'set so as to falsify the corresponding literal in T' cannot be correct: those coordinates are never randomized. Concretely, for sufficiently large n and s, set k = |F| + Δ with Δ = 1000 log^{300}(ns), let y be the all-ones string, let T* = (∧_{i∈F1} x_i) ∧ (∧_{j∈G} x_j) where F1 ⊆ F has size Δ and G ⊆ [n]\F has size |F|, and let T = (∧_{i∈F} x_i) ∧ (∧_{j∈G'} x_j) where G' ⊆ [n]\F has size Δ. Both T and T* have size k and are satisfied by y, and |T*_F| = Δ ≤ 2(k-|F|). Since |T_F \ T*_F| ≥ |F|-Δ ≥ (k-|F|)/log(ns), Lemma 69(ii) would require d_sat(z,T) ≥ log^{150}(s); but Noise outputs z = y on F, and y already satisfies T, so d_sat(z,T) = 0. Thus the filtering of W' in Step 5(a)(iv) is unjustified, and the correctness of Find-Far-Point (Lemma 65, hence Theorem 56) is not established.
[Section 9.4.2, Lemma 79 and Lemma 70] The application of Lemma 70 inside Lemma 79 is invalid. Lemma 79 only establishes, for surviving terms T in W', a lower bound on |T_{A⊔S}| relative to |T*_{A⊔S}|, or equivalently via Lemma 69 a bound on |T_{A⊔S} \ T*_{A⊔S}|. Lemma 70 requires the global bound |T \ T*| ≤ 2a/log(ns) for a = |T*| (or for a restricted term, with matching restricted universe). These conditions are not equivalent: a term may agree with T* on all of A⊔S and still have arbitrarily many literals outside A⊔S that are not in T*, and if z happens to satisfy those literals, the term remains in W'. When |S| is large, k-|S| is small and the restricted-overlap condition becomes nearly vacuous, so the global difference bound is exactly the missing control. Moreover, if one applies Lemma 70 to the restricted term T*_{A⊔S}, the coordinates it certifies as super-popular lie in A⊔S, whereas Step 5(a)(v) requires super-popular coordinates in [n]\(A⊔S). Consequently, the existence of (z,W')-super-popular coordinates is not proved, and the main branch cut argument fails.
[Section 9.3, proof of Theorem 56] The proof asserts that in each for-loop iteration, 'with probability at least 0.01ε, z satisfies a term T⋆∈f\L', and that this event is independent enough for the subsequent Azuma bound. No derivation of this probability is given. The draw y ~ D|f=1 need not land on a true term missing from L with probability Ω(ε); the probability is bounded only if the total D-mass of missing true terms is Ω(ε), and that condition is not established. The claimed per-iteration progress probability is therefore unsupported, which is another load-bearing gap in the proof of Theorem 56.

minor comments (4)

[Throughout] Main results and lemmas are repeatedly labelled 'Definition' (e.g., Definition 1, Definition 3, Definition 56, Definition 65) instead of 'Theorem' or 'Lemma'; this appears to be a systematic cross-referencing error and should be fixed.
[Algorithm 7, Step 2(a)] The noise step sets z_i to be equal to y_i with probability log^{300}(ns)/(k-|F|) and to y_i otherwise, so both branches leave z_i unchanged and the algorithm never flips a coordinate. The surrounding proof indicates the intended behavior is to set z_i = 1-y_i with the stated probability.
[Algorithm 7, Step 2] The loop variable i is used both for the iteration counter and for the coordinate index inside the loop; using a separate variable for the iteration count would improve clarity.
[Section 9.4.1] The statement of Lemma 69 should make explicit that the condition |T|_F \ T*|_F| refers to the number of literals of T restricted to F that are not literals of T* restricted to F; the current notation is easy to misread as a set difference of terms rather than a counting condition.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main theorems are derived from a standalone local-mixing theorem over expander-covered graphs, and the DNF applications re-derive their list-recovery claims internally rather than importing them by citation.

full rationale

The derivation chain is: Theorem 24 (local mixing) is proved in Sections 3 through 6 from Cheeger's inequality, the higher-order Cheeger inequality of [KLL+13] and [LRTV12], and Spielman-Teng escape bounds. These are external supporting facts, not the target DNF results. Theorem 1 and Theorem 56 are derived by instantiating the graph as the subgraph induced by the satisfying assignments of the DNF; each term induces a subcube, a standard expander, and the 'largest term satisfied by drawn points' claim is proved directly in the proof of Lemma 63 and again in the final Section B proof, rather than merely cited. The only self-citation with content overlap is [DDS14], where one author of the present paper is a co-author, but it is used as background and motivation and for an easy observation that is re-proved internally. That citation is not load-bearing: the final proof of Theorem 1 and the exact-DNF proof in Section 9 do not require accepting [DDS14] as a black box. No fitted parameter is renamed as a prediction, no uniqueness theorem is imported from the authors' prior work, and no ansatz is smuggled in by citation. The local-mixing theorem itself is a new graph-theoretic statement proven from stated assumptions, and the DNF algorithms are evaluated against external distribution-free PAC+MQ benchmarks. Consequently there is no circular step to exhibit, and the paper is self-contained with respect to its central claims. Any concern about the correctness of Lemma 69 or the Find-Far-Point proof is a proof-gap or technical-validity issue, not an input-output circularity.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

The paper introduces no new physical or abstract entities; it defines new algorithmic concepts (local mixing time, far points, thick components) as mathematical tools. The free parameters are hand-chosen constants in thresholds and exponents, not data-fitted values.

free parameters (3)

lambda exponent -1000 = -1000 in Eq. (6)
The definition lambda = (1000 s dmax theta^{-1} log|G| log(1/epsilon))^{-1000} uses hand-chosen constants that drive the local mixing proof; different exponents would still yield quasipolynomial bounds.
far-point thresholds log^3(ns), log^100(ns), log^1000(ns) = exponents 3, 100, 1000
Used in Find-Far-Point and Lemma 64; they are chosen to make union bounds and couplings work, not fitted to data.
popular-coordinate fractions 0.005 and 0.01 = 0.005, 0.01
Definition 67 defines popular and super-popular coordinates with these thresholds; they affect the recursion tree bound but are arbitrary constants.

assumptions (4)

domain assumption Assumption 1 (nice graphs): each vertex has as many self-loops as edges to other vertices
Made at the start of Section 2.1 to convert standard random walks into lazy walks; the authors argue in Remark 25 it is without loss of generality for the main theorem.
standard math Higher-order Cheeger inequalities (Kwok et al., Louis et al.)
Used in Section 2.4 to avoid quadratic loss in expansion; Theorem 15 and Theorem 16 are quoted as known.
standard math Spielman-Teng local clustering observation (Lemma 17)
Used in Lemma 33 and Lemma 18 to bound escape probabilities; quoted from ST13.
domain assumption A random walk on G[f^{-1}(1)] can be simulated with membership queries plus one initial positive example from D
Section 1.3 and Section 8 implicitly rely on this: from a positive example the walk flips coordinates and queries f, staying put when f=0. This is standard in membership-query learning.

how reviews work

0 comments

Cite this review

Pith. "Pith review of DNF Learning via Locally Mixing Random Walks." pith.science (2026). https://pith.science/paper/UC3OMTLP

@misc{pith2026250518839,
  author       = {Pith},
  title        = {Pith review of: DNF Learning via Locally Mixing Random Walks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UC3OMTLP}},
  note         = {Machine review of arXiv:2505.18839}
}

abstract

We give two results on PAC learning DNF formulas using membership queries in the challenging "distribution-free" learning framework, where learning algorithms must succeed for an arbitrary and unknown distribution over $\{0,1\}^n$. (1) We first give a quasi-polynomial time "list-decoding" algorithm for learning a single term of an unknown DNF formula. More precisely, for any target $s$-term DNF formula $f = T_1 \vee \cdots \vee T_s$ over $\{0,1\}^n$ and any unknown distribution $D$ over $\{0,1\}^n$, our algorithm, which uses membership queries and random examples from $D$, runs in $\textsf{quasipoly}(n,s)$ time and outputs a list $L$ of candidate terms such that with high probability some term $T_i$ of $f$ belongs to $L$. (2) We then use result (1) to give a $\textsf{quasipoly}(n,s)$-time algorithm, in the distribution-free PAC learning model with membership queries, for learning the class of size-$s$ DNFs in which all terms have the same size. Our algorithm learns using a DNF hypothesis. The key tool used to establish result (1) is a new result on "locally mixing random walks," which, roughly speaking, shows that a random walk on a graph that is covered by a small number of expanders has a non-negligible probability of mixing quickly in a subset of these expanders.

Figures

Figures reproduced from arXiv: 2505.18839 by the authors.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

47 extracted references · 45 canonical work pages

[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 J. Comput. , 27(6):1515--1530, 1998

work page 1998
[2]

Exact learning of read-twice DNF formulas (extended abstract)

Howard Aizenstein and Leonard Pitt. Exact learning of read-twice DNF formulas (extended abstract). In 32nd Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 1-4 October 1991 , pages 170--179, 1991

work page 1991
[3]

Aizenstein and L

H. Aizenstein and L. Pitt. On the learnability of disjunctive normal form formulas. Machine Learning , 19:183--208, 1995

work page 1995
[4]

Beimel, F

A. Beimel, F. Bergadano, N. Bshouty, E. Kushilevitz, and S. Varricchio. Learning functions represented as multiplicity automata. J. ACM , 47(3):506--530, 2000

work page 2000
[5]

Linear time deterministic learning of k-term DNF

Ulf Berggren. Linear time deterministic learning of k-term DNF . In Proceedings of the Sixth Annual ACM Conference on Computational Learning Theory (COLT) , pages 37--40, 1993

work page 1993
[6]

Bshouty and J

N. Bshouty and J. Jackson. Learning DNF over the uniform distribution using a quantum example oracle. SIAM J. on Computing , 28(3):1136--1153, 1999

work page 1999
[7]

Bshouty, J

N. Bshouty, J. Jackson, and C. Tamon. More efficient PAC learning of DNF with membership queries under the uniform distribution. In Proceedings of the Twelfth Annual Conference on Computational Learning Theory , pages 286--295, 1999

work page 1999
[8]

Bshouty, E

N. Bshouty, E. Mossel, R. O'Donnell, and R. Servedio. Learning DNF from Random Walks . Journal of Computer & System Sciences , 71(3):250--265, 2005

work page 2005

Show all 47 references

[9]

Blum and S

A. Blum and S. Rudich. Fast learning of k -term DNF formulas with queries. Journal of Computer and System Sciences , 51(3):367--373, 1995

1995
[10]

N. Bshouty. Exact learning via the monotone theory. Information and Computation , 123(1):146--153, 1995

1995
[11]

Nader H. Bshouty. A Subexponential Exact Learning Algorithm for DNF Using Equivalence Queries . Information Processing Letters , 59(1):37--39, 1996

1996
[12]

N. Bshouty. Simple learning algorithms using divide and conquer. Computational Complexity , 6:174--194, 1997

1997
[13]

Learning from satisfying assignments

Anindya De, Ilias Diakonikolas, and Rocco A Servedio. Learning from satisfying assignments. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms , pages 478--497. SIAM, 2014

2014
[14]

Efficient Read-Restricted Monotone CNF/DNF Dualization by Learning with Membership Queries

Carlos Domingo, Nina Mishra, and Leonard Pitt. Efficient Read-Restricted Monotone CNF/DNF Dualization by Learning with Membership Queries . Machine Learning , 37(1):89--110, 1999

1999
[15]

Optimally-smooth adaptive boosting and application to agnostic learning

Dmitry Gavinsky. Optimally-smooth adaptive boosting and application to agnostic learning. Journal of Machine Learning Research , 4:101--117, 2003

2003
[16]

Approximating the expansion profile and almost optimal local graph clustering

Shayan Oveis Gharan and Luca Trevisan. Approximating the expansion profile and almost optimal local graph clustering. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science , pages 187--196. IEEE, 2012

2012
[17]

T. Hancock. Learning 2 DNF formulas and k decision trees . In Proceedings of the Fourth Annual Workshop on Computational Learning Theory , pages 199--209, 1991

1991
[18]

Quantifying inductive bias: AI learning algorithms and valiant's learning framework

David Haussler. Quantifying inductive bias: AI learning algorithms and valiant's learning framework. Artif. Intell. , 36(2):177--221, 1988

1988
[19]

Haussler, M

D. Haussler, M. Kearns, N. Littlestone, and M. Warmuth. Equivalence of models for polynomial learnability. Information and Computation , 95(2):129--161, 1991

1991
[20]

Hancock and Y

T. Hancock and Y. Mansour. Learning monotone k - DNF formulas on product distributions. In Proceedings of the Fourth Annual Conference on Computational Learning Theory , pages 179--193, 1991

1991
[21]

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

1997
[22]

Jackson, H.K

J. Jackson, H.K. Lee, R. Servedio, and A. Wan. Learning Random Monotone DNF . Discrete Applied Mathematics , 159(5):259--271, 2011

2011
[23]

Jackson and R

J. Jackson and R. Servedio. On learning random DNF formulas under the uniform distribution. Theory of Computing , 2(8):147--172, 2006. (Preliminary version in RANDOM 2005)

2006
[24]

Jackson, C

J. Jackson, C. Tamon, and T. Yamakami. Quantum DNF learnability revisited. In Proceedings of the Eighth Annual International Conference on Computing and Combinatorics (COCOON) , pages 595--604, 2002

2002
[25]

R. Khardon. On using the F ourier transform to learn disjoint DNF . Information Processing Letters , 49:219--222, 1994

1994
[26]

Improved cheeger's inequality: Analysis of spectral partitioning algorithms through higher order spectral gap

Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, Shayan Oveis Gharan, and Luca Trevisan. Improved cheeger's inequality: Analysis of spectral partitioning algorithms through higher order spectral gap. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing , pages...

2013
[27]

Ku c era, A

L. Ku c era, A. Marchetti-Spaccamela, and M. Protassi. On learning monotone DNF formulae under uniform distributions. Information and Computation , 110:84--95, 1994

1994
[28]

Kushilevitz and D

E. Kushilevitz and D. Roth. On learning visual concepts and DNF formulae. In Proceedings of the Sixth Annual Conference on Computational Learning Theory , pages 317--326, 1993

1993
[29]

Klivans and R

A. Klivans and R. Servedio. Boosting and hard-core sets. Machine Learning , 53(3):217--238, 2003

2003
[30]

Klivans and R

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

2004
[31]

Kushilevitz

E. Kushilevitz. A simple algorithm for learning o( n) -term DNF . Information Processing Letters , 61(6):289--292, 1997

1997
[32]

Kearns and U

M. Kearns and U. Vazirani. An Introduction to Computational Learning Theory . MIT Press, Cambridge, MA, 1994

1994
[33]

Multiway spectral partitioning and higher-order cheeger inequalities

James R Lee, Shayan Oveis Gharan, and Luca Trevisan. Multiway spectral partitioning and higher-order cheeger inequalities. Journal of the ACM (JACM) , 61(6):1--30, 2014

2014
[34]

Locally stationary distributions: A framework for analyzing slow-mixing markov chains

Kuikui Liu, Sidhanth Mohanty, Prasad Raghavendra, Amit Rajaraman, and David X Wu. Locally stationary distributions: A framework for analyzing slow-mixing markov chains. arXiv preprint arXiv:2405.20849 , 2024

2024 arXiv
[35]

Levin and Y

D. Levin and Y. Peres. Markov Chains and Mixing Times, 2nd Revised Edition . American Mathematical society Press, 2017

2017
[36]

Many sparse cuts via higher eigenvalues

Anand Louis, Prasad Raghavendra, Prasad Tetali, and Santosh Vempala. Many sparse cuts via higher eigenvalues. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing , pages 1131--1140, 2012

2012
[37]

A greedy method for learning -DNF functions under the uniform distribution

Giulia Pagallo and David Haussler. A greedy method for learning -DNF functions under the uniform distribution . Technical report, University of California at Santa Cruz, UCSC-CRL-89-12, 1989

1989
[38]

Read-twice DNF formulas are properly learnable

Krishnan Pillaipakkamnatt and Vijay Raghavan. Read-twice DNF formulas are properly learnable. Inf. Comput. , 122(2):236--267, 1995

1995
[39]

L. Sellie. Learning Random Monotone DNF Under the Uniform Distribution . In Proc. 21st Colt , pages 181--192, 2008

2008
[40]

Exact learning of random dnf over the uniform distribution

Linda Sellie. Exact learning of random dnf over the uniform distribution. pages 45--54, 2009

2009
[41]

Servedio

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

2004
[42]

Sakai and A

Y. Sakai and A. Maruoka. Learning monotone log-term DNF formulas under the uniform distribution. Theory of Computing Systems , 33:17--33, 2000

2000
[43]

A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning

Daniel A Spielman and Shang-Hua Teng. A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning. SIAM Journal on computing , 42(1):1--26, 2013

2013
[44]

Tarui and T

J. Tarui and T. Tsukiji. Learning DNF by approximating inclusion-exclusion formulae. In Proceedings of the Fourteenth Conference on Computational Complexity , pages 215--220, 1999

1999
[45]

A theory of the learnable

Leslie Valiant. A theory of the learnable. Communications of the ACM , 27(11):1134--1142, 1984

1984
[46]

Verbeurgt

Karsten A. Verbeurgt. Learning DNF under the uniform distribution in quasi-polynomial time. In Mark A. Fulk, editor, Conference on Learning Theory , pages 314--326. Morgan Kaufmann, 1990

1990
[47]

Verbeurgt

K. Verbeurgt. Learning sub-classes of monotone DNF on the uniform distribution. In Proceedings of the Ninth Conference on Algorithmic Learning Theory , pages 385--399, 1998

1998

Pith tools

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

[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 J. Comput. , 27(6):1515--1530, 1998

work page 1998

[2] [2]

Exact learning of read-twice DNF formulas (extended abstract)

Howard Aizenstein and Leonard Pitt. Exact learning of read-twice DNF formulas (extended abstract). In 32nd Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 1-4 October 1991 , pages 170--179, 1991

work page 1991

[3] [3]

Aizenstein and L

H. Aizenstein and L. Pitt. On the learnability of disjunctive normal form formulas. Machine Learning , 19:183--208, 1995

work page 1995

[4] [4]

Beimel, F

A. Beimel, F. Bergadano, N. Bshouty, E. Kushilevitz, and S. Varricchio. Learning functions represented as multiplicity automata. J. ACM , 47(3):506--530, 2000

work page 2000

[5] [5]

Linear time deterministic learning of k-term DNF

Ulf Berggren. Linear time deterministic learning of k-term DNF . In Proceedings of the Sixth Annual ACM Conference on Computational Learning Theory (COLT) , pages 37--40, 1993

work page 1993

[6] [6]

Bshouty and J

N. Bshouty and J. Jackson. Learning DNF over the uniform distribution using a quantum example oracle. SIAM J. on Computing , 28(3):1136--1153, 1999

work page 1999

[7] [7]

Bshouty, J

N. Bshouty, J. Jackson, and C. Tamon. More efficient PAC learning of DNF with membership queries under the uniform distribution. In Proceedings of the Twelfth Annual Conference on Computational Learning Theory , pages 286--295, 1999

work page 1999

[8] [8]

Bshouty, E

N. Bshouty, E. Mossel, R. O'Donnell, and R. Servedio. Learning DNF from Random Walks . Journal of Computer & System Sciences , 71(3):250--265, 2005

work page 2005