Vassilevska 通常指 Virginia Vassilevska Williams,斯坦福大学计算机科学教授,是理论计算机科学中细粒度复杂度(fine-grained complexity)领域的代表性学者,长期围绕矩阵乘法、APSP、3SUM 与 k-SUM 等核心计算问题研究算法上界与下界。近期以她为核心或相关团队的 arXiv 论文密集出现,使 Vassilevska 相关研究再度成为算法界关注焦点。
Vassilevska 相关研究的近期进展
当前焦点与观察点
Vassilevska 所在的细粒度复杂度社区目前的核心张力在于:若干长期被当作"合理难度假设"的猜想(如奇数 k 的 k-SUM 猜想)在近期工作中被证伪,而矩形矩阵乘法指数等基础参数又在新分析下被推高。这意味着大量基于旧猜想的条件性下界需要重新审视。值得注意的是,本轮论文与 OpenAI、Anthropic 等机构的 arXiv 账号关联,也引发了关于大型 AI 实验室是否在系统性投入基础算法理论的讨论。
观察点集中在三个方面:其一,α≥1/2 的矩形乘法结果能否被进一步推进至更高指数;其二,k-SUM 猜想的修正版本将以何种形式稳定下来,并支撑哪些新下界;其三,(min, +) 乘法与 APSP 的更简洁算法是否会带来可实际部署的改进。总体看,Vassilevska 相关方向正处于假设松动与新工具涌现并行的活跃期。