On the Advantage of Adaptivity for Sampling with Cell Probes
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910214472597504 |
|---|---|
| author | Byramji, Farzan Kane, Daniel M. Morris, Jackson Ostuni, Anthony |
| author_facet | Byramji, Farzan Kane, Daniel M. Morris, Jackson Ostuni, Anthony |
| contents | We construct an explicit distribution $\mathbf{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 $\mathbf{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). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_12873 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On the Advantage of Adaptivity for Sampling with Cell Probes Byramji, Farzan Kane, Daniel M. Morris, Jackson Ostuni, Anthony Computational Complexity Data Structures and Algorithms We construct an explicit distribution $\mathbf{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 $\mathbf{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). |
| title | On the Advantage of Adaptivity for Sampling with Cell Probes |
| topic | Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2605.12873 |