Aaron Schild

FOCS Conference 2025 Conference Paper

Round Elimination via Self-Reduction: Closing Gaps for Distributed Maximal Matching

• Seri Khoury
• Aaron Schild

Maximal Independent Set (MIS) and Maximal Matching (MM) play a vital role in distributed symmetry breaking. Despite decades of research, the complexity of both problems in the standard LOCAL model remains unresolved, and several gaps between the best-known upper and lower bounds persist. For n-node graphs with maximum degree $\Delta$, the best current upper bound for randomized algorithms is $O(\log \Delta+\operatorname{poly}(\log \log n))$, shown by Barenboim, Elkin, Pettie, and Schneider for MM [FOCS’12, JACM’16], and by Ghaffari for MIS [SODA’16]. On the other hand, the best-known lower bound for the two problems is $\Omega\left(\min \left\{\sqrt{\frac{\log n}{\log \log n}}, \frac{\log \Delta}{\log \log \Delta}\right\}\right)$, shown by Kuhn, Moscibroda, and Wattenhofer [PODC’04, JACM’16]. In this work, we present an $\Omega(\min \{\log \Delta, \sqrt{\log n}\})$ lower bound for MM in $\Delta$-ary trees against randomized algorithms. By a folklore reduction, the same lower bound applies to MIS, albeit not in trees. As a function of n, this is the first advancement in our understanding of the randomized complexity of the two problems in more than two decades. As a function of $\Delta$, this shows that the current upper bounds are optimal for a wide range of $\Delta \in 2^{O(\sqrt{\log n})}$, answering an open question by Balliu, Brandt, Hirvonen, Olivetti, Rabie, and Suomela [FOCS’19, JACM’21]. Moreover, our result implies a surprising and counterintuitive separation between MIS and MM in trees, as it was very recently shown that MIS in trees can be solved in $o(\sqrt{\log n})$ rounds. While MIS can be used to find an MM in general graphs, the reduction does not preserve the tree structure when applied to trees. Our separation shows that this is not an artifact of the reduction, but a fundamental difference between the two problems in trees. This also implies that MIS is strictly harder in general graphs compared to trees. Our main technical contribution is a novel technique in which we show that there is a self-reduction from a matching problem in r rounds to the same matching problem in r-1rounds (with slightly weaker probabilistic guarantees). Conceptually, this resembles the celebrated round elimination technique, which transforms an r-round algorithm for a problem $\Pi$ into an (r-1)round algorithm for a different problem $\Pi^{\prime}$. However, our proof differs significantly from the round elimination framework in several fundamental aspects. One of the key concepts we analyze in achieving our result is vertex survival probability, where we show that after $r \ll \min \{\log \Delta, \sqrt{\log n}\}$ rounds, any algorithm that finds a matching must leave two surviving unmatched nodes that are adjacent.

FOCS Conference 2020 Conference Paper

Algorithms and Hardness for Linear Algebra on Geometric Graphs

• Josh Alman
• Timothy Chu
• Aaron Schild
• Zhao Song 0002

For a function $\mathrm{K}: \mathbb{R}^{d}\times \mathbb{R}^{d}\rightarrow \mathbb{R}_{\geq 0}$, and a set $P=\{x_{1}, \ldots, x_{n}\}\subset \mathbb{R}^{d}$ of $n$ points, the K graph $G_{P}$ of $P$ is the complete graph on $n$ nodes where the weight between nodes $i$ and $j$ is given by $\mathrm{K}(x_{i}, x_{j})$. In this paper, we initiate the study of when efficient spectral graph theory is possible on these graphs. We investigate whether or not it is possible to solve the following problems in $n^{1+o(1)}$ time for a K-graph $G_{P}$ when $d < n^{o(1)}$: •Multiply a given vector by the adjacency matrix or Laplacian matrix of $G_{P}$ •Find a spectral sparsifier of $G_{P}$ •Solve a Laplacian system in $G_{P}$ 's Laplacian matrix For each of these problems, we consider all functions of the form $\mathrm{K}(u, v)=f(\Vert u-v\Vert_{2}^{2})$ for a function $f: \mathbb{R}\rightarrow \mathbb{R}$. We provide algorithms and comparable hardness results for many such K, including the Gaussian kernel, Neural tangent kernels, and more. For example, in dimension $d=\Omega(\log n)$, we show that there is a parameter associated with the function $f$ for which low parameter values imply $n^{1+o(1)}$ time algorithms for all three of these problems and high parameter values imply the nonexistence of subquadratic time algorithms assuming Strong Exponential Time Hypothesis (SETH), given natural assumptions on $f$. As part of our results, we also show that the exponential dependence on the dimension $d$ in the celebrated fast multi-pole method of Greengard and Rokhlin cannot be improved, assuming SETH, for a broad class of functions $f$. To the best of our knowledge, this is the first formal limitation proven about fast multipole methods.

SODA Conference 2019 Conference Paper

Embedding Planar Graphs into Low-Treewidth Graphs with Applications to Efficient Approximation Schemes for Metric Problems

• Eli Fox-Epstein
• Philip N. Klein
• Aaron Schild

We show that, for any ∊ > 0, there is a deterministic embedding of edge-weighted planar graphs of diameter D into bounded-treewidth graphs. The embedding has additive error ∊D. We use this construction to obtain the first efficient bicriteria approximation schemes for weighted planar graphs addressing k -C enter (equivalently d -D omination ), and a metric generalization of independent set, d - independent SET. The approximation schemes employ a metric generalization of Baker's framework that is based on our embedding result.

STOC Conference 2018 Conference Paper

An almost-linear time algorithm for uniform random spanning tree generation

• Aaron Schild

We give an m 1+ o (1) β o (1) -time algorithm for generating uniformly random spanning trees in weighted graphs with max-to-min weight ratio β. In the process, we illustrate how fundamental tradeoffs in graph partitioning can be overcome by eliminating vertices from a graph using Schur complements of the associated Laplacian matrix. Our starting point is the Aldous-Broder algorithm, which samples a random spanning tree using a random walk. As in prior work, we use fast Laplacian linear system solvers to shortcut the random walk from a vertex v to the boundary of a set of vertices assigned to v called a “shortcutter.” We depart from prior work by introducing a new way of employing Laplacian solvers to shortcut the walk. To bound the amount of shortcutting work, we show that most random walk steps occur far away from an unvisited vertex. We apply this observation by charging uses of a shortcutter S to random walk steps in the Schur complement obtained by eliminating all vertices in S that are not assigned to it.

SODA Conference 2018 Conference Paper

Localization of Electrical Flows

• Aaron Schild
• Satish Rao
• Nikhil Srivastava

We show that in any graph, the average length of a flow path in an electrical flow between the endpoints of a random edge is O (log 2 n ). This is a consequence of a more general result which shows that the spectral norm of the entrywise absolute value of the transfer impedance matrix of a graph is O (log 2 n ). This result implies a simple oblivious routing scheme based on electrical flows in the case of transitive graphs.

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.

SODA Conference 2017 Conference Paper

Sandpile prediction on a tree in near linear time

• Akshay Ramachandran
• Aaron Schild