2026-09-10T09:44:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27783 2026-09-09T12:19:38Z ddc:004 open_access

On the Advantage of Adaptivity for Sampling with Cell Probes Byramji, Farzan Kane, Daniel M. Morris, Jackson Ostuni, Anthony sampling lower bound cell probe model adaptive sampling We construct an explicit distribution 𝐃 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 Ω̃(N) non-adaptive cell probes to generate a distribution with total variation distance less than 1-o(1) from 𝐃. This provides a 2-vs-Ω̃(N) separation for sampling with adaptive versus non-adaptive cell probes, improving upon the 2-vs-Ω̃(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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Farzan Byramji and Daniel M. Kane and Jackson Morris and Anthony Ostuni 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.66 urn:nbn:de:0030-drops-277839 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.66 eng https://creativecommons.org/licenses/by/4.0/legalcode