NeFut Logo NeFut
Admin Login

[CS.DS] The Advantage of Adaptivity in Sampling

Published at: 2026-07-27 22:00 Last updated: 2026-07-28 01:43
#algorithm #optimization #Data Structure

We construct an explicit distribution $\mathbf{D}$ that exhibits an essentially optimal separation between adaptive and non-adaptive cell-probe sampling. The distribution can be sampled exactly when each output bit is allowed two adaptive probes to an arbitrarily long sequence of independent uniform symbols from $[N]$.

In contrast, any non-adaptive sampler requires $\tilde{\Omega}(N)$ non-adaptive cell probes to generate a distribution with total variation distance less than $1-o(1)$ from $\mathbf{D}$. This provides a $2$-vs-$\tilde{\Omega}(N)$ separation for adaptive versus non-adaptive cell probes, improving upon the $2$-vs-$\tilde{\Omega}(\log N)$ separation of Yu and Zhan (ITCS '24) and the $(\log N)^{O(1)}$-vs-$N^{\Omega(1)}$ separation of Alekseev, G"o"os, Myasnikov, Riazanov, and Sokolov (STOC '26).

Original Source: https://arxiv.org/abs/2605.12873

[h] Back to Home