research
∙
02/12/2023
Infinite Lewis Weights in Spectral Graph Theory
We study the spectral implications of re-weighting a graph by the ℓ_∞-Le...
share
research
∙
11/27/2022
Dynamic Kernel Sparsifiers
A geometric graph associated with a set of points P= {x_1, x_2, ⋯, x_n }...
research
∙
10/22/2022
Quartic Samples Suffice for Fourier Interpolation
We study the problem of interpolating a noisy Fourier-sparse signal in t...
research
∙
10/22/2022
Discrepancy Minimization in Input-Sparsity Time
A recent work of Larsen [Lar23] gave a faster combinatorial alternative ...
research
∙
08/09/2022
Training Overparametrized Neural Networks in Sublinear Time
The success of deep learning comes at a tremendous computational and ene...
research
∙
05/30/2022
Fast Distance Oracles for Any Symmetric Norm
In the Distance Oracle problem, the goal is to preprocess n vectors x_1,...
research
∙
05/02/2022
Sparse Fourier Transform over Lattices: A Unified Approach to Signal Reconstruction
We revisit the classical problem of band-limited signal reconstruction –...
research
∙
02/24/2022
A Dynamic Fast Gaussian Transform
The Fast Gaussian Transform (FGT) enables subquadratic-time multiplicati...
research
∙
02/17/2022
A Faster Interior-Point Method for Sum-of-Squares Optimization
We present a faster interior-point method for optimizing sum-of-squares ...
research
∙
01/01/2022
Dynamic Least-Squares Regression
A common challenge in large-scale supervised learning, is how to exploit...
research
∙
06/20/2020
Training (Overparametrized) Neural Networks in Near-Linear Time
The slow convergence rate and pathological curvature issues of first-ord...
research
∙
04/16/2020
Faster Dynamic Matrix Inverse for Faster LPs
Motivated by recent Linear Programming solvers, we design dynamic data s...
research
∙
12/05/2019
Settling the relationship between Wilber's bounds for dynamic optimality
In FOCS 1986, Wilber proposed two combinatorial lower bounds on the oper...
research
∙
10/29/2019
An Adaptive Step Toward the Multiphase Conjecture
In 2010, Pǎtraşcu proposed the following three-phase dynamic problem, as...
research
∙
07/25/2019
How to Store a Random Walk
Motivated by storage applications, we study the following data structure...
research
∙
04/09/2019
Lower Bounds for Oblivious Near-Neighbor Search
We prove an Ω(d n/ ( n)^2) lower bound on the dynamic cell-probe comple...
research
∙
11/07/2018
Static Data Structure Lower Bounds Imply Rigidity
We show that static data structure lower bounds in the group (linear) mo...
research
∙
08/12/2018
Local Decodability of the Burrows-Wheeler Transform
The Burrows-Wheeler Transform (BWT) is among the most influential discov...
research
∙
05/08/2018