标题： 基于排列的问题的计算障碍以及弱相依随机变量的累积量 显示英文标题

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

摘要： 在许多高维问题中，多项式时间算法无法达到在无计算约束下可实现的统计极限。 探测多项式时间算法极限的一种强大方法是研究低次多项式的性能。 arXiv:2008.02269 的开创性工作将低次下界与多变量累积量联系起来。 先前的工作 arXiv:2308.15728, arXiv:2506.13647 利用潜在变量之间的独立性来限制累积量。 然而，对于缺乏独立性的潜在结构问题，如涉及随机排列的问题，此类方法会失效。 为了解决这一重要限制，我们开发了一种技术，在弱依赖条件下（如无放回抽样或随机排列产生的依赖）对累积量进行上界估计。 为了展示我们方法的有效性，我们在多个特征匹配和序列问题中发现了统计-计算差距的证据。 显示英文摘要

摘要： 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 arXiv:2008.02269 connects low-degree lower bounds to multivariate cumulants. Prior works arXiv:2308.15728, arXiv:2506.13647 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.