Polynomial-Time Population Recovery under Random-Transposition Noise

We give a polynomial-time algorithm for sparse population recovery under continuous-time random-transposition noise. For every fixed known rational noise time c >= 0, an arbitrary unknown distribution supported on at most k words in A^n can be recovered to latent l1 error epsilon with polynomial sample count and worst-case bit time in n, |A|, k, 1/epsilon, and log(1/delta). No minimum mixing weight, known support, or separation is required. The main structural result is a positive, efficiently samplable transformation from interchange noise into independent binary-symmetric observations of arbitrary coordinate predicates. Its construction uses a tracked-particle extension and a marked-spanning-tree estimator for connected Duhamel coefficients, together with a specialization of randomized polymer-tree methods. We also prove an nOmega(log k) sample lower bound for sparse permutation populations at an explicit Theta(n log n) transposition time. Exact binary-word lower bounds show that the polynomial degree must depend on the fixed noise time. The upper theorem has mean c(n-1)/2 nontrivial swaps and does not assert a uniform polynomial bound when c grows with n.