# DNF Learning via Locally Mixing Random Walks

arXiv: https://arxiv.org/abs/2505.18839 · HTML: https://mlsanity.com/paper/2505.18839/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 May 2025.

## Built on by (most cited first, 2 of 2)

- [Positive Distribution Shift as a Framework for Understanding Tractable Learning](https://mlsanity.com/paper/2602.08907/) (2026)
- [Learning CNF formulas from uniform random solutions in the local lemma regime](https://mlsanity.com/paper/2511.02487/) (2025)

## Abstract (arXiv)

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,1n. (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 = T1 vee cdots vee Ts over 0,1n and any unknown distribution D over 0,1n, our algorithm, which uses membership queries and random examples from D, runs in textsfquasipoly(n,s) time and outputs a list L of candidate terms such that with high probability some term Ti of f belongs to L. (2) We then use result (1) to give a textsfquasipoly(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.