Hardness Results for Laplacians of Simplicial Complexes via Sparse-Linear Equation Complete Gadgets
OPEN ACCESS
Loading...
Author / Producer
Date
2022
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
We study linear equations in combinatorial Laplacians of k-dimensional simplicial complexes (kcomplexes), 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 ≥ 1, if we can solve linear equations in combinatorial Laplacians of 2-complexes up to high accuracy in time Õ((# 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 Õ((# 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.
Permanent link
Publication status
published
External links
Book title
49th EATCS International Conference on Automata, Languages, and Programming
Volume
229
Pages / Article No.
53
Publisher
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Event
49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Simplicial Complexes; Combinatorial Laplacians; Linear Equations; Fine-Grained Complexity
Organisational unit
09687 - Kyng, Rasmus / Kyng, Rasmus
Notes
Funding
204787 - Algorithms and complexity for high-accuracy flows and convex optimization (SNF)