3 papers
cs.DS2025
Near-optimal Linear Sketches and Fully-Dynamic Algorithms for Hypergraph Spectral Sparsification
Sanjeev Khanna, Huan Li, Aaron Putterman
A hypergraph spectral sparsifier of a hypergraph is a weighted subgraph that approximates the Laplacian of to a specified precision. Recent work has shown that similar…
cs.CC2024
Detecting Low-Degree Truncation
Anindya De, Huan Li, Shivam Nadimpalli +1
We consider the following basic, and very broad, statistical problem: Given a known high-dimensional distribution over and a collection of data points in…
cs.DS2024
Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic Depth
Arpit Agarwal, Sanjeev Khanna, Huan Li +4
We present a parallel algorithm for the -approximate maximum flow problem in capacitated, undirected graphs with vertices and edges, achieving $O(ε^{-3}\text{polyl…