频率矩估计的最佳空间复杂度研究取得突破
2024-12-29
一篇由Mark Braverman和Or Zamir撰写的论文证明了频率矩估计的最佳空间下界为Ω(log(nε²)/ε²) ，其中ε = Ω(1/√n)。该研究解决了长期以来困扰计算复杂性领域的难题，在一定范围内，该下界与经典的Alon-Matias-Szegedy算法的上界相匹配。对于更小的ε值，论文还提出了一种改进的算法，进一步完善了频率矩估计的空间复杂度。这项突破性成果为流数据处理和算法设计提供了重要的理论指导。