在流式计算的空间复杂度研究中，一个核心问题是：每个空间高效的转轴（turnstile）算法是否都可以视为线性草图（linear sketch）。Li、Nguyen 与 Woodruff（STOC 2014）证明了两者的等价性，但他们的归约要求流的长度至少是维度 $n$ 的双指数级。相反，Kallaugher 与 Price（STOC 2020）展示了在长度为线性级别的流上存在分离，说明等价性并非普遍成立。于是，最自然且实际相关的多项式长度流情形一直悬而未决。
本文证明了多项式长度的转轴算法可以被线性草图模拟。具体而言，设某转轴算法使用 $S$ 位空间，并在所有长度为 $\operatorname{poly}(D, n)$ 的流上成功，则对于满足 $\|x\|_2 \le D$ 的最终向量 $x$，其输出可以从 $O(S)$ 条线性测量中恢复，整体使用 $O(S)$ 位空间。对于在适当输入分布下的平滑问题，经过平滑化的归约还能得到条目幅度受限的草图，只需 $O(S / \log D)$ 条测量且总空间仍为最优的 $O(S)$。
我们的结果同样适用于严格转轴流以及非均匀一次性分支程序（ROBPs）。不同于以往利用转移图的论证，本文的证明基于傅里叶分析和加性组合数学工具，以提取离散的线性测量。我们展示，$S$ 位算法只能对一小集合的重傅里叶频率敏感，而这些频率聚集在一个阶为 $2^{O(S)}$ 的有限群附近；该群的生成元即可作为草图矩阵的行向量。
结合已有的实数草图和通信下界，我们进一步得到针对多项式长度转轴流的新下界。
点评