Search Results

Documents authored by Black, Mitchell

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.23
Hodge Decomposition and General Laplacian Solvers for Embedded Simplicial Complexes

Authors: Mitchell Black and Amir Nayyeri

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
We describe a nearly-linear time algorithm to solve the linear system L₁x = b parameterized by the first Betti number of the complex, where L₁ is the 1-Laplacian of a simplicial complex K that is a subcomplex of a collapsible complex X linearly embedded in ℝ³. Our algorithm generalizes the work of Black et al. [SODA2022] that solved the same problem but required that K have trivial first homology. Our algorithm works for complexes K with arbitrary first homology with running time that is nearly-linear with respect to the size of the complex and polynomial with respect to the first Betti number. The key to our solver is a new algorithm for computing the Hodge decomposition of 1-chains of K in nearly-linear time. Additionally, our algorithm implies a nearly quadratic solver and nearly quadratic Hodge decomposition for the 1-Laplacian of any simplicial complex K embedded in ℝ³, as K can always be expanded to a collapsible embedded complex of quadratic complexity.
Cite as

Mitchell Black and Amir Nayyeri. Hodge Decomposition and General Laplacian Solvers for Embedded Simplicial Complexes. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 23:1-23:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{black_et_al:LIPIcs.ICALP.2022.23,
  author =	{Black, Mitchell and Nayyeri, Amir},
  title =	{{Hodge Decomposition and General Laplacian Solvers for Embedded Simplicial Complexes}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{23:1--23:17},
  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/entities/document/10.4230/LIPIcs.ICALP.2022.23},
  URN =		{urn:nbn:de:0030-drops-163641},
  doi =		{10.4230/LIPIcs.ICALP.2022.23},
  annote =	{Keywords: Computational Topology, Laplacian solvers, Combinatorial Laplacian, Hodge decomposition, Parameterized Complexity}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.17
ETH-Tight Algorithms for Finding Surfaces in Simplicial Complexes of Bounded Treewidth

Authors: Mitchell Black, Nello Blaser, Amir Nayyeri, and Erlend Raa Vågset

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
Given a simplicial complex with n simplices, we consider the Connected Subsurface Recognition (c-SR) problem of finding a subcomplex that is homeomorphic to a given connected surface with a fixed boundary. We also study the related Sum-of-Genus Subsurface Recognition (SoG) problem, where we instead search for a surface whose boundary, number of connected components, and total genus are given. For both of these problems, we give parameterized algorithms with respect to the treewidth k of the Hasse diagram that run in 2^{O(k log k)}n^{O(1)} time. For the SoG problem, we also prove that our algorithm is optimal assuming the exponential-time hypothesis. In fact, we prove the stronger result that our algorithm is ETH-tight even without restriction on the total genus.
Cite as

Mitchell Black, Nello Blaser, Amir Nayyeri, and Erlend Raa Vågset. ETH-Tight Algorithms for Finding Surfaces in Simplicial Complexes of Bounded Treewidth. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 17:1-17:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{black_et_al:LIPIcs.SoCG.2022.17,
  author =	{Black, Mitchell and Blaser, Nello and Nayyeri, Amir and V\r{a}gset, Erlend Raa},
  title =	{{ETH-Tight Algorithms for Finding Surfaces in Simplicial Complexes of Bounded Treewidth}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{17:1--17:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.17},
  URN =		{urn:nbn:de:0030-drops-160253},
  doi =		{10.4230/LIPIcs.SoCG.2022.17},
  annote =	{Keywords: Computational Geometry, Surface Recognition, Treewidth, Hasse Diagram, Simplicial Complexes, Low-Dimensional Topology, Parameterized Complexity, Computational Complexity}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.31
Effective Resistance and Capacitance in Simplicial Complexes and a Quantum Algorithm

Authors: Mitchell Black and William Maxwell

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
We investigate generalizations of the graph theoretic notions of effective resistance and capacitance to simplicial complexes and prove analogs of formulas known in the case of graphs. In graphs the effective resistance between two vertices is O(n); however, we show that in a simplicial complex the effective resistance of a null-homologous cycle may be exponential. This is caused by relative torsion in the simplicial complex. We provide upper bounds on both effective resistance and capacitance that are polynomial in the number of simplices as well as the maximum cardinality of the torsion subgroup of a relative homology group denoted 𝒯_{max}(𝒦). We generalize the quantum algorithm deciding st-connectivity in a graph and obtain an algorithm deciding whether or not a (d-1)-dimensional cycle γ is null-homologous in a d-dimensional simplicial complex 𝒦. The quantum algorithm has query complexity parameterized by the effective resistance and capacitance of γ. Using our upper bounds we find that the query complexity is O (n^{5/2}⋅ d^{1/2} ⋅ 𝒯_{max}(𝒦)²). Under the assumptions that γ is the boundary of a d-simplex (which may or may not be included in the complex) and that 𝒦 is relative torsion-free, we match the O(n^{3/2}) query complexity obtained for st-connectivity. These assumptions always hold in the case of st-connectivity. We provide an implementation of the algorithm whose running time is polynomial in the size of the complex and the relative torsion. Finally, we prove a duality theorem relating effective resistance and capacitance when 𝒦 is d-dimensional and admits an embedding into ℝ^{d+1}.
Cite as

Mitchell Black and William Maxwell. Effective Resistance and Capacitance in Simplicial Complexes and a Quantum Algorithm. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 31:1-31:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{black_et_al:LIPIcs.ISAAC.2021.31,
  author =	{Black, Mitchell and Maxwell, William},
  title =	{{Effective Resistance and Capacitance in Simplicial Complexes and a Quantum Algorithm}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{31:1--31:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.31},
  URN =		{urn:nbn:de:0030-drops-154641},
  doi =		{10.4230/LIPIcs.ISAAC.2021.31},
  annote =	{Keywords: Simplicial complexes, quantum computing}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact