AKS三人提出了第一个筛法求解SVP的算法,但在参数选择、复杂度分析等方面不是很完善。NV在后续研究中确定了合适的参数,并给出单指数复杂度的SVP求解算法。
列表筛可以看成是动态版本的AKS/NV筛,不是在初始化阶段进行采样,而是在执行筛法的过程中采样并增加点。由于在新增点时会判断与现有点之间的距离(角度),可以用球覆盖的原理进行分析。由于列表筛是不删除点的,同样会导致空间和时间的浪费,改进列表的维护策略得到更优的高斯筛。
从图中可以看出,高斯筛的空间利用效率较高,而且在运行时间的表现也优于当时最优的筛法。
该论文的贡献主要体现在理论与算法两个方面。在理论方面,之前的工作中隐含了球面堆积理论,本文将该理论和算法进行了深度结合。在算法方面,本文改进了筛选的策略,主要想法是提早舍弃可能会产生碰撞的向量。
高斯筛的结果保证每个向量之间的夹角大于60度,且相互约简无法得到更短的向量,整体的质量较高。从理论分析中可以得出,使用筛法进行SVP的求解时,求解维度与空间大小息息相关,在有限空间的情况下进一步求解更高维度的SVP,可能需要使用枚举方法。