Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning

Deeparnab Chakrabarty, Xi Chen, Simeon Ristic, C. Seshadhri, Erik Waingarten · 2025

Read Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning by Deeparnab Chakrabarty, Xi Chen, Simeon Ristic, C. Seshadhri, Erik Waingarten (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-2502-16355.txt.

Description

Deeparnab Chakrabarty, Xi Chen, Simeon Ristic, Seshadhri, and Erik Waingarten settled the cost of testing monotonicity of high-dimensional distributions in 2025. Past work showed that plain sampling needs exponentially many samples. A stronger access model, subcube conditioning, lets a tester query random draws from any face of the cube.

Under that model the team proved matching upper and lower bounds: the query cost grows linearly in dimension, up to log factors. Their proof imports tools from directed isoperimetric inequalities, first used for functions, and extends a known inequality to real-valued maps. A side problem, testing uniformity among monotone distributions, was also settled: the promise of monotonicity barely helps.

Catalog record

CREATORDeeparnab Chakrabarty, Xi Chen, Simeon Ristic, C. Seshadhri, Erik Waingarten
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE78 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-16355

Browse the full library · About the Tower of Babel