Computational barriers for permutation-based problems, and cumulants of weakly dependent random variables
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916837361451008 |
|---|---|
| author | Even, Bertrand Giraud, Christophe Verzelen, Nicolas |
| author_facet | Even, Bertrand Giraud, Christophe Verzelen, Nicolas |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_07946 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Computational barriers for permutation-based problems, and cumulants of weakly dependent random variables Even, Bertrand Giraud, Christophe Verzelen, Nicolas Statistics Theory 68Q17 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. |
| title | Computational barriers for permutation-based problems, and cumulants of weakly dependent random variables |
| topic | Statistics Theory 68Q17 |
| url | https://arxiv.org/abs/2507.07946 |