2026-08-16T03:38:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16394 2024-03-06T10:57:22Z ddc:004 open_access

Hardness Results for Laplacians of Simplicial Complexes via Sparse-Linear Equation Complete Gadgets Ding, Ming Kyng, Rasmus Gutenberg, Maximilian Probst Zhang, Peng Simplicial Complexes Combinatorial Laplacians Linear Equations Fine-Grained Complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ming Ding and Rasmus Kyng and Maximilian Probst Gutenberg and Peng Zhang 2022 Is Part Of LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2022.53 urn:nbn:de:0030-drops-163945 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.53 eng https://creativecommons.org/licenses/by/4.0/legalcode