Computational barriers for permutation-based problems, and cumulants of weakly dependent random variables

In many high-dimensional problems, polynomial-time algorithms fall short of achieving the statistical limits attainable without computational constraints. A powerful approach to probe the limits of polynomial-time algorithms is to study the performance of low-degree polynomials. The seminal work of [SW22] connects low-degree lower bounds to multivariate cumulants. Prior works [LG24, EGV25] leverage independence among latent variables to bound cumulants. However, such approaches break down for problems with latent structure lacking independence, such as those involving random permutations. To address this important restriction, we develop a technique to upper-bound cumulants under weak dependencies – such as those arising from sampling without replacement or random permutations. To show-case the effectiveness of our approach, we uncover evidence of statistical–computational gaps in multiple feature matching and in seriation problems.