23 citations · 24 across the 3 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
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.CC2017★ 1 cited
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…