Huan Li 0002

STOC Conference 2025 Conference Paper

Near-Optimal Linear Sketches and Fully-Dynamic Algorithms for Hypergraph Spectral Sparsification

• Sanjeev Khanna
• Huan Li 0002
• Aaron Putterman

STOC Conference 2024 Conference Paper

Detecting Low-Degree Truncation

• Anindya De
• Huan Li 0002
• Shivam Nadimpalli
• Rocco A. Servedio

We consider the following basic, and very broad, statistical problem: Given a known high-dimensional distribution D over ℝ n and a collection of data points in ℝ n , distinguish between the two possibilities that (i) the data was drawn from D , versus (ii) the data was drawn from D | S , i.e. from D subject to truncation by an unknown truncation set S ⊆ ℝ n . We study this problem in the setting where D is a high-dimensional i.i.d. product distribution and S is an unknown degree- d polynomial threshold function (one of the most well-studied types of Boolean-valued function over ℝ n ). Our main results are an efficient algorithm when D is a hypercontractive distribution, and a matching lower bound: 1. For any constant d , we give a polynomial-time algorithm which successfully distinguishes D from D | S using O ( n d /2 ) samples (subject to mild technical conditions on D and S ); 2. Even for the simplest case of D being the uniform distribution over {±1} n , we show that for any constant d , any distinguishing algorithm for degree- d polynomial threshold functions must use Ω( n d /2 ) samples.

SODA Conference 2024 Conference Paper

Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic Depth

• Arpit Agarwal 0001
• Sanjeev Khanna
• Huan Li 0002
• Prathamesh Patil
• Chen Wang 0027
• Nathan White
• Peilin Zhong

STOC Conference 2023 Conference Paper

On Regularity Lemma and Barriers in Streaming and Dynamic Matching

• Sepehr Assadi
• Soheil Behnezhad
• Sanjeev Khanna
• Huan Li 0002

We present a new approach for finding matchings in dense graphs by building on Szemerédi’s celebrated Regularity Lemma. This allows us to obtain non-trivial albeit slight improvements over longstanding bounds for matchings in streaming and dynamic graphs. In particular, we establish the following results for n -vertex graphs: A deterministic single-pass streaming algorithm that finds a (1− o (1))-approximate matching in o ( n 2 ) bits of space. This constitutes the first single-pass algorithm for this problem in sublinear space that improves over the 1/2-approximation of the greedy algorithm. A randomized fully dynamic algorithm that with high probability maintains a (1− o (1))-approximate matching in o ( n ) worst-case update time per each edge insertion or deletion. The algorithm works even against an adaptive adversary. This is the first o ( n ) update-time dynamic algorithm with approximation guarantee arbitrarily close to one. Given the use of regularity lemma, the improvement obtained by our algorithms over trivial bounds is only by some (log * n ) Θ(1) factor. Nevertheless, in each case, they show that the “right” answer to the problem is not what is dictated by the previous bounds. Finally, in the streaming model, we also present a randomized (1− o (1))-approximation algorithm whose space can be upper bounded by the density of certain Ruzsa-Szemerédi (RS) graphs. While RS graphs by now have been used extensively to prove streaming lower bounds, ours is the first to use them as an upper bound tool for desigining improved streaming algorithms.

FOCS Conference 2022 Conference Paper

On Weighted Graph Sparsification by Linear Sketching

• Yu Chen 0039
• Sanjeev Khanna
• Huan Li 0002

A seminal work of [Ahn-Guha-McGregor, PODS’12] showed that one can compute a cut sparsifier of an unweighted undirected graph by taking a near-linear number of linear measurements on the graph. Subsequent works also studied computing other graph sparsifiers using linear sketching, and obtained near-linear upper bounds for spectral sparsifiers [Kapralov-Lee-Musco-Musco-Sidford, FOCS’14] and first non-trivial upper bounds for spanners [Filtser-Kapralov-Nouri, SODA’21]. All these linear sketching algorithms, however, only work on unweighted graphs, and are extended to weighted graphs by weight grouping, a non-linear operation not implementable in, for instance, general turnstile streams. In this paper, we initiate the study of weighted graph sparsification by linear sketching by investigating a natural class of linear sketches that we call incidence sketches, in which each measurement is a linear combination of the weights of edges incident on a single vertex. This class captures all aforementioned linear sketches for unweighted sparsification. It also covers linear sketches implementable in the simultaneous communication model, where edges are distributed across n machines. Our results are: 1)Weighted cut sparsification: We give an algorithm that computes a $(1+\epsilon)$-cut sparsifier using $\tilde{O}(n\epsilon^{-3})$ linear measurements, which is nearly optimal. This also implies a turnstile streaming algorithm with $\tilde{O}(n\epsilon^{-3})$ space. Our algorithm is achieved by building a so-called “weighted edge sampler” for each vertex. 2)Weighted spectral sparsification: We give an algorithm that computes a $(1+\epsilon)$-spectral sparsifier using $\tilde{O}(n^{6/5}\epsilon^{-4})$ linear measurements. This also implies a turnstile streaming algorithm with $\tilde{O}(n^{6/5}\epsilon^{-4})$ space. Key to our algorithm is a novel analysis of how the effective resistances change under vertex sampling. Complementing our algorithm, we then prove a superlinear lower bound of $\Omega(n^{21/20-o(1)})$ measurements for computing some O(1)-spectral sparsifier using incidence sketches. 3)Weighted spanner computation: We first show that any $o(n^{2})$ linear measurements can only recover a spanner of stretch that in general depends linearly on $\frac{w_{\max}}{w_{\min}}$. We thus focus on graphs with $\frac{w_{\max}}{w_{\min}}=O(1)$ and study the stretch’s dependence on n. On such graphs, the algorithm in [FiltserKapralov-Nouri, SODA’21] can obtain a spanner of stretch $\tilde{O}\left(n^{\frac{2}{3}\left(1-\alpha\right)}\right)$ using $\tilde{O}(n^{1+\alpha})$ measurements for any $\alpha\in [0, 1]$. We prove that, for incidence sketches, this tradeoff is optimal up to an $n^{o(1)}$ factor for all $\alpha\lt 1/10$. We prove both our lower bounds by analyzing the “effective resistances” in certain matrix-weighted graphs, where we develop a number of new tools for reasoning about such graphs – most notably (i) a matrix-weighted analog of the widely used expander decomposition of ordinary graphs, and (ii) a proof that a random vertex-induced subgraph of a matrix-weighted expander is also an expander. We believe these tools are of independent interest.

SODA Conference 2018 Conference Paper

Kirchhoff Index as a Measure of Edge Centrality in Weighted Networks: Nearly Linear Time Algorithms

• Huan Li 0002
• Zhongzhi Zhang

Estimating the relative importance of vertices and edges is a fundamental issue in the analysis of complex networks, and has found vast applications in various aspects, such as social networks, power grids, and biological networks. Most previous work focuses on metrics of vertex importance and methods for identifying powerful vertices, while related work for edges is much lesser, especially for weighted networks, due to the computational challenge. In this paper, we propose to use the well-known Kirchhoff index as the measure of edge centrality in weighted networks, called θ -Kirchhoff edge centrality. The Kirchhoff index of a network is defined as the sum of effective resistances over all vertex pairs. The centrality of an edge e is reflected in the increase of Kirchhoff index of the network when the edge e is partially deactivated, characterized by a parameter θ. We define two equivalent measures for θ -Kirchhoff edge centrality. Both are global metrics and have a better discriminating power than commonly used measures, based on local or partial structural information of networks, e. g. edge betweenness and spanning edge centrality. Despite the strong advantages of Kirchhoff index as a centrality measure and its wide applications, computing the exact value of Kirchhoff edge centrality for each edge in a graph is computationally demanding. To solve this problem, for each of the θ -Kirchhoff edge centrality metrics, we present an efficient algorithm to compute its ∊ -approximation for all the m edges in nearly linear time in m. The proposed θ -Kirchhoff edge centrality is the first global metric of edge importance that can be provably approximated in nearly-linear time. Moreover, according to the θ -Kirchhoff edge centrality, we present a θ -Kirchhoff vertex centrality measure, as well as a fast algorithm that can compute e -approximate Kirchhoff vertex centrality for all the n vertices in nearly linear time in m.

FOCS Conference 2018 Conference Paper

Spectral Subspace Sparsification

• Huan Li 0002
• Aaron Schild

We introduce a new approach to spectral sparsification that approximates the quadratic form of the pseudoinverse of a graph Laplacian restricted to a subspace. We show that sparsifiers with a near-linear number of edges in the dimension of the subspace exist. Our setting generalizes that of Schur complement sparsifiers. Our approach produces sparsifiers by sampling a uniformly random spanning tree of the input graph and using that tree to guide an edge elimination procedure that contracts, deletes, and reweights edges. In the context of Schur complement sparsifiers, our approach has two benefits over prior work. First, it produces a sparsifier in almost-linear time with no runtime dependence on the desired error. We directly exploit this to compute approximate effective resistances for a small set of vertex pairs in faster time than prior work (Durfee-Kyng-Peebles-Rao-Sachdeva '17). Secondly, it yields sparsifiers that are reweighted minors of the input graph. As a result, we give a near-optimal answer to a variant of the Steiner point removal problem. A key ingredient of our algorithm is a subroutine of independent interest: a near-linear time algorithm that, given a chosen set of vertices, builds a data structure from which we can query a multiplicative approximation to the decrease in the effective resistance between two vertices after identifying all vertices in the chosen set to a single vertex with inverse polynomial additional additive error in near-constant time.