.png){kind=icon}
返回
Tight Lower Bounds for l2 Sampling
.png){kind=icon}
PRE
AI
DOI：10.1145/3801915.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
我们研究了线性概要和数据流算法在l(p)-采样问题中的应用。在此问题中，选择一个r × n矩阵A并计算A · v，其中v是基础向量。从A · v中，应以概率(1 ± ε)‖ν(i)‖p/‖ν‖p输出坐标i ∈ {1, 2, ..., n}，且允许以小常数概率输出FAIL。在估计版本的问题中，还希望输出对‖ν(i)‖p/‖ν‖p的(1 ± ε)-近似值，这是采样到i的概率。对于0 < p < 2，Jayaram和Woodruff（FOCS, 2018）的工作给出了r = O(log n)的上界，而对于p = 2，已知最佳上界为r = O(log² n)。他们将其作为开放问题提出以解决这一差距。我们证明了p = 2时的Ω(log² n)概要维度下界，从而将0 < p < 2的复杂度与p = 2的复杂度区分开，并表明他们的上界是最优的。此外，我们证明了估计问题的Ω(ε⁻² log n)概要维度下界，改进了之前的Ω(ε⁻²)下界，并表明他们的算法是最优的。这些结果给出了实值输入的概要维度下界，但通过应用Gribelyuk、Lin、Woodruff、Yu和Zhou（STOC, 2025）的结果，我们得到了poly(n)-值整数流上poly(n)-有界整数流的相同概要维度下界，从而表明Jayaram和Woodruff的概要对于turnstile流是最优的。
Keyword:
l2 sampling
lower bounds
streaming algorithms
期刊
P
IF:
0
论文数:
31
被引数:
0
机构
引用论文
暂无论文信息