688 citations · 1.5k across the 49 of their papers we have counts for
34 papers · 1 filter
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…
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…
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…
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…
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…
An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications
Haotian Jiang, Yin Tat Lee, Zhao Song +1
Given a separation oracle for a convex set that is contained in a box of radius , the goal is to either compute a point in or prove that does no…
Optimal Sketching for Kronecker Product Regression and Low Rank Approximation
Huaian Diao, Rajesh Jayaram, Zhao Song +2
We study the Kronecker product regression problem, in which the design matrix is a Kronecker product of two or more matrices. Given for $i=1,2…
Total Least Squares Regression in Input Sparsity Time
Huaian Diao, Zhao Song, David P. Woodruff +1
In the total least squares problem, one is given an matrix , and an matrix , and one seeks to "correct" both and , obtaining matrices $\hat{A…
(Nearly) Sample-Optimal Sparse Fourier Transform in Any Dimension; RIPless and Filterless
Vasileios Nakos, Zhao Song, Zhengyu Wang
In this paper, we consider the extensively studied problem of computing a -sparse approximation to the -dimensional Fourier transform of a length signal. Our algorithm us…
Solving Empirical Risk Minimization in the Current Matrix Multiplication Time
Yin Tat Lee, Zhao Song, Qiuyi Zhang
Many convex problems in machine learning and computer science share the same form: \begin{align*} \min_{x} \sum_{i} f_i( A_i x + b_i), \end{align*} where are convex functions…
Reducing approximate Longest Common Subsequence to approximate Edit Distance
Aviad Rubinstein, Zhao Song
Given a pair of strings, the problems of computing their Longest Common Subsequence and Edit Distance have been extensively studied for decades. For exact algorithms, LCS and Edit…
Stronger L2/L2 Compressed Sensing; Without Iterating
Vasileios Nakos, Zhao Song
We consider the extensively studied problem of compressed sensing. The main contribution of our work is an improvement over [Gilbert, Li, Porat and Strauss, STOC 20…
Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave Densities
Yin Tat Lee, Zhao Song, Santosh S. Vempala
Sampling logconcave functions arising in statistics and machine learning has been a subject of intensive study. Recent developments include analyses for Langevin dynamics and Hamil…
Towards a Zero-One Law for Column Subset Selection
Zhao Song, David P. Woodruff, Peilin Zhong
There are a number of approximation algorithms for NP-hard versions of low rank approximation, such as finding a rank- matrix minimizing the sum of absolute values of differ…