信息来源：人大高瓴人工智能学院 发布时间：2025年11月18日

近日，中国人民大学高瓴人工智能学院魏哲巍教授团队的论文被国际学术会议ITCS 2026录用。ITCS（Innovations in Theoretical Computer Science Conference，创新理论计算机科学会议）是理论计算机科学领域的顶级国际会议之一，以鼓励原创性和突破性的理论研究而著称。ITCS特别关注具有创新思想和新颖技术的工作，强调研究的概念创新和对领域发展的启发意义，在学术界享有盛誉。2026年的ITCS会议将于1月27-30日在意大利米兰召开。

本论文由上海财经大学理论计算机科学研究中心与中国人民大学高瓴人工智能学院合作完成，是中国人民大学发表的首篇ITCS论文。

论文介绍

论文题目：On Solving Asymmetric Diagonally Dominant Linear Systems in Sublinear Time

论文作者：Tsz Chiu Kwok（上海财经大学理论计算机科学研究中心）、魏哲巍、杨铭基（人大高瓴人工智能学院）

注：同等贡献，按照理论计算机科学领域惯例，作者顺序按姓氏字母序排列。

论文概述：本论文研究了行/列对角占优线性方程组的亚线性时间求解问题。线性方程组求解是许多科学计算和机器学习应用中的核心问题，传统方法需要处理方程组涉及的整个矩阵，计算成本高昂；而亚线性时间算法希望在不访问整个矩阵的情况下快速地计算出近似解。

该方向的已有工作局限于对称对角占优方程组，而本文将这一研究扩展到了更具挑战性的非对称情况。我们通过引入“最大p-范数间隙”这一创新数学概念，刻画了问题的计算复杂性本质。该概念推广了对称矩阵的谱间隙理论，为理解非对称线性方程组的内在结构提供了新的理论工具。

在算法设计方面，本文基于局部图算法中的随机游走采样、局部推送、双向探索等技术，构建了一套高效的局部近似算法框架。该框架不仅成功地将已有技术推广到更一般的线性方程组求解场景，还为图上PageRank计算、有效电阻估计等经典问题提供了更深入的理论洞察和改进的复杂度界。同时，本工作还首次从统一的视角理解了图算法中前向推送和后向推送这两种基本方法，揭示了两者的内在联系。

本文在亚线性求解器、局部图算法和有向谱图理论等领域之间建立了桥梁，为相关理论的发展与融合提供了新的统一框架与研究路径。