License:
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2022.53
URN: urn:nbn:de:0030-drops-163945
URL: https://drops.dagstuhl.de/opus/volltexte/2022/16394/
Ding, Ming ;
Kyng, Rasmus ;
Gutenberg, Maximilian Probst ;
Zhang, Peng
Hardness Results for Laplacians of Simplicial Complexes via Sparse-Linear Equation Complete Gadgets
Abstract
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 ≥ 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.
BibTeX - Entry
@InProceedings{ding_et_al:LIPIcs.ICALP.2022.53,
author = {Ding, Ming and Kyng, Rasmus and Gutenberg, Maximilian Probst and Zhang, Peng},
title = {{Hardness Results for Laplacians of Simplicial Complexes via Sparse-Linear Equation Complete Gadgets}},
booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
pages = {53:1--53:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-235-8},
ISSN = {1868-8969},
year = {2022},
volume = {229},
editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16394},
URN = {urn:nbn:de:0030-drops-163945},
doi = {10.4230/LIPIcs.ICALP.2022.53},
annote = {Keywords: Simplicial Complexes, Combinatorial Laplacians, Linear Equations, Fine-Grained Complexity}
}
Keywords: |
|
Simplicial Complexes, Combinatorial Laplacians, Linear Equations, Fine-Grained Complexity |
Collection: |
|
49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) |
Issue Date: |
|
2022 |
Date of publication: |
|
28.06.2022 |