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

CREATORBertrand Even and Christophe Giraud and Nicolas Verzelen
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE263 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-07946

Browse the full library · About the Tower of Babel