On the Computational Complexity of Betti Numbers: Reductions from Matrix Rank

No abstract is available for this paper.

• Publication year

  2014

• Venue

  ACM-SIAM Symposium on Discrete Algorithms

• Publication date

  2014-01-05

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/1.9781611973402.11
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Multiplying matrices faster than coppersmith-winograd

  2012cited by this paper
• A Deterministic O(mlogm)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(m \log {m})$$\end{document} Time Algorithm f

  2012cited by this paper
• Reeb Graphs: Approximation and Persistence

  2011cited by this paper
• A randomized O(m log m) time algorithm for computing Reeb graphs of arbitrary simplicial complexes

  2010cited by this paper
• Efficient algorithms for computing Reeb graphs

  2009cited by this paper
• Extending Persistence Using Poincaré and Lefschetz Duality

  2009cited by this paper
• Matrix Sparsification for Rank and Determinant Computations via Nested Dissection

  2008cited by this paper
• Using The Borsuk-Ulam Theorem

  2007cited by this paper
• Effective Computational Geometry for Curves and Surfaces Chapter 7 Computational Topology : An Introduction

  2007cited by this paper
• Faster inversion and other black box matrix computations using efficient block projections

  2007cited by this paper
• Fast sparse matrix multiplication

  2004cited by this paper
• Computational topology: ambient isotopic approximation of 2-manifolds

  2003cited by this paper
• Topological Persistence and Simplification

  2000cited by this paper
• Computational Topology

  1999cited by this paper
• An incremental algorithm for Betti numbers of simplicial complexes on the 3-sphere

  1995cited by this paper
• Matrix multiplication via arithmetic progressions

  1987cited by this paper
• Solving sparse linear equations over finite fields

  1986cited by this paper
• Triangular Factorization and Inversion by Fast Matrix Multiplication

  1974cited by this paper

• Topological Obstructions to Shared Priors

  2025cites this paper
• Alternative set-theoretical algorithms for efficient computations of cliques in Vietoris-Rips complexes

  2025cites this paper
• Computing Betti tables and minimal presentations of zero-dimensional persistent homology

  2024cites this paper
• Computing Representatives of Persistent Homology Generators with a Double Twist

  2024cites this paper
• EMP: Effective Multidimensional Persistence for Graph Representation Learning

  2024cites this paper
• Efficient set-theoretic algorithms for computing high-order Forman-Ricci curvature on abstract simplicial complexes

  2023cites this paper
• Weighted 1-Laplacian Solvers for Well-Shaped Simplicial Complexes

  2023cites this paper
• Advantage of Quantum Machine Learning from General Computational Advantages

  2023cites this paper
• Efficient 1-Laplacian Solvers for Well-Shaped Simplicial Complexes: Beyond Betti Numbers and Collapsing Sequences

  2023cites this paper
• TAMP-S2GCNets: Coupling Time-Aware Multipersistence Knowledge Representation with Spatio-Supra Graph Convolutional Networks for Time-Series Forecasting

  2022cites this paper
• On Complexity of Computing Bottleneck and Lexicographic Optimal Cycles in a Homology Class

  2021cites this paper
• Computing Zigzag Persistence on Graphs in Near-Linear Time

  2021influential citation
• Dissecting Ethereum Blockchain Analytics: What We Learn from Topology and Geometry of Ethereum Graph

  2019cites this paper
• Condition and homology in semialgebraic geometry

  2019cites this paper
• A Homology Based Coverage Optimization Algorithm for Wireless Sensor Networks

  2019cites this paper
• Height Persistence and Homology Generators in R 3 Efficiently

  2019cites this paper
• Topological techniques in model selection

  2019cites this paper
• ChainNet: Learning on Blockchain Graphs with Topological Features

  2019cites this paper
• Computing Height Persistence and Homology Generators in ℝ3 Efficiently

  2019influential citation
• Computing Height Persistence and Homology Generators in $\mathbb{R}^3$ Efficiently

  2018cites this paper
• Resting-State fMRI Functional Connectivity: Big Data Preprocessing Pipelines and Topological Data Analysis

  2017cites this paper
• Robust detection and segmentation of cell nuclei in biomedical images based on a computational topology framework

  2017cites this paper
• Optimize wireless networks for energy saving by distributed computation of Čech complex

  2017cites this paper
• An Approach to Establishing the Correspondence of Spatial Objects on Heterogeneous Maps Based on Methods of Computational Topology

  2017cites this paper
• Distributed Simplicial Homology Based Load Balancing Algorithm for Cellular Networks

  2017cites this paper
• Time-delay lifts for physiological signal exploration: An application to ECG analysis

  2017cites this paper
• Barcodes of Towers and a Streaming Algorithm for Persistent Homology

  2017cites this paper
• Topological analysis of data

  2017cites this paper
• Complexity of simplicial homology and independence complexes of chordal graphs

  2016cites this paper
• Singular Persistent Homology with Effective Concurrent Computation

  2016cites this paper
• Persistent Homology and Nested Dissection

  2016cites this paper
• Singular persistent homology with geometrically parallelizable computation

  2016cites this paper
• Small Model $2$-Complexes in $4$-space and Applications

  2015cites this paper
• Parallel Computation of Persistent Homology using the Blowup Complex

  2015cites this paper
• Simplicial homology based energy saving algorithms for wireless networks

  2015cites this paper
• Algorithms for the Reeb Graph and Related Concepts

  2014cites this paper
• Solving 1-Laplacians in Nearly Linear Time: Collapsing and Expanding a Topological Ball

  2014cites this paper