Beyond the Low-Degree Algorithm: Mixtures of Subcubes and Their Applications

Sitan Chen, Ankur Moitra

We introduce the problem of learning mixtures of $k$ subcubes over $\{0,1{\}}^n$, which contains many classic learning theory problems as a special case (and is itself a special case…