{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreid3pabv565dgmn2awgtgortqezdspu6y5z3b5ol6yrqw4xhfdffoq",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mlqndpitngs2"
  },
  "path": "/report/2026/075",
  "publishedAt": "2026-05-13T00:39:55.000Z",
  "site": "https://eccc.weizmann.ac.il",
  "textContent": "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 $\\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 sampling with 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öös, Myasnikov, Riazanov, and Sokolov (STOC '26).",
  "title": "TR26-075 |  On the Advantage of Adaptivity for Sampling with Cell Probes | \n\n\tAnthony Ostuni, \n\n\tDaniel Kane, \n\n\tFarzan Byramji, \n\n\tJackson Morris"
}