688 citations · 1.5k across the 49 of their papers we have counts for
52 papers
Sparse Convolution for Approximate Sparse Instance
Xiaoxiao Li, Zhao Song, Guangyi Zhang
Computing the convolution of two vectors of dimension is one of the most important computational primitives in many fields. For the non-negative convolution scenari…
Faster Robust Tensor Power Method for Arbitrary Order
Yichuan Deng, Zhao Song, Junze Yin
Tensor decomposition is a fundamental method used in various areas to deal with high-dimensional data. \emph{Tensor power method} (TPM) is one of the widely-used techniques in the…
Solving Tensor Low Cycle Rank Approximation
Yichuan Deng, Yeqi Gao, Zhao Song
Large language models have become ubiquitous in modern life, finding applications in various domains such as natural language processing, language translation, and speech recogniti…
Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimension
Yichuan Deng, Sridhar Mahadevan, Zhao Song
Large language models (LLMs) have shown their power in different areas. Attention computation, as an important subroutine of LLMs, has also attracted interests in theory. Recently…
Algorithm and Hardness for Dynamic Attention Maintenance in Large Language Models
Jan van den Brand, Zhao Song, Tianyi Zhou
Large language models (LLMs) have made fundamental changes in human life. The attention scheme is one of the key components over all the LLMs, such as BERT, GPT-1, Transformers, GP…
An Over-parameterized Exponential Regression
Yeqi Gao, Sridhar Mahadevan, Zhao Song
Over the past few years, there has been a significant amount of research focused on studying the ReLU activation function, with the aim of achieving neural network convergence thro…
An Improved Sample Complexity for Rank-1 Matrix Sensing
Yichuan Deng, Zhihang Li, Zhao Song
Matrix sensing is a problem in signal processing and machine learning that involves recovering a low-rank matrix from a set of linear measurements. The goal is to reconstruct the o…
Solving Regularized Exp, Cosh and Sinh Regression Problems
Zhihang Li, Zhao Song, Tianyi Zhou
In modern machine learning, attention computation is a fundamental task for training large language models such as Transformer, GPT-4 and ChatGPT. In this work, we study exponentia…
Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time
Yuzhou Gu, Zhao Song, Junze Yin +1
Given a matrix , the low rank matrix completion problem asks us to find a rank- approximation of as for …
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…
Dynamic Kernel Graph Sparsifiers
Yang Cao, Yichuan Deng, Wenyu Jin +4
A geometric graph associated with a set of points and a fixed kernel function $\mathsf{K}:\mathbb{R}^d\times \mathbb{R}^d\to\ma…
Discrepancy Minimization in Input-Sparsity Time
Yichuan Deng, Xiaoyu Li, Zhao Song +1
A recent work by [Larsen, SODA 2023] introduced a faster combinatorial alternative to Bansal's SDP algorithm for finding a coloring that approximately minimizes…
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…
Approximation Algorithms for LCS and LIS with Truly Improved Running Times
Aviad Rubinstein, Saeed Seddighin, Zhao Song +1
Longest common subsequence () is a classic and central problem in combinatorial optimization. While admits a quadratic time solution, recent evidence s…
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…
Solving SDP Faster: A Robust IPM Framework and Efficient Implementation
Baihe Huang, Shunhua Jiang, Zhao Song +2
This paper introduces a new robust interior point method analysis for semidefinite programming (SDP). This new robust analysis can be combined with either logarithmic barrier or hy…
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…
An improved quantum-inspired algorithm for linear regression
András Gilyén, Zhao Song, Ewin Tang
We give a classical algorithm for linear regression analogous to the quantum matrix inversion algorithm [Harrow, Hassidim, and Lloyd, Physical Review Letters'09, arXiv:0811.3171] f…
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…
Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs
Jan van den Brand, Yin-Tat Lee, Danupon Nanongkai +5
We present an -time randomized algorithm for maximum cardinality bipartite matching and related problems (e.g. transshipment, negative-weight shortest paths, a…
Hyperbolic Concentration, Anti-concentration, and Discrepancy
Zhao Song, Ruizhe Zhang
Chernoff bound is a fundamental tool in theoretical computer science. It has been extensively used in randomized algorithm design and stochastic type analysis. Discrepancy theory,…
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…
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…