55 citations · 80 across the 22 of their papers we have counts for
32 papers
Infinite Lewis Weights in Spectral Graph Theory
Amit Suliman, Omri Weinstein
We study the spectral implications of re-weighting a graph by the -Lewis weights of its edges. Our main motivation is the ER-Minimization problem (Saberi et al., SIAM'…
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…
Quartic Samples Suffice for Fourier Interpolation
Zhao Song, Baocheng Sun, Omri Weinstein +1
We study the problem of interpolating a noisy Fourier-sparse signal in the time duration from noisy samples in the same range, where the ground truth signal can be any …
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…
Training Overparametrized Neural Networks in Sublinear Time
Yichuan Deng, Hang Hu, Zhao Song +2
The success of deep learning comes at a tremendous computational and energy cost, and the scalability of training massively overparametrized neural networks is becoming a real barr…
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…