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
| CREATOR | Deeparnab Chakrabarty, Xi Chen, Simeon Ristic, C. Seshadhri, Erik Waingarten |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 78 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-16355