23 citations · 24 across the 3 of their papers we have counts for
6 papers
Efficient -Laplacian Solvers for Well-Shaped Simplicial Complexes: Beyond Betti Numbers and Collapsing Sequences
Ming Ding, Peng Zhang
We present efficient algorithms for approximately solving systems of linear equations in -Laplacians of well-shaped simplicial complexes up to high precision. -Laplacians, or…
Hardness Results for Laplacians of Simplicial Complexes via Sparse-Linear Equation Complete Gadgets
Ming Ding, Rasmus Kyng, Maximilian Probst Gutenberg +1
We study linear equations in combinatorial Laplacians of -dimensional simplicial complexes (-complexes), a natural generalization of graph Laplacians. Combinatorial Laplacian…
Two-Commodity Flow is Equivalent to Linear Programming under Nearly-Linear Time Reductions
Ming Ding, Rasmus Kyng, Peng Zhang
We give a nearly-linear time reduction that encodes any linear program as a 2-commodity flow problem with only a small blow-up in size. Under mild assumptions similar to those empl…
Incomplete Nested Dissection
Rasmus Kyng, Richard Peng, Robert Schwieterman +1
We present an asymptotically faster algorithm for solving linear systems in well-structured 3-dimensional truss stiffness matrices. These linear systems arise from linear elasticit…
Hardness Results for Structured Linear Systems
Rasmus Kyng, Peng Zhang
We show that if the nearly-linear time solvers for Laplacian matrices and their generalizations can be extended to solve just slightly larger families of linear systems, then they…
Faster and Simpler Width-Independent Parallel Algorithms for Positive Semidefinite Programming
Richard Peng, Kanat Tangwongsan, Peng Zhang
This paper studies the problem of finding an -approximate solution to positive semidefinite programs. These are semidefinite programs in which all matrices in the constraint…