Tight Lower Bounds for ℓ 2 Sampling
Proceedings of the ACM on Management of Data · 12.05.2026 · 4 (2) · 1-15
DOI: 10.1145/3801915 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 14.05.2026. Verfasst von William Swartworth und 1 weiteren Autor:innen. Die Arbeit nennt 14 Literaturangaben. Gefördert von: Office of Naval Research, Simons Foundation.
Abstract (Originalsprache)
We study linear sketches and data stream algorithms for the ℓp-sampling problem. Here one chooses an r x n matrix A and computes A · v for an underlying vector v. From A · v, one should output a coordinate i ∈ {1, 2, . . . , n} with probability (1 ± ε) ∥vi∥p/ ∥v ∥ p/ p . One is also allowed to output FAIL with a small constant probability. In the estimation version of the problem, one would also like to output a (1 ± ε)-approximation to ∥vi∥p/ ∥v ∥ p/ p, which is the probability for which i was sampled. For 0 < p < 2, work of Jayaram and Woodruff (FOCS, 2018) showed an upper bound of r = O(logn) while for p = 2 the best known upper bound is r = O(log 2 n). They posed it as an open question to resolve this gap. We prove an Ω(log 2 n) sketching dimension lower bound for p = 2, thereby separating the complexity for 0
Förderung
- Office of Naval Research
- Simons Foundation
Zitieren
APA
Swartworth, W., & Woodruff, D. P. (2026). Tight Lower Bounds for ℓ 2 Sampling. Proceedings of the ACM on Management of Data, 4(2), 1-15. https://doi.org/10.1145/3801915
Vancouver
Swartworth W, Woodruff DP. Tight Lower Bounds for ℓ 2 Sampling. Proceedings of the ACM on Management of Data. 2026;4(2):1-15. doi:10.1145/3801915
BibTeX
@article{Swartworth2026,
author = {Swartworth, William and Woodruff, David P.},
title = {Tight Lower Bounds for ℓ 2 Sampling},
journal = {Proceedings of the ACM on Management of Data},
year = {2026},
volume = {4},
number = {2},
pages = {1--15},
doi = {10.1145/3801915}
}
EUVIMED