Learning random monotone DNF (Q628302)

Learning polynomial-time disjunctive normal formulas from random samples is an open problem in learning theory, even with the uniform distribution. A special case is to learn monotone disjunctive normal formulas under the uniform distribution, which is the topic considered in this paper. By studying Fourier properties of monotone functions, the authors give a polynomial-time algorithm to solve an average-case version of this problem for learning monotone disjunctive normal formulas.