CAREER: Fine-Grained Complexity and Algorithms for Structured Linear Equations and Linear Programs

摘要：线性方程和线性规划在计算数学、工程、机器学习和数据科学中普遍存在，它们是开发各种算法范例的强大原语。不幸的是，目前最著名的求解一般线性方程和线性规划的算法运行在超二次时间内，这对于现代大规模数据集来说可能会慢得令人望而却步。然而，在实践中，许多线性方程和程序表现出额外的结构，使得解算器的速度显著提高。这个项目的目的是(1)识别和分类那些可以加速解线性方程和线性规划的结构，以及那些不能加速解线性方程和线性规划的结构，以及(2)了解我们可以多快地求解一般的线性方程和线性规划。该项目的另一个主要部分是为研究生、本科生和高中生提供多学科教育和研究培训，并扩大妇女和代表不足的学生在STEM领域的参与。该项目旨在研究结构线性方程和结构线性规划的细粒度复杂性和算法，主要集中在三个主要目标上。第一个目标是为结构线性方程和线性规划建立“等价”类，这样如果我们可以快速解决一个问题，我们就可以立即同样快速地解决同一等价类中的所有问题。第二个目标是开发结构线性方程和线性规划的有效解算器，这些线性方程和线性规划通常是从实践中产生的。例如，具有附加几何结构的广义拉普拉斯、密集实例(如核矩阵)和随机实例。最后，第三个目标是更好地理解一般线性方程和线性规划的时间复杂性。例如，我们能比矩阵乘法更快地解决一般的线性方程和线性规划吗？在强指数时间假设下的运行时间下限是多少？这个奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Abstract:Linear equations and linear programs are ubiquitous in computational mathematics, engineering, machine learning, and data science, and they are powerful primitives for developing various algorithmic paradigms. Unfortunately, the currently best-known algorithms for solving general linear equations and linear programs run in super-quadratic time, which can be prohibitively slow for modern large-scale datasets. In practice, however, many linear equations and programs exhibit additional structures that enable significantly faster solvers. This project aims (1) to identify and classify structures that can accelerate solving linear equations and linear programs and those that can not and (2) to understand how fast we can solve general linear equations and linear programs. Another major part of this project is to provide multi-disciplinary education and research training for graduate, undergraduate, and high school students and to broaden the participation of women and underrepresented students in STEM fields. This project aims to study fine-grained complexity and algorithms for structured linear equations and structured linear programs and focuses on three major goals. The first goal is to establish ``equivalent`` classes for structured linear equations and linear programs so that if we can solve one problem fast, we can immediately solve all the problems in the same equivalence class equally fast. The second goal is to develop efficient solvers for structured linear equations and linear programs that arise commonly from practice. Examples include generalized Laplacians with additional geometric structures, dense instances such as kernel matrices, and random instances. Finally, the third goal is to better understand the time complexity of general linear equations and linear programs. For example, can we solve general linear equations and linear programs faster than matrix multiplication? What are the runtime lower bounds under the Strong Exponential Time Hypothesis?This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.