Hardness Results for Laplacians of Simplicial Complexes via Sparse-Linear Equation Complete Gadgets

Ming Ding, Rasmus Kyng, Maximilian Probst Gutenberg, Peng Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

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.

Original languageEnglish (US)
Title of host publication49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022
EditorsMikolaj Bojanczyk, Emanuela Merelli, David P. Woodruff
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772358
DOIs
StatePublished - Jul 1 2022
Event49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022 - Paris, France
Duration: Jul 4 2022Jul 8 2022

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume229
ISSN (Print)1868-8969

Conference

Conference49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022
Country/TerritoryFrance
CityParis
Period7/4/227/8/22

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Combinatorial Laplacians
  • Fine-Grained Complexity
  • Linear Equations
  • Simplicial Complexes

Fingerprint

Dive into the research topics of 'Hardness Results for Laplacians of Simplicial Complexes via Sparse-Linear Equation Complete Gadgets'. Together they form a unique fingerprint.

Cite this