55 citations · 87 across the 7 of their papers we have counts for
5 papers · 1 filter
A Dynamic Low-Rank Fast Gaussian Transform
Baihe Huang, Zhao Song, Omri Weinstein +3
The \emph{Fast Gaussian Transform} (FGT) enables subquadratic-time multiplication of an Gaussian kernel matrix with…
Space-Efficient Interior Point Method, with applications to Linear Programming and Maximum Weight Bipartite Matching
S. Cliff Liu, Zhao Song, Hengjie Zhang +2
We study the problem of solving linear program in the streaming model. Given a constraint matrix and vectors , w…
Faster Dynamic Matrix Inverse for Faster LPs
Shunhua Jiang, Zhao Song, Omri Weinstein +1
Motivated by recent Linear Programming solvers, we design dynamic data structures for maintaining the inverse of an real matrix under updates, with…
Distributed Triangle Detection via Expander Decomposition
Yi-Jun Chang, Seth Pettie, Hengjie Zhang
We present improved distributed algorithms for triangle detection and its variants in the CONGEST model. We show that Triangle Detection, Counting, and Enumeration can be solved in…
Improved Algorithms for Fully Dynamic Maximal Independent Set
Yuhao Du, Hengjie Zhang
Maintaining maximal independent set in dynamic graph is a fundamental open problem in graph theory and the first sublinear time deterministic algorithm was came up by Assadi, Onak,…