On the Advantage of Adaptivity for Sampling with Cell Probes

2026/05/13 by Farzan Byramji, Daniel M. Kane, Jackson Morris +1
#cs.CC #cs.DS

paper · pdf

Abstract

We construct an explicit distribution D over \0,1\^N 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 \widetildeΩ(N) non-adaptive cell probes to generate a distribution with total variation distance less than 1-o(1) from D. This provides a 2-vs-\widetildeΩ(N) separation for sampling with adaptive versus non-adaptive cell probes, improving upon the 2-vs-\widetildeΩ(log N) separation of Yu and Zhan (ITCS '24) and the (log N)^O(1)-vs-N^Ω(1) separation of Alekseev, Göös, Myasnikov, Riazanov, and Sokolov (STOC '26).

Citations

• Hard-to-Sample Distributions from Robust Extractors
• Unconditional Quantum Advantage for Sampling with Shallow Circuits

Related

• Sampling Permutations with Cell Probes is Hard
• On High-Resolution Adaptive Sampling of Deterministic Signals
• Derandomization of Cell Sampling
• Distilled Sensing: Adaptive Sampling for Sparse Detection and Estimation
• AdaptiveBandit: A multi-armed bandit framework for adaptive sampling in\n molecular simulations