  We study the problem of learning an unknown mixture of $k$ rankings over $n$
elements, given access to noisy samples drawn from the unknown mixture. We
consider a range of different noise models, including natural variants of the
"heat kernel" noise framework and the Mallows model. For each of these noise
models we give an algorithm which, under mild assumptions, learns the unknown
mixture to high accuracy and runs in $n^{O(\log k)}$ time. The best previous
algorithms for closely related problems have running times which are
exponential in $k$.
