The rank-independent theorem sharpens many later guarantees that inherit their sampling bounds by strengthening the independent STOC 2023 works of Lee and Jambulapati--Liu--Sidford by removing their rank dependence and answering Lee's open question on whether this loss is inherent.
Abstract
We show that every weighted hypergraph on $n$ vertices admits a spectral $\varepsilon$-sparsifier with $O(n\log n/\varepsilon^2)$ hyperedges, strengthening the independent STOC 2023 works of Lee and Jambulapati--Liu--Sidford by removing their rank dependence and answering Lee's open question on whether this loss is inherent. The key idea is global-dictionary chaining: after choosing clique edge weights with balanced effective resistances, every hyperedge seminorm is Lipschitz with respect to the same global-dictionary norm generated by normalized vertex-pair directions; the local rank complexity is thereby replaced by the Gaussian width of this common dictionary. Since these STOC 2023 works have become standard analytic primitives across a broad subsequent literature on spectral hypergraph sparsification and its variants, our rank-independent theorem sharpens many later guarantees that inherit their sampling bounds.
It is shown that r-uniform Erd\H{o}s-R\'enyi hypergraphs on n vertices exhibit a spectral gap as soon as their expected number of hyperedges satisfies $m \gg n^{r/2}$.
We present a new solver-free parallel spectral sparsification algorithm for weighted graphs that relies only on parallel low-diameter decompositions and independent sampling. This yields the first algorithmic improvement over prior, solver-free parallel sparsification approaches since Koutis (2014) and, for the first time for a practical algorithm, eliminates any dependence on the target approximation accuracy ε in the algorithm's work and depth. Our algorithm works by sub-sampling edges according to their robust connectivity, as introduced by Kapralov and Panigrahy (2012). We show how to estimate the robust connectivities of G in an extremely simple manner: we create multiple random sub graphs Gp, where each edge in G is sub-sampled independently with probability pe = min {we · p, 1}. Then, we run a Low Diameter Decomposition in each of the graphs. If u and v often share a cluster in the LDDs, then this provides us with an upper bound on the robust connectivity of the edge e = (u,v). Carefully invoking this procedure for O (log n) different values of the probabilities p then allows us to obtain sufficiently good estimates for sub-sampling. We additionally complement the theory with an experimental evaluation demonstrating strong performance across relevant graphs and sparsity regimes.
Yves Baumann, Gernot Zöcklein· ACM Symposium on Parallelism...· 0 citations
P-SAPST Lite replaces peeling with a degree order and provides a lower latency order choice within the same framework and complements edge oblivious streaming APST by addressing an offline regime in which structural plans can be reused.
Rong Fu, Yongtai Liu, Xiaowen Ma et al.· 0 citations
We give a randomized data structure for undirected weighted graphs that are partially dynamic, i.e., that undergo either only edge insertions or only edge deletions. The data structure maintains $(1\pm\epsilon)$-approximations to the maxflow value and effective resistance between any queried pair of vertices, with total update time $\widetilde{O}_{\epsilon}(n^2)$ and worst-case query time $\widetilde{O}_{\epsilon}(1)$. Thus, for dense graphs where $m = \Omega(n^2)$, our guarantees are near-optimal. Our algorithms succeed with high probability against an adaptive adversary. Our result follows from a simple stability principle for partially dynamic graphs. We show how to partition an online sequence of $m$ updates into $\widetilde{O}(n/\epsilon)$ epochs such that every graph within an epoch is a $(1\pm O(\epsilon))$-spectral approximation of the graph at the beginning of the epoch. The epochs are determined by the cumulative leverage score of the updated edges: small leverage-score mass implies small spectral change, while the total leverage-score mass over a monotone update sequence is $\widetilde{O}(n)$. Consequently, a spectral sparsifier needs to be recomputed only once per epoch. Applying known static all-pairs maxflow and effective-resistance oracles to these sparsifiers then yields the result.
Gramoz Goranci, Rasmus Kyng, Maximilian Probst Gutenberg et al.· 0 citations
We investigate heavy-Wigner tensors: symmetric random tensors whose independent entries, up to the tensor symmetries, are centered and have moments of order $N^{-(p-1)}$, where $N$ is the tensor dimension. This framework includes normalized adjacency tensors of sparse Erd\H{o}s-R\'enyi hypergraphs and truncated heavy-tailed tensor models. We study trace invariants, a complete family of polynomial invariants under permutations of the tensor indices. We prove that, after the natural normalization, the only non-vanishing asymptotic contributions are those associated with fat hypertrees, and we derive a central limit theorem for these injective trace invariants. As applications, we first analyze Erd\H{o}s-R\'enyi $p$-uniform hypergraphs with edge probability $\alpha_N=c/N^{p-1}$. We prove local weak convergence to a uniform Galton-Watson hypertree with Poisson offspring distribution. We also prove convergence of the empirical spectral distribution of the matrix obtained by contracting the adjacency tensor; in the sparse regime the limiting law depends on the sparsity parameter $c$ and has unbounded support, while in the regime $N^{p-1}\alpha_N\to\infty$ with $N^{p-1}(1-\alpha_N)\to\infty$, the limiting spectral distribution is the semicircle law. This result generalizes for matrices obtained by contracting an arbitrary heavy-Wigner tensor and we derive an explicit formula for the moments of the limiting spectral measure.
We study random sketching matrices with Khatri-Rao structure. In particular, we consider the Khatri-Rao product (i.e., column-wise tensor product) $A_1\odot\cdots\odot A_d \in \mathbb R^{(n_1 \cdots n_d) \times m}$ of random matrices $A_i \in \mathbb R^{n_i \times m}$ whose columns are isotropic, independent and sub-Gaussian (e.g., Gaussian matrices). Khatri-Rao sketching matrices are widely applied in randomized algorithms for linear algebraic computation and data analysis, when the input data has tensor structure that allows for fast multiplication with $A_1\odot\cdots\odot A_d$. However, existing theory is not able to fully explain their performance in practice. In particular, despite significant attention, our best bounds for the important \emph{oblivious subspace embedding} property with Khatri-Rao matrices lag behind what is achievable with standard unstructured matrices. For embedding a $k$-dimensional subspace to $(1\pm \epsilon)$ error, Bujanovi\'c et al. \cite{bujanovic2025subspace} prove that sketching dimension $m = O(k^{3/2}/\epsilon^2)$ suffices in the special case of $d = 2$. Their dependence on $k$ is weaker than the tight bound of $O(k/\epsilon^2)$ known for unstructured sub-Gaussian sketching matrices. In this work, we close this gap, showing that $m = \tilde O(k/\epsilon^2)$ suffices for subspace embedding with a Khatri-Rao sketching matrix with any fixed order $d$. Our proof is simple, leveraging just two basic properties of the Khatri-Rao sketching distribution: 1) the columns of $A_1\odot\cdots\odot A_d \in \mathbb R^{(n_1 \cdots n_d) \times m}$ are independent and isotropic, and 2) each column of $A_1\odot\cdots\odot A_d \in \mathbb R^{(n_1 \cdots n_d) \times m}$ satisfies a weak Johnson-Lindenstrauss type moment property.