This work proposes an algorithm that approximates the number of spanning trees in $\widetilde O(m+n^{7/4}\eps^{-3/2})$ time on a graph with $n$ vertices and $m$ edges and is based on the novel concept of $\ell_1$-regularized resistance.
Abstract
We study the basic problem of approximating the number of spanning trees of a graph. We propose an algorithm that approximates the number of spanning trees in $\widetilde O(m+n^{7/4}\eps^{-3/2})$ time on a graph with $n$ vertices and $m$ edges. Our algorithm improves upon the previously best known $\widetilde O(m+n^{15/8}\eps^{-7/4})$ time algorithm by Chu, Gao, Peng, Sachdeva, Sawlani, and Wang [FOCS 2018] and the $\widetilde O(m^{1.5}\eps^{-1})$ time algorithm by Liu, Peng and Yang [FOCS 2026] when $m\ge n^{7/6}$. Notably, our algorithm is based on the novel concept of $\ell_1$-regularized resistance. We propose simple and efficient algorithms for computing $\ell_1$-regularized resistance and we show that they can be used to approximate the number of spanning trees by combining with the determinant sparsifier framework of Durfee, Peebles, Peng, and Rao [FOCS 2017].
The paper presents a one-pass algorithm in the insert-delete graph stream model that returns a $(1+\varepsilon)(\alpha+2)$-approximation for the size of the maximum matching in a graph of arboricity at most $\alpha$. The algorithm uses $O(\varepsilon^{-4/3}\alpha^{4/3}n^{2/3} \text{polylog} n)$ space. For constant $\al...
For a family $\mathcal{F}$ of $k$-graphs, $\ex_k(n,\mathcal{F})$ denotes the maximum number of edges in an $n$-vertex $\mathcal{F}$-free $k$-graph. Let $M_{s+1}^k$ denote a matching of size $s+1$ in $k$-uniform hypergraphs. Recently, Alon and Frankl (JCTB, 2024) determined $\ex_2(n,\{M_{s+1}^2,K_{\ell+1}\})$ for all $n...
For an $F$-free graph $G$, a non-edge is $F$-saturating if adding it to $G$ creates a copy of $F$. We denote by $f_{p+1}(n,m)$ the minimum number of $K_{p+1}$-saturating non-edges in a $K_{p+1}$-free $n$-vertex graph with $m$ edges. Erd\H{o}s and Tuza conjectured that $f_4\left(n,\mathrm{ex}(n,K_3)+ 1\right)= (1 + o(1)...
Let $\lambda$ denote the ratio of the length of a longest common subsequence of two length-$n$ strings to $n$. Rubinstein, Seddighin, Song and Sun [RSSS19] gave an $\Omega(\lambda^3)$-approximation for LCS running in $\widetilde O(n^{39/20})$ time, where $39/20=1.95$. Song [Son19] mentioned that improving the $n^{1.95}...
For a $3$-graph $F$, the Tur\'an number of $F$, denoted by $\ex(n,F)$, is the maximum number of edges in a $3$-graph on $n$ vertices containing no subgraph isomorphic to $F$. Let $F^-_{4,3}$ be the $3$-graph formed by a complete four-vertex core and three outer vertices, with all but one of the twelve triples containin...
The soundness uses a result of Haeupler, Saha, and Srinivasan building on the proof of Moser and Tardos, to upper-bound the probability that a fixed relatively large subset is an independent set after the Moser-Tardos algorithm terminates.
Édouard Bonnet· 0 citations
Related blog posts
Microsoft Research Blog· microsoft.comOct 21, 2026
For decades, a fundamental question about the difficulty of computing in high-dimensional spaces has resisted proof. New research resolves this question, removing a major theoretical obstacle to understanding the efficiency of randomized algorithms used across science and computing. The Kannan–Lovász–Simonovits (KLS) conjecture was proposed in 1995. It asks whether, for a broad class of high-dimensional […] The post Solving a 31-year-old grand challenge in mathematics – the KLS conjecture appear…
MIT News · Artificial Intelligence· news.mit.eduOct 15, 2026
A new computational approach reveals how cells communicate to assemble into tissues. This could accelerate stem cell engineering, improve disease models, and inform therapies.
Microsoft Research Blog· microsoft.comOct 15, 2026
Zero-knowledge proofs can verify computing results without rerunning workloads or exposing sensitive data. Magnetar helps bring them into the mainstream with support for standard programming languages, major speed gains, and quantum-resistant security. The post Proof-based general-purpose computing with Magnetar appeared first on Microsoft Research.
MIT News · Artificial Intelligence· news.mit.eduOct 8, 2026
