Computational barriers for permutation-based problems, and cumulants of weakly dependent random variables
Bertrand Even and Christophe Giraud and Nicolas Verzelen · 2025
Read Computational barriers for permutation-based problems, and cumulants of weakly dependent random variables by Bertrand Even and Christophe Giraud and Nicolas Verzelen (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-07946.txt.
Description
Bertrand Even, Christophe Giraud, and Nicolas Verzelen tackled a hard question in 2025: when can fast methods not reach the best possible results? They study low-degree methods, a common way to test the limits of fast computing. Past work relied on parts of the data being free of each other, which fails for tasks built on random shuffles.
The team built a new way to bound a key measure when parts depend on each other in weak ways. Cases such as sampling without putting items back are covered. They then use the tool on matching tasks and on ordering tasks. Both show signs of a gap between what is possible in theory and what fast methods can do.
Catalog record
| CREATOR | Bertrand Even and Christophe Giraud and Nicolas Verzelen |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 263 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-07946