Solving the Shortest Vector Problem in $2^{0.6039n}$ Time via Mid-point Hessian
本文提出一种求解最短向量问题（SVP）的随机化算法。SVP 是格密码学中的核心困难问题，其求解复杂度直接关系到基于格的密码方案（如 NTRU、LWE）的安全性评估。此前由 Aggarwal、Dadush、Regev 和 Stephens-D
#algorithm
共收录 5 条相关情报。
← 返回所有主题Calculating the floor of y**(1/m)
该论文针对自然整数 y>2 和 m>1，提出了两种基于牛顿-拉夫森方法的算法，用于计算 y^(1/m) 的向下取整（即整数部分）。该问题在数论中常用于判断一个整数是否为另一个整数的整数次幂。尽管传统上二分查找方法被认为更易实现，但作者提出的
Derivative-Free Richelot Isogenies via Subresultants with Algebraic Certification
该论文针对超椭圆曲线（genus-2）上经典的 Richelot (2,2)-同源步提出了一种完全无导数的重表述。传统的 Richelot 步骤通过曲线 f=uvw 的因式分解，利用 Wronskian 导数构造目标三元组 (U,V,W)。
Privately Estimating Monotone Statistics in Polynomial Time
该论文研究差分隐私下单调统计量的高效估计算法。单调统计量指随着新观测数据增加而单调变化的统计量（如分位数、累积分布函数等）。传统方法采用子采样-聚合（subsample-and-aggregate）框架：将数据集分成多个子块，分别计算统计量
Near-Optimal Generalized Private Testing
该论文研究了差分隐私（DP）中的广义私有测试问题，该问题由 Liu 和 Talwar 在 STOC 2019 中提出。给定一个数据集 X 和一个序列的黑盒 ε_t-DP 机制 M_t，分析者需要以 DP 方式接受第一个成功概率 p_t =