128 citations · 352 across the 17 of their papers we have counts for
28 papers
A Faster Small Treewidth SDP Solver
Yuzhou Gu, Zhao Song
Semidefinite programming is a fundamental tool in optimization and theoretical computer science. It has been extensively used as a black-box for solving many problems, such as embe…
Fast Distance Oracles for Any Symmetric Norm
Yichuan Deng, Zhao Song, Omri Weinstein +1
In the Distance Oracle problem, the goal is to preprocess vectors in a -dimensional metric space into a cheap data st…
Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs
Lijie Chen, Gillat Kol, Dmitry Paramonov +3
For a directed graph with vertices and a start vertex , we wish to (approximately) sample an -step random walk over starting from with…
A Faster Interior Point Method for Semidefinite Programming
Haotian Jiang, Tarun Kathuria, Yin Tat Lee +2
Semidefinite programs (SDPs) are a fundamental class of optimization problems with important recent applications in approximation algorithms, quantum complexity, robust learning, a…
Training (Overparametrized) Neural Networks in Near-Linear Time
Jan van den Brand, Binghui Peng, Zhao Song +1
The slow convergence rate and pathological curvature issues of first-order gradient methods for training deep neural networks, initiated an ongoing effort for developing faster $\m…
Average Case Column Subset Selection for Entrywise -Norm Loss
Zhao Song, David P. Woodruff, Peilin Zhong
We study the column subset selection problem with respect to the entrywise -norm loss. It is known that in the worst case, to obtain a good rank- approximation to a matr…