论文标题
通过稀疏内性方程完整的小工具，简单复合物的laplacians的硬度结果
Hardness Results for Laplacians of Simplicial Complexes via Sparse-Linear Equation Complete Gadgets
论文作者
论文摘要
我们研究了$ k $二维的简单复合物（$ k $ complexes）的组合拉普拉斯人的线性方程，这是图形laplacians的自然概括。组合laplacians在同源性中起着至关重要的作用，并且是拓扑中的核心工具。除此之外，他们在数据分析和物理建模问题中还具有各种应用。众所周知，图形laplacians存在近线性的时间求解器。然而，组合拉普拉斯人的几乎线性时间求解器仅以限制的复合物类别而闻名。 本文表明，2个复合体的组合拉普拉奇人的线性方程与通用线性方程一样难以求解。 More precisely, for any constant $c \geq 1$, if we can solve linear equations in combinatorial Laplacians of 2-complexes up to high accuracy in time $\tilde{O}((\# \text{ of nonzero coefficients})^c)$, then we can solve general linear equations with polynomially bounded integer coefficients and condition numbers up to high准确性的准确性$ \ tilde {o}（（（\＃\ text {of nonzero系数}））^c）$。我们通过从一般线性方程到2个复合物的组合拉普拉素剂的几乎线性时间来证明这一点。我们的还原保留了问题实例的稀疏性，直到多同源因素。
We study linear equations in combinatorial Laplacians of $k$-dimensional simplicial complexes ($k$-complexes), a natural generalization of graph Laplacians. Combinatorial Laplacians play a crucial role in homology and are a central tool in topology. Beyond this, they have various applications in data analysis and physical modeling problems. It is known that nearly-linear time solvers exist for graph Laplacians. However, nearly-linear time solvers for combinatorial Laplacians are only known for restricted classes of complexes. This paper shows that linear equations in combinatorial Laplacians of 2-complexes are as hard to solve as general linear equations. More precisely, for any constant $c \geq 1$, if we can solve linear equations in combinatorial Laplacians of 2-complexes up to high accuracy in time $\tilde{O}((\# \text{ of nonzero coefficients})^c)$, then we can solve general linear equations with polynomially bounded integer coefficients and condition numbers up to high accuracy in time $\tilde{O}((\# \text{ of nonzero coefficients})^c)$. We prove this by a nearly-linear time reduction from general linear equations to combinatorial Laplacians of 2-complexes. Our reduction preserves the sparsity of the problem instances up to poly-logarithmic factors.
