{"ID":2835273,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.00632","arxiv_id":"2512.00632","title":"Perfect $L_p$ Sampling with Polylogarithmic Update Time","abstract":"Perfect $L_p$ sampling in a stream was introduced by Jayaram and Woodruff (FOCS 2018) as a streaming primitive which, given turnstile updates to a vector $x \\in \\{-\\text{poly}(n), \\ldots, \\text{poly}(n)\\}^n$, outputs an index $i^* \\in \\{1, 2, \\ldots, n\\}$ such that the probability of returning index $i$ is exactly \\[\\Pr[i^* = i] = \\frac{|x_i|^p}{\\|x\\|_p^p} \\pm \\frac{1}{n^C},\\] where $C \u003e 0$ is an arbitrarily large constant. Jayaram and Woodruff achieved the optimal $\\tilde{O}(\\log^2 n)$ bits of memory for $0 \u003c p \u003c 2$, but their update time is at least $n^C$ per stream update. Thus an important open question is to achieve efficient update time while maintaining optimal space. For $0 \u003c p \u003c 2$, we give the first perfect $L_p$-sampler with the same optimal amount of memory but with only $\\text{poly}(\\log n)$ update time. Crucial to our result is an efficient simulation of a sum of reciprocals of powers of truncated exponential random variables by approximating its characteristic function, using the Gil-Pelaez inversion formula, and applying variants of the trapezoid formula to quickly approximate it.","short_abstract":"Perfect $L_p$ sampling in a stream was introduced by Jayaram and Woodruff (FOCS 2018) as a streaming primitive which, given turnstile updates to a vector $x \\in \\{-\\text{poly}(n), \\ldots, \\text{poly}(n)\\}^n$, outputs an index $i^* \\in \\{1, 2, \\ldots, n\\}$ such that the probability of returning index $i$ is exactly \\[\\P...","url_abs":"https://arxiv.org/abs/2512.00632","url_pdf":"https://arxiv.org/pdf/2512.00632v1","authors":"[\"William Swartworth\",\"David P. Woodruff\",\"Samson Zhou\"]","published":"2025-11-29T21:09:23Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}