3 papers
cs.CC2022
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…
cs.CC2022
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…
cs.DS2018
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…