I am an associate professor at
the Department of Computer Science, ETH
Zurich,
where I joined in the fall 2019 and was tenured in 2026.
My research focuses on fast algorithms for graph problems and convex optimization, along with
applications in machine learning and scientific computing.
I also work on fine-grained complexity theory, and probability and discrepancy theory.
My research is supported in part by project grant no. 200021 204787
and starting grant no. TMSGI2 218022 of the Swiss National Science
Foundation.
I spent 2018 and the spring of 2019 as a postdoc in the Theory of
Computation Group at
Harvard working with Jelani
Nelson.
Before that, I spent the fall semester 2017 as a
research fellow at the
Simons Institute at UC Berkeley.
I finished my PhD at the Department
of Computer Science at Yale
in the summer 2017, where I was advised by Daniel A.
Spielman.
Before attending Yale, I received B.A. in Computer Science from the University of Cambridge in
2011.
My research has been recognized by several awards, including the FOCS '17 Machtey award for best student paper,
the FOCS '22 best paper award, the ICBS Frontiers of Science '23 award, and most recently the
ETH Zurich Latsis Prize2025,
an award dedicated to recognizing excellent research at ETH Zurich by young scientists across all fields.
The Latsis Foundation produced a video to showcase the work of my group.
If you're interested in applying to do a PhD in our group,
you can send an email to applications-kyng@lists.inf.ethz.ch (as a precaution against spam
filters, cc me as well).
Please include your transcript, a CV, and any other relevant information.
We may request letters of recommendation later in our interview process, but prefer to receive these directly from recommenders.
Our standard PhD program requires you to hold a master's degree when you start.
If you would like to start directly after receiving a bachelor's degree, you should apply to our
Direct Doctorate
Program (joint Master's and PhD),
and also send an email to the above address to let me know you are interested in joining my
group.
Candidates should have a strong background in theoretical computer science or mathematics.
Students in our group are usually jointly mentored by Max Probst Gutenberg and myself.
Postdoc openings
We have an opening for a two-year postdoc in our group.
Candidates should have a strong publication record in theoretical computer science
and research interests that overlap with our group.
The starting date is flexible, and we offer a competitive salary, and generous funding for work travel.
To apply, send an email to applications-kyng@lists.inf.ethz.ch (as a precaution against spam
filters, cc me as well).
Please include your CV and any other relevant information.
We may request letters of recommendation later in our interview process, but prefer to receive these directly from recommenders.
Beyond the postdoc positions in our group, theory researchers interested in doing a postdoc at ETH are also highly encouraged to apply to
the
ITS junior fellowship.
Our group supervises bachelor and master's theses of students in ETHZ D-INFK, and we supervise
student projects through the courses 'Research in Computer Science' and 'Praktische Arbeit'.
In some cases, we also supervise master's theses and projects for students in other ETHZ
departments.
The first almost-linear time maximum and minimum cost flow algorithm of Chen-Kyng-Liu-Peng-Probst Gutenberg-Sachdeva (FOCS 2022), reduced these flow objectives to a sequence of min-ratio cycle problems. Solving this core primitive requires approximately minimizing the ratio of a linear gradient term and an undirected length term.
In Chen-Kyng-Liu-Peng-Probst Gutenberg-Sachdeva (FOCS 2022) and the subsequent work of Chen-Kyng-Liu-Meierhans-Probst Gutenberg (STOC 2024), intricate data structures were given to solve the min-ratio problem.
We show that such a cycle can be extracted directly from the dynamic distance oracle of Kyng-Meierhans-Probst Gutenberg (STOC 2024) using linearity. This simplifies previous algorithms that relied on multiple additional steps to extract the cycle, and can be seen as evidence that solving the min-ratio cycle problem really is all about distances. As a result, we obtain a faster primal maxflow and min-cost flow solver that also extends to incremental graphs.
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.
We propose Volume Approximate Cholesky (VAC), an alternative sampling rule for practical approximate Cholesky algorithms. Our rule samples a uniformly random spanning tree of the arising product clique to reduce the fill-in generated at each step. Sampling a random spanning tree preserves the edgewise marginals of the provably correct scheme of Kyng-Sachdeva (FOCS '16), while ensuring connectivity in the spirit of the practical rule proposed in Gao-Kyng-Spielman (SISC '26). Our sampling method is simple, provably linear time and also admits an \(O(\log n)\) depth parallel implementation.
In their seminal paper [Cohen et al., 2016], Cohen, Musco, and Pachocki proposed a natural and simple online spectral sparsification algorithm: rows \(a_1, a_2, \ldots \in \mathbb{R}^d\) of a matrix \(A\) arrive one-by-one, and when row \(a_i\) arrives, it is appended to sparsifier \(\tilde{A}\) (after appropriately reweighting it) with probability proportional to its current leverage score \(\tau^{\mathrm{OL}}(a_i)=a_i^\top(A_i^\top A_i)^\dagger a_i\), where \(A_i = [a_1, a_2, \ldots, a_i]^\top\), or otherwise discarded forever.
For oblivious streams, they showed that this maintains a \((1\pm\epsilon)\)-spectral approximation \(\tilde{A}\) of every \(A\) with \(O(d\epsilon^{-2}\log^2 d)\) many rows.
A natural question is whether the same algorithm works for adaptive streams, where each row may depend on the algorithm's previous random choices. The original proof does not extend directly: it analyzes the process in isotropic position with respect to the final matrix \(A\), which is not fixed in advance under adaptivity. As an extension of this proof framework remained elusive, various algorithmic variants have since been suggested.
In this paper, we show that the original online leverage-score sampling algorithm is indeed robust to adaptive adversaries. Our main technical contribution is a Freedman-type matrix martingale inequality with an evolving isotropic map, allowing the isotropic map used in the concentration argument to change with the stream.
As a consequence, this gives the first online sparsification algorithm for adaptive streams that yields a sparsifier of near-optimal size \(O(d \varepsilon^{-2}\log^2 d)\) whose working memory is proportional to the size of the sparsifier. For the special case of spectral graph sparsification, we provide an implementation that additionally runs in time near-linear in the stream size.
We present the first polylog-depth, nearly-linear-work parallel algorithm that achieves a \((1 + \epsilon)\)-bicriteria approximation guarantee for undirected minimum-cost flow on expanders. Fix an undirected graph \(G = (V, E)\) with unit capacities, unit lengths, and conductance \(\phi\). For any feasible demand vector \(d\) and any \(\epsilon \in (0, 1)\), we compute a flow that routes \(d\) exactly while simultaneously controlling congestion and total cost. Our main contribution is a new saddle-point optimization method for mixed \(\ell_{\infty}\)-\(\ell_1\) optimization.
We introduce a new algorithm and software for solving linear equations in symmetric
diagonally dominant matrices with non-positive off-diagonal entries (SDDM matrices),
including Laplacian matrices. We use pre-conditioned conjugate gradient (PCG) to
solve the system of linear equations. Our preconditioner is a variant of the
Approximate Cholesky factorization of Kyng and Sachdeva (FOCS 2016). Our
factorization approach is simple: we eliminate matrix rows/columns one at a time and
update the remaining matrix using sampling to approximate the outcome of complete
Cholesky factorization. Unlike earlier approaches, our sampling always maintains a
connectivity in the remaining non-zero structure. Our algorithm comes with a tuning
parameter that upper bounds the number of samples made per original entry.
We implement our algorithm in Julia, providing two versions, AC and AC2, that
respectively use 1 and 2 samples per original entry. We compare their
single-threaded performance to that of current state-of-the-art solvers
Combinatorial Multigrid (CMG), BoomerAMG-preconditioned Krylov solvers from HyPre
and PETSc, Lean Algebraic Multigrid (LAMG), and MATLAB's PCG with Incomplete
Cholesky Factorization (ICC). Our evaluation uses a broad class of problems,
including all large SDDM matrices from the SuiteSparse collection and diverse
programmatically generated instances. Our experiments suggest that our algorithm
attains a level of robustness and reliability not seen before in SDDM solvers, while
retaining good performance across all instances.
Our code and data are public, and we provide a tutorial on how to replicate our
tests. We hope that others will adopt this suite of tests as a benchmark, which we
refer to as SDDM2023. Our solver code is available on
the
Laplacians.jl Github Repo.
Our benchmarking data and tutorial are available in our
SDDM2023 Benchmark.
As large language models (LLMs) advance, their role in higher education, particularly in free-response problem-solving, requires careful examination. This study assesses the performance of GPT-4o and o1-preview under realistic educational conditions in an undergraduate algorithms course. Anonymous GPT-generated solutions to take-home exams were graded by teaching assistants unaware of their origin. Our analysis examines both coarse-grained performance (scores) and fine-grained reasoning quality (error patterns). Results show that GPT-4o consistently struggles, failing to reach the passing threshold, while o1-preview performs significantly better, surpassing the passing score and even exceeding the student median in certain exercises. However, both models exhibit issues with unjustified claims and misleading arguments. These findings highlight the need for robust assessment strategies and AI-aware grading policies in education.
Given an \(m\)-edge, undirected, weighted graph \(G=(V,E,w)\), a Gomory-Hu tree \(T\) (Gomory and Hu, 1961) is a tree over the vertex set \(V\) such that all-pairs mincuts in \(G\) are preserved exactly in \(T\). In this article, we give the first almost-optimal \(m^{1+o(1)}\)-time deterministic algorithm for constructing a Gomory-Hu tree. Prior to our work, the best deterministic algorithm for this problem dated back to the original algorithm of Gomory and Hu that runs in \(nm^{1+o(1)}\) time (using current maxflow algorithms). In fact, this is the first almost-linear time deterministic algorithm for even simpler problems, such as finding the \(k\)-edge-connected components of a graph. Our new result hinges on two separate and novel components that each introduce a distinct set of de-randomization tools of independent interest: - a deterministic reduction from the all-pairs mincuts problem to the single-souce mincuts problem incurring only subpolynomial overhead, and - a deterministic almost-linear time algorithm for the single-source mincuts problem.
We present a new and surprisingly simple analysis of random-shift decompositions -- originally proposed by Miller, Peng, and Xu [SPAA'13]: We show that decompositions for exponentially growing scales \(D = 2^0, 2^1, \ldots, 2^{\log_2(\operatorname{diam}(G))}\), have a tight constant trade-off between distance-to-center and separation probability on average across the distance scales -- opposed to a necessary \(\Omega(\log n)\) trade-off for a single scale.
This almost immediately yields a way to compute a tree \(T\) for graph \(G\) that preserves all graph distances with expected \(O(\log n)\)-stretch. This gives an alternative proof that obtains tight approximation bounds of the seminal result by Fakcharoenphol, Rao, and Talwar [STOC'03] matching the \(\Omega(\log n)\) lower bound by Bartal [FOCS'96]. Our insights can also be used to refine the analysis of a simple \(\ell_1\)-oblivious routing proposed in [FOCS'22], yielding a tight \(O(\log n)\) competitive ratio.
Our algorithms for constructing tree embeddings and \(\ell_1\)-oblivious routings can be implemented in the sequential, parallel, and distributed settings with optimal work, depth, and rounds, up to polylogarithmic factors. Previously, fast algorithms with tight guarantees were not known for tree embeddings in parallel and distributed settings, and for \(\ell_1\)-oblivious routings, not even a fast sequential algorithm was known.
We give a simple algorithm for the dynamic approximate All-Pairs Shortest Paths (APSP) problem. Given a graph \(G = (V, E, l)\) with polynomially bounded edge lengths, our data structure processes \(|E|\) edge insertions and deletions in total time \(|E|^{1 + o(1)}\) and provides query access to \(|E|^{o(1)}\)-approximate distances in time \(\tilde{O}(1)\) per query.
We produce a data structure that mimics Thorup-Zwick distance oracles [TZ05], but is dynamic and deterministic. Our algorithm selects a small number of pivot vertices. Then, for every other vertex, it reduces distance computation to maintaining distances to a small neighborhood around that vertex and to the nearest pivot. We maintain distances between pivots efficiently by representing them in a smaller graph and recursing. We construct these smaller graphs by (a) reducing vertex count using the dynamic distance-preserving core graphs of Kyng-Meierhans-Probst Gutenberg [KMP24] in a black-box manner and (b) reducing edge-count using a dynamic spanner akin to Chen-Kyng-Liu-Meierhans-Probst Gutenberg [CKL+24]. Our dynamic spanner internally uses an APSP data structure. Choosing a large enough size reduction factor in the first step allows us to simultaneously bootstrap our spanner and a dynamic APSP data structure.
Notably, our approach does not need expander graphs, an otherwise ubiquitous tool in derandomization.
We propose a randomized multiplicative weight update (MWU) algorithm for \(\ell_{\infty}\) regression that runs in \(\widetilde{O}\left(n^{2+1/22.5} \text{poly}(1/ε)\right)\) time when \(ω= 2+o(1)\), improving upon the previous best \(\widetilde{O}\left(n^{2+1/18} \text{poly} \log(1/ε)\right)\) runtime in the low-accuracy regime. Our algorithm combines state-of-the-art inverse maintenance data structures with acceleration. In order to do so, we propose a novel acceleration scheme for MWU that exhibits {\it stabiliy} and {\it robustness}, which are required for the efficient implementations of the inverse maintenance data structures.
We also design a faster {\it deterministic} MWU algorithm that runs in \(\widetilde{O}\left(n^{2+1/12}\text{poly}(1/ε)\right))\) time when \(ω= 2+o(1)\), improving upon the previous best \(\widetilde{O}\left(n^{2+1/6} \text{poly} \log(1/ε)\right)\) runtime in the low-accuracy regime. We achieve this by showing a novel stability result that goes beyond previously known works based on interior point methods (IPMs).
Our work is the first to use acceleration and inverse maintenance together efficiently, finally making the two most important building blocks of modern structured convex optimization compatible.
We give a simple algorithm for maintaining a \(n^{o(1)}\)-approximate spanner \(H\) of a graph \(G\) with \(n\) vertices as \(G\) receives edge updates by reduction to the dynamic All-Pairs Shortest Paths (APSP) problem. Given an initially empty graph \(G\), our algorithm processes \(m\) insertions and \(n\) deletions in total time \(m^{1 + o(1)}\) and maintains an initially empty spanner \(H\) with total recourse \(n^{1 + o(1)}\). When the number of insertions is much larger than the number of deletions, this notably yields recourse sub-linear in the total number of updates.
Our algorithm only has a single \(O(\log n)\) factor overhead in runtime and approximation compared to the underlying APSP data structure. Therefore, future improvements for APSP will directly yield an improved dynamic spanner.
We give the first almost-linear total time algorithm for deciding if a flow of cost at most \(F\) still exists in a directed graph, with edge costs and capacities, undergoing decremental updates, i.e., edge deletions, capacity decreases, or cost increases.
This implies almost-linear time algorithms for approximating the minimum-cost flow value and \(s\)-\(t\) distance on such decremental graphs.
Our framework additionally allows us to maintain decremental strongly connected components in almost-linear time deterministically.
These algorithms also improve over the current best known runtimes for statically computing minimum-cost flow, in both the randomized and deterministic settings.
We obtain our algorithms by taking the dual perspective, which yields cut-based algorithms.
More precisely, our algorithm computes the flow via a sequence of \(m^{1+o(1)}\) dynamic min-ratio cut problems, the dual analog of the dynamic min-ratio cycle problem that underlies recent fast algorithms for minimum-cost flow. Our main technical contribution is a new data structure that returns an approximately optimal min-ratio cut in amortized \(m^{o(1)}\) time by maintaining a tree-cut sparsifier. This is achieved by devising a new algorithm to maintain the dynamic expander hierarchy of [Goranci-Räcke-Saranurak-Tan, SODA 2021] that also works in capacitated graphs. All our algorithms are deterministc, though they can be sped up further using randomized techniques while still working against an adaptive adversary.
In this paper, we investigate the question of whether the electrical flow routing is a good oblivious routing scheme on an \(m\)-edge graph \(G = (V, E)\) that is a \(\Phi\)-expander, i.e. where \(\lvert \partial S \rvert \geq \Phi \cdot \mathrm{vol}(S)\) for every \(S \subseteq V, \mathrm{vol}(S) \leq \mathrm{vol}(V)/2\). Beyond its simplicity and structural importance, this question is well-motivated by the current state-of-the-art of fast algorithms for \(\ell_{\infty}\) oblivious routings that reduce to the expander-case which is in turn solved by electrical flow routing.
Our main result proves that the electrical routing is an \(O(\Phi^{-1} \log m)\)-competitive oblivious routing in the \(\ell_1\)- and \(\ell_\infty\)-norms. We further observe that the oblivious routing is \(O(\log^2 m)\)-competitive in the \(\ell_2\)-norm and, in fact, \(O(\log m)\)-competitive if \(\ell_2\)-localization is \(O(\log m)\) which is widely believed.
Using these three upper bounds, we can smoothly interpolate to obtain upper bounds for every \(p \in [2, \infty]\) and \(q\) given by \(1/p + 1/q = 1\). Assuming \(\ell_2\)-localization in \(O(\log m)\), we obtain that in \(\ell_p\) and \(\ell_q\), the electrical oblivious routing is \(O(\Phi^{-(1-2/p)}\log m)\) competitive. Using the currently known result for \(\ell_2\)-localization, this ratio deteriorates by at most a sublogarithmic factor for every \(p, q \neq 2\).
We complement our upper bounds with lower bounds that show that the electrical routing for any such \(p\) and \(q\) is \(\Omega(\Phi^{-(1-2/p)}\log m)\)-competitive. This renders our results in \(\ell_1\) and \(\ell_{\infty}\) unconditionally tight up to constants, and the result in any \(\ell_p\)- and \(\ell_q\)-norm to be tight in case of \(\ell_2\)-localization in \(O(\log m)\).
In a breakthrough result, Spielman and Teng (2004) developed a nearly-linear time solver for Laplacian linear equations, i.e. equations where the coefficient matrix is symmetric with non-negative diagonals and zero row sums. Since the development of the Spielman-Teng solver, there has been substantial progress, simplifying and improving their result, but obtaining a fast practical, parallel Laplacian solver remains an open problem.
We present a framework for obtaining extremely simple, parallel Laplacian linear equation solvers with nearly-linear work and sublinear depth. Our framework allows us to parallelize any Laplacian solver based on repeated single-vertex approximate Gaussian elimination. We demonstrate this by parallelizing both the algorithm of Kyng and Sachdeva (2016) and the practical variant by Gao, Kyng, and Spielman (2023). Our framework is work-efficient in the sense of matching the sequential work of these algorithms.
Our parallelization framework is very simple: We sample a subset of the current low-degree vertices (sparse columns), and in parallel we eliminate all vertices that are isolated in the resulting induced subgraph. This approach can be combined with any parallelizable approximate single-vertex elimination subroutine with sparse output. Given the simplicity of the approach, we believe that using it to parallelize the solver of Gao, Kyng, and Spielman (2023) is the most promising direction for obtaining practical parallel Laplacian solvers.
If we additionally use a parallel spectral sparsification routine, our approach can be modified to work in polylogarithmic depth and nearly-linear work.
We give the first almost-linear time algorithms for several problems in incremental
graphs
including cycle detection, strongly connected component maintenance, \(s\)-\(t\)
shortest path, maximum flow, and minimum-cost flow.
To solve these problems, we give a deterministic data structure that returns a
\(m^{o(1)}\)-approximate minimum-ratio cycle in fully dynamic graphs in amortized
\(m^{o(1)}\) time per update.
Combining this with the interior point method framework of Brand-Liu-Sidford (STOC
2023) gives the first almost-linear time algorithm for deciding the first update in
an incremental graph after which the cost of the minimum-cost flow attains value at
most some given threshold \(F\).
By rather direct reductions to minimum-cost flow, we are then able to solve the
problems in incremental graphs mentioned above.
Our new data structure also leads to a modular and deterministic almost-linear time
algorithm for minimum-cost flow by removing the need for complicated modeling of a
restricted adversary, in contrast to recent randomized and deterministic algorithms
for minimum-cost flow in
Chen-Kyng-Liu-Peng-Probst Gutenberg-Sachdeva (FOCS 2022) &
Brand-Chen-Kyng-Liu-Peng-Probst Gutenberg-Sachdeva-Sidford (FOCS 2023).
At a high level, our algorithm dynamizes the \(\ell_1\) oblivious routing of
Rozho\v{n}-Grunau-Haeupler-Zuzic-Li (STOC 2022), and develops a method to extract an
approximate minimum ratio cycle from the structure of the oblivious routing. To
maintain the oblivious routing, we use tools from concurrent work of
Kyng-Meierhans-Probst Gutenberg which designed vertex sparsifiers for shortest
paths, in order to maintain a sparse neighborhood cover in fully dynamic graphs.
To find a cycle, we first show that an approximate minimum ratio cycle can be
represented as a fundamental cycle on a small set of trees resulting from the
oblivious routing. Then, we find a cycle whose quality is comparable to the best
tree cycle.
This final cycle query step involves vertex and edge sparsification procedures
reminiscent of the techniques
introduced in Chen-Kyng-Liu-Peng-Probst Gutenberg-Sachdeva (FOCS 2022), but
crucially requires a more powerful dynamic spanner, which can handle far more edge
insertions than prior work.
We build such a spanner via a construction that hearkens back to the classic greedy
spanner algorithm of
Althöfer-Das-Dobkin-Joseph-Soares
(Discrete & Computational Geometry 1993).
We present a general toolbox, based on new vertex sparsifiers, for designing data
structures to maintain shortest paths in dynamic graphs.
In an \(m\)-edge graph undergoing edge insertions and deletions, our data
structures give the first algorithms for maintaining (a) \(m^{o(1)}\)-approximate
all-pairs shortest paths (APSP) with \emph{worst-case} update time \(m^{o(1)}\) and
query time \(\tilde{O}(1)\), and (b) a tree \(T\) that has diameter no larger than a
subpolynomial factor times the diameter of the underlying graph, where each update
is handled in amortized subpolynomial time.
In graphs undergoing only edge deletions, we develop a simpler and more
efficient data structure to maintain a \((1+\epsilon)\)-approximate single-source
shortest paths (SSSP) tree \(T\) in a graph undergoing edge deletions in amortized
time \(m^{o(1)}\) per update.
Our data structures are deterministic. The trees we can maintain are not
subgraphs of \(G\), but embed with small edge congestion into \(G\). This is in
stark
contrast to previous approaches and is useful for algorithms that internally use
trees to route flow.
To illustrate the power of our new toolbox, we show that our SSSP data structure
gives simple deterministic implementations of flow-routing MWU methods in several
contexts, where previously only randomized methods had been known.
To obtain our toolbox, we give the first algorithm that, given a graph \(G\)
undergoing edge insertions and deletions and a dynamic terminal set \(A\), maintains
a
vertex sparsifier \(H\) that approximately preserves distances between terminals in
\(A\), consists of at most \(|A|m^{o(1)}\) vertices and edges, and can be updated in
worst-case time \(m^{o(1)}\).
Crucially, our vertex sparsifier construction allows us to maintain a low
edge-congestion embedding of \(H\) into \(G\), which is needed for our applications.
We provide an algorithm which, with high probability, maintains a
\((1-\epsilon)\)-approximate maximum flow on an undirected graph undergoing
\(m\)-edge additions in amortized \(m^{o(1)} \epsilon^{-3}\) time per update. To
obtain this result, we provide a more general algorithm that solves what we call the
incremental, thresholded \(p\)-norm flow problem that asks to determine the first
edge-insertion in an undirected graph that causes the minimum \(\ell_p\)-norm flow
to decrease below a given threshold in value. Since we solve this thresholded
problem, our data structure succeeds against an adaptive adversary that can only see
the data structure's output. Furthermore, since our algorithm holds for \(p =
2\), we obtain improved algorithms for dynamically maintaining the effective
resistance between a pair of vertices in an undirected graph undergoing edge
insertions. Our algorithm builds upon previous dynamic algorithms for approximately
solving the minimum-ratio cycle problem that underlie previous advances on the
maximum flow problem [Chen-Kyng-Liu-Peng-Probst Gutenberg-Sachdeva, FOCS '22] as
well as recent dynamic maximum flow algorithms [v.d.Brand-Liu-Sidford, STOC
'23]. Instead of using interior point methods, which were a key component of
these recent advances, our algorithm uses an optimization method based on
\(\ell_p\)-norm iterative refinement and the multiplicative weight update method.
This ensures a monotonicity property in the minimum-ratio cycle subproblems that
allows us to apply known data structures and bypass issues arising from adaptive
queries.
We give a deterministic algorithm that computes exact maximum flows and minimum-cost
flows on directed graphs with \(m\) edges and polynomially bounded integral demands,
costs, and capacities in \(m^{1+o(1)}\) time. As a consequence, we obtain the first
improvement in the running time of deterministic algorithms for computing
maximum-flow in graphs with polynomial bounded capacities since the work of
Goldberg-Rao [J.ACM '98].
Our algorithm is based on the flow framework of
Chen-Kyng-Liu-Peng-Gutenberg-Sachdeva [FOCS '22] that computes the optimal flow
through a sequence of \(m^{1+o(1)}\) approximate undirected minimum-ratio cycles. We
obtain a deterministic dynamic graph data-structure to process such a sequence of
minimum-ratio cycles in an amortized \(m^{o(1)}\) time.
Our two key technical contributions are 1) a deterministic analog of the vertex
sparsification component of the data-structure from Chen et al. that was
based on sampling random low-stretch trees, and 2) a deterministic edge
sparsification component based on a new construction of dynamic spanners
with explicit embeddings. Our methods can also be applied to give a deterministic
data structure that maintains a fully dynamic low-stretch spanning tree on graphs
with polynomially large lengths, with subpolynomial average stretch and requiring
only subpolynomial amortized update time.
In this article, we show that the algorithm of maintaining expander
decompositions in graphs undergoing edge deletions directly by removing sparse
cuts repeatedly can be made efficient. Formally, for an \(m\)-edge undirected graph
\(G\), we say a cut \((S, \bar{S})\)
is \(\phi\)-sparse if \(|E_G(S, \bar{S})| < \phi \cdot \min\{vol_G(S),
vol_G(\bar{S})\}\). A \(\phi\)-expander decomposition of \(G\) is a partition of
\(V\)
into sets \(X_1, X_2, \ldots, X_k\) such that each cluster \(G[X_i]\) contains no
\(\phi\)-sparse cut (meaning it is a \(\phi\)-expander) with \(\tilde{O}(\phi m)\)
edges crossing between clusters. A natural way to compute a \(\phi\)-expander
decomposition is to decompose clusters by \(\phi\)-sparse cuts until no such cut
is contained in any cluster. We show that even in graphs undergoing edge
deletions, a slight relaxation of this meta-algorithm can be implemented
efficiently with amortized update time \(m^{o(1)}/\phi^2\). Our approach naturally
extends to maintaining directed \(\phi\)-expander
decompositions and \(\phi\)-expander hierarchies and thus gives a unifying
framework while having simpler proofs than previous state-of-the-art work. In
all settings, our algorithm matches the run-times of previous algorithms up to
subpolynomial factors. Moreover, our algorithm provides stronger guarantees for
\(\phi\)-expander decompositions, for example, for graphs undergoing edge
deletions, our approach achieves the first sublinear \(\phi m^{o(1)}\) recourse
bounds on the number of edges to become crossing between clusters. Our techniques
also give by far the simplest, deterministic algorithms for
maintaining Strongly-Connected Components (SCCs) in directed graphs undergoing
edge deletions, and for maintaining connectivity in undirected fully-dynamic
graphs, both matching the current state-of-the-art run-times up to
subpolynomial factors.
We present a very simple and intuitive algorithm to find balanced sparse cuts
in a graph via shortest-paths. Our algorithm combines a new
multiplicative-weights framework for solving unit-weight multi-commodity flows
with standard ball growing arguments. Using Dijkstra's algorithm for computing
the shortest paths afresh every time gives a very simple algorithm that runs in
time \(\widetilde{O}(m^2/\phi)\) and finds an \(\widetilde{O}(\phi)\)-sparse
balanced cut, when the given graph has a \(\phi\)-sparse balanced cut. Combining
our algorithm with known deterministic data-structures for answering
approximate All Pairs Shortest Paths (APSP) queries under increasing edge
weights (decremental setting), we obtain a simple deterministic algorithm that
finds \(m^{o(1)}\phi\)-sparse balanced cuts in \(m^{1+o(1)}/\phi\) time. Our
deterministic almost-linear time algorithm matches the state-of-the-art in
randomized and deterministic settings up to subpolynomial factors, while being
significantly simpler to understand and analyze, especially compared to the
only almost-linear time deterministic algorithm, a recent breakthrough by
Chuzhoy-Gao-Li-Nanongkai-Peng-Saranurak (FOCS 2020).
We give an algorithm that computes exact maximum flows and minimum-cost flows
on directed graphs with \(m\) edges and polynomially bounded integral demands,
costs, and capacities in \(m^{1+o(1)}\) time. Our algorithm builds the flow
through a sequence of \(m^{1+o(1)}\) approximate undirected minimum-ratio cycles,
each of which is computed and processed in amortized \(m^{o(1)}\) time using a
dynamic data structure.
Our framework extends to an algorithm running in \(m^{1+o(1)}\) time for
computing flows that minimize general edge-separable convex functions to high
accuracy. This gives an almost-linear time algorithm for several problems
including entropy-regularized optimal transport, matrix scaling, \(p\)-norm
flows, and isotonic regression.
In this article, we present the first deterministic directed Laplacian L
systems solver that runs in time almost-linear in the number of non-zero
entries of L. Previous reductions imply the first deterministic almost-linear
time algorithms for computing various fundamental quantities on directed graphs
including stationary distributions, personalized PageRank, hitting times and
escape probabilities. We obtain these results by introducing partial symmetrization,
a new
technique that makes the Laplacian of an Eulerian directed graph ``less
directed'' in a useful sense, which may be of independent interest. The
usefulness of this technique comes from two key observations: Firstly, the
partially symmetrized Laplacian preconditions the original Eulerian Laplacian
well in Richardson iteration, enabling us to construct a solver for the
original matrix from a solver for the partially symmetrized one. Secondly, the
undirected structure in the partially symmetrized Laplacian makes it possible
to sparsify the matrix very crudely, i.e. with large spectral error, and still
show that Richardson iterations convergence when using the sparsified matrix as
a preconditioner. This allows us to develop deterministic sparsification tools
for the partially symmetrized Laplacian. Together with previous reductions from
directed Laplacians to Eulerian
Laplacians, our technique results in the first deterministic almost-linear time
algorithm for solving linear equations in directed Laplacians. To emphasize the
generality of our new technique, we show that two prominent existing
(randomized) frameworks for solving linear equations in Eulerian Laplacians can
be derandomized in this way: the squaring-based framework of Cohen, Kelner,
Peebles, Peng, Rao, Sidford and Vladu (STOC 2017) and the sparsified
Cholesky-based framework of Peng and Song (STOC 2022).
We present new scalar and matrix Chernoff-style concentration bounds for a
broad class of probability distributions over the binary hypercube \(\{0,1\}^n\).
Motivated by recent tools developed for the study of mixing times of Markov
chains on discrete distributions, we say that a distribution is
\(\ell_\infty\)-independent when the infinity norm of its influence matrix
\(\mathcal{I}\) is bounded by a constant. We show that any distribution which is
\(\ell_\infty\)-infinity independent satisfies a matrix Chernoff bound that
matches the matrix Chernoff bound for independent random variables due to
Tropp. Our matrix Chernoff bound is a broad generalization and strengthening of
the matrix Chernoff bound of Kyng and Song (FOCS'18). Using our bound, we can
conclude as a corollary that a union of \(O(\log|V|)\) random spanning trees
gives a spectral graph sparsifier of a graph with \(|V|\) vertices with high
probability, matching results for independent edge sampling, and matching lower
bounds from Kyng and Song.
Recently, Gutenberg, Williams and Wein [STOC'20] introduced a deterministic
\(\tilde{O}(n^2)\) algorithm for this problem, achieving near linear time for
very dense graphs. For sparse graphs, Chechik and Zhang [SODA'21] recently
presented a deterministic \(\tilde{O}(m^{5/3})\) algorithm, and an adaptive
randomized algorithm with run-time \(\tilde{O}(m\sqrt{n} + m^{7/5})\). This
algorithm is remarkable for two reasons: 1) in very spare graphs it reaches the
directed hopset barrier of \(\tilde{\Omega}(n^{3/2})\) that applied to all
previous approaches for partially-dynamic SSSP [STOC'14, SODA'20, FOCS'20]
\emph{and} 2) it does not resort to a directed hopset technique itself.
In this article we introduce \emph{propagation synchronization}, a new
technique for controlling the error build-up on paths throughout batches of
insertions. This leads us to a significant improvement of the approach in
[SODA'21] yielding a \emph{deterministic} \(\tilde{O}(m^{3/2})\) algorithm for
the problem. By a very careful combination of our new technique with the
sampling approach from [SODA'21], we further obtain an adaptive randomized
algorithm with total update time \(\tilde{O}(m^{4/3})\). This is the first
partially-dynamic SSSP algorithm in sparse graphs to bypass the notorious
directed hopset barrier which is often seen as the fundamental challenge
towards achieving truly near-linear time algorithms.
We study linear equations in combinatorial Laplacians of k-dimensional simplicial
complexes (k-complexes), a natural generalization of graph Laplacians. Combinatorial
Laplacians play a crucial role in homology and are a central tool in topology.
Beyond this, they have various applications in data analysis and physical modeling
problems. It is known that nearly-linear time solvers exist for graph Laplacians.
However, nearly-linear time solvers for combinatorial Laplacians are only known for
restricted classes of complexes.
This paper shows that linear equations in combinatorial Laplacians of 2-complexes
are as hard to solve as general linear equations. More precisely, for any constant
c≥1, if we can solve linear equations in combinatorial Laplacians of 2-complexes to
high accuracy in time \(\tilde{O}(\text{# of nonzero coefficients})^c\), then we can
solve general linear equations with polynomially bounded integer coefficients and
condition numbers to high accuracy in time \(\tilde{O}(\text{# of nonzero
coefficients})^c\). We prove this by a nearly-linear time reduction from general
linear equations to combinatorial Laplacians of 2-complexes. Our reduction preserves
the sparsity of the problem instances up to poly-logarithmic factors.
We give a nearly-linear time reduction that encodes any linear
program as a 2-commodity flow problem with only a polylogarithmic
blow-up in size.
Our reduction applies to high-accuracy approximation algorithms and
exact algorithms.
Given an approximate solution to the 2-commodity flow problem, we
can extract a solution to the linear program in linear time with
only a polynomial factor increase in the error.
This implies that
any algorithm that solves the 2-commodity flow problem can solve linear
programs in essentially the same time.
Given a directed graph with edge capacities and two source-sink pairs, the goal of
the 2-commodity flow problem is to maximize the sum of the flows routed between the
two source-sink pairs subject to edge capacities and flow conservation.
A 2-commodity flow problem can be formulated as a linear program,
which can be solved to high accuracy in almost the current matrix
multiplication time (Cohen-Lee-Song JACM'21). In this paper, we show
that linear programs can be approximately solved, to high accuracy,
using 2-commodity flow as well. As a corollary, if a 2-commodity flow
problem can be approximately solved in time \(O(|E|^c
\operatorname{polylog}(U|E|\epsilon^{-1}))\), where \(E\) is the
graph edge set, \(U\) is the ratio of maximum to minimum edge capacity, \(\epsilon\)
is
the multiplicative error parameter, and \(c\) is a constant greater than
or equal to 1, then a linear program with integer coefficients and
feasible set radius \(r\) can be approximately solved in time \(O(N^c
\operatorname{polylog}((r+1)X\epsilon^{-1}))\), where \(N\) is the number
of nonzeros and \(X\) is the largest magnitude of the coefficients.
Thus a solver for 2-commodity flow with running time exponent \(c < \omega\),
where
\(\omega \leq 2.37286\) is the matrix multiplication constant, would improve the
running time for solving sparse linear programs. Our proof follows the outline
of Itai’s polynomial-time reduction of a linear program to a 2-commodity flow
problem (JACM’78). Itai's reduction shows that exactly solving 2-commodity flow
and exactly solving linear programming are polynomial-time equivalent. We
improve Itai’s reduction to preserve the sparsity of all the intermediate steps.
In addition, we establish an error bound for approximately solving each
intermediate problem in the reduction, and show that the accumulated error is
polynomially bounded. We remark that our reduction does not run in strongly
polynomial time and that it is open whether 2-commodity flow and linear
programming are equivalent in strongly polynomial time.
We improve the current best running time value to invert sparse matrices over
finite fields, lowering it to an expected \(O\big(n^{2.2131}\big)\) time for the
current values of fast rectangular matrix multiplication. We achieve the same
running time for the computation of the rank and nullspace of a sparse matrix
over a finite field. This improvement relies on two key techniques. First, we
adopt the decomposition of an arbitrary matrix into block Krylov and Hankel
matrices from Eberly et al. (ISSAC 2007). Second, we show how to recover the
explicit inverse of a block Hankel matrix using low displacement rank
techniques for structured matrices and fast rectangular matrix multiplication
algorithms. We generalize our inversion method to block structured matrices
with other displacement operators and strengthen the best known upper bounds
for explicit inversion of block Toeplitz-like and block Hankel-like matrices,
as well as for explicit inversion of block Vandermonde-like matrices with
structured blocks. As a further application, we improve the complexity of
several algorithms in topological data analysis and in finite group theory.
We prove lower bounds for higher-order methods in smooth non-convex finite-sum
optimization.
Our contribution is threefold: We first show that a deterministic algorithm cannot
profit
from the finite-sum structure of the objective, and that simulating a pth-order
regularized
method on the whole function by constructing exact gradient information is optimal
up to constant factors.
We further show lower bounds for randomized algorithms and compare them with the
best known upper bounds.
To address some gaps between the bounds, we propose a new second-order smoothness
assumption that can be
seen as an analogue of the first-order mean-squared smoothness assumption. We prove
that it is sufficient
to ensure state-of-the-art convergence guarantees, while allowing for a sharper
lower bound.
We give almost-linear-time algorithms for constructing sparsifiers
with \(n \text{poly}(\log n)\) edges that approximately preserve weighted
\((\ell^{2}_2 + \ell^{p}_p)\) flow or voltage objectives on graphs. For
flow objectives, this is the first sparsifier construction for such
mixed objectives beyond unit \(\ell_p\) weights, and is based on
expander decompositions. For voltage objectives, we give the first
sparsifier construction for these objectives, which we build using
graph spanners and leverage score sampling. Together with the
iterative refinement framework of [Adil et al, SODA 2019], and a new
multiplicative-weights based constant-approximation algorithm for
mixed-objective flows or voltages, we show how to find
\((1+2^{-\text{poly}(\log n)})\) approximations for weighted
\(\ell_p\)-norm minimizing flows or voltages in
\(p(m^{1+o(1)} + n^{4/3 + o(1)})\) time for \(p=\omega(1),\) which is
almost-linear for graphs that are slightly dense
(\(m \ge n^{4/3 + o(1)}\)).
We prove a matrix discrepancy bound that strengthens the famous
Kadison-Singer result of Marcus, Spielman, and Srivastava. Consider any
independent scalar random variables \(ξ_1, \ldots, ξ_n\) with finite support,
e.g.
\(\{ \pm 1 \}\) or \(\{ 0,1 \}\)-valued random variables, or some combination
thereof. Let \(u_1, \dots, u_n \in \mathbb{C}^m\) and \( σ^2 = \left\|
\sum_{i=1}^n \text{Var}[ ξ_i ] (u_i u_i^{*})^2 \right\|.\) Then there exists
a choice of outcomes \(\varepsilon_1,\ldots,\varepsilon_n\) in the support of
\(ξ_1, \ldots, ξ_n\) s.t. \( \left \|\sum_{i=1}^n \mathbb{E} [ ξ_i] u_i
u_i^* - \sum_{i=1}^n \varepsilon_i u_i u_i^* \right \| \leq 4 σ.\) A
simple consequence of our result is an improvement of a Lyapunov-type theorem
of Akemann and Weaver.
We study the complexity of approximately solving packing linear programs. In the Real
RAM model, it is known how to solve packing LPs with N non-zeros in time
Õ(N/ϵ). We investigate whether the ϵ dependence in the running time
can be improved.
Our first main result relates the difficulty of this problem to
hardness assumptions for solving dense linear equations. We show that, in the Real
RAM model,
unless linear equations in matrices n × n with condition number O(n10)
can be solved to ϵ accuracy faster than Õ(n2.01 log(1/ϵ)), no algorithm
(1−ϵ)-approximately
solves a O(n)×O(n) packing LPs (where N = O(n2))
in time Õ(n2ϵ−0.0003). It would be surprising to solve linear
equations
in the Real RAM model this fast, as we currently cannot solve them faster than
Õ(nω), where
ω denotes the exponent in the running time for matrix multiplication in the Real RAM
model (and equivalently matrix inversion).
The current best bound on this exponent is roughly ω ≤ 2.372. Note, however, that a
fast solver for linear equations does not
directly imply faster matrix multiplication. But, our reduction shows that if fast
and accurate packing LP solvers exist, then either
linear equations can be solved much faster than matrix multiplication or the matrix
multiplication constant is very close to 2.
Instantiating the same reduction with different parameters, we show that unless
linear equations in matrices with condition number
O(n1.5) can be solved to ϵ accuracy faster than Õ(n2.372
log(1/ϵ)), no
algorithm (1 – ϵ)-approximately solves packing LPs in time
Õ(n2ϵ−0.067).
Thus smaller improvements in the exponent for ϵ in the running time of Packing LP
solvers also imply improvements in the current
state-of-the-art for solving linear equations.
Our second main result relates the difficulty of approximately solving packing
linear programs to hardness assumptions for solving sparse linear equations: In the
Real RAM model, unless well-conditioned sparse systems
of linear equations can be solved faster than Õ((no. non-zeros of matrix) ),
no algorithm (1 – ϵ)-approximately solves packing LPs with N non-zeros in time
Õ(Nϵ−0.165). This
running time of Õ((no. non-zeros of matrix) )
is obtained by the classical Conjugate Gradient algorithm by a standard analysis.
Our reduction implies that if sufficiently good packing LP solvers exist, then this
long-standing best-known bound on the running time for solving well-conditioned
systems of linear equations is sub-optimal. While we prove results in the Real RAM
model, our condition number assumptions ensure that our results can be translated to
fixed point arithmetic with (log n)O(1) bits per number.
We present algorithms for solving a large class of flow and regression
problems on unit weighted graphs to \((1 + 1 / poly(n))\) accuracy in
almost-linear time. These problems include \(\ell_p\)-norm minimizing flow for
\(p\) large (\(p \in [ω(1), o(\log^{2/3} n) ]\)), and their duals,
\(\ell_p\)-norm semi-supervised learning for \(p\) close to \(1\).
As \(p\) tends to infinity, \(\ell_p\)-norm flow and its dual tend to max-flow
and min-cut respectively. Using this connection and our algorithms, we give an
alternate approach for approximating undirected max-flow, and the first
almost-linear time approximations of discretizations of total variation
minimization objectives.
This algorithm demonstrates that many tools previous viewed as limited to
linear systems are in fact applicable to a much wider range of convex
objectives. It is based on the the routing-based solver for Laplacian linear
systems by Spielman and Teng (STOC '04, SIMAX '14), but require several new
tools: adaptive non-linear preconditioning, tree-routing based
ultra-sparsification for mixed \(\ell_2\) and \(\ell_p\) norm objectives, and
decomposing graphs into uniform expanders.
We give improved algorithms for the \(\ell_{p}\)-regression problem, \(\min_{x}
\|x\|_{p}\) such that \(A x=b,\) for all \(p \in (1,2) \cup (2,\infty).\) Our
algorithms obtain a high accuracy solution in \(\tilde{O}_{p}(m^{\frac{|p-2|}{2p
+ |p-2|}}) \le \tilde{O}_{p}(m^{\frac{1}{3}})\) iterations, where each iteration
requires solving an \(m \times m\) linear system, \(m\) being the dimension of the
ambient space.
By maintaining an approximate inverse of the linear systems that we solve in
each iteration, we give algorithms for solving \(\ell_{p}\)-regression to \(1 /
\text{poly}(n)\) accuracy that run in time \(\tilde{O}_p(m^{\max\{ω,
7/3\}}),\) where \(ω\) is the matrix multiplication constant. For the current
best value of \(ω> 2.37\), we can thus solve \(\ell_{p}\) regression as fast
as \(\ell_{2}\) regression, for all constant \(p\) bounded away from \(1.\)
Our algorithms can be combined with fast graph Laplacian linear equation
solvers to give minimum \(\ell_{p}\)-norm flow / voltage solutions to \(1 /
\text{poly}(n)\) accuracy on an undirected graph with \(m\) edges in
\( \tilde{O}_{p}(m^{1 + \frac{|p-2|}{2p + |p-2|}}) \le
\tilde{O}_{p}(m^{\frac{4}{3}}) \) time.
For sparse graphs and for matrices with similar dimensions, our iteration
counts and running times improve on the \(p\)-norm regression algorithm by
[Bubeck-Cohen-Lee-Li STOC`18] and general-purpose convex optimization
algorithms. At the core of our algorithms is an iterative refinement scheme for
\(\ell_{p}\)-norms, using the smoothed \(\ell_{p}\)-norms introduced in the work of
Bubeck et al. Given an initial solution, we construct a problem that seeks to
minimize a quadratically-smoothed \(\ell_{p}\) norm over a subspace, such that a
crude solution to this problem allows us to improve the initial solution by a
constant factor, leading to algorithms with fast convergence.
Strongly Rayleigh distributions are a class of negatively dependent
distributions of binary-valued random variables [Borcea, Branden, Liggett JAMS
09]. Recently, these distributions have played a crucial role in the analysis
of algorithms for fundamental graph problems, e.g. Traveling Salesman Problem
[Gharan, Saberi, Singh FOCS 11]. We prove a new matrix Chernoff bound for
Strongly Rayleigh distributions.
As an immediate application, we show that adding together the Laplacians of
\(ε^{-2} \log^2 n\) random spanning trees gives an \((1\pm ε)\)
spectral sparsifiers of graph Laplacians with high probability. Thus, we
positively answer an open question posed in [Baston, Spielman, Srivastava, Teng
JACM 13]. Our number of spanning trees for spectral sparsifier matches the
number of spanning trees required to obtain a cut sparsifier in [Fung,
Hariharan, Harvey, Panigraphi STOC 11]. The previous best result was by naively
applying a classical matrix Chernoff bound which requires \(ε^{-2} n \log
n\) spanning trees. For the tree averaging procedure to agree with the original
graph Laplacian in expectation, each edge of the tree should be reweighted by
the inverse of the edge leverage score in the original graph. We also show that
when using this reweighting of the edges, the Laplacian of single random tree
is bounded above in the PSD order by the original graph Laplacian times a
factor \(\log n\) with high probability, i.e. \(L_T \preceq O(\log n) L_G\).
We show a lower bound that almost matches our last result, namely that in
some graphs, with high probability, the random spanning tree is \(\it{not}\)
bounded above in the spectral order by \(\frac{\log n}{\log\log n}\) times the
original graph Laplacian. We also show a lower bound that in \(ε^{-2}
\log n\) spanning trees are necessary to get a \((1\pm ε)\) spectral
sparsifier.
We show how to solve directed Laplacian systems in nearly-linear time. Given
a linear system in an \(n \times n\) Eulerian directed Laplacian with \(m\) nonzero
entries, we show how to compute an \(ε\)-approximate solution in time \(O(m
\log^{O(1)} (n) \log (1/ε))\). Through reductions from [Cohen et al.
FOCS'16] , this gives the first nearly-linear time algorithms for computing
\(ε\)-approximate solutions to row or column diagonally dominant linear
systems (including arbitrary directed Laplacians) and computing
\(ε\)-approximations to various properties of random walks on directed
graphs, including stationary distributions, personalized PageRank vectors,
hitting times, and escape probabilities. These bounds improve upon the recent
almost-linear algorithms of [Cohen et al. STOC'17], which gave an algorithm to
solve Eulerian Laplacian systems in time \(O((m+n2^{O(\sqrt{\log n \log \log
n})})\log^{O(1)}(n ε^{-1}))\).
To achieve our results, we provide a structural result that we believe is of
independent interest. We show that Laplacians of all strongly connected
directed graphs have sparse approximate LU-factorizations. That is, for every
such directed Laplacian \({\mathbf{L}}\), there is a lower triangular matrix
\(\boldsymbol{\mathit{\mathfrak{L}}}\) and an upper triangular matrix
\(\boldsymbol{\mathit{\mathfrak{U}}}\), each with at most \(\tilde{O}(n)\)
nonzero entries, such that their product \(\boldsymbol{\mathit{\mathfrak{L}}}
\boldsymbol{\mathit{\mathfrak{U}}}\) spectrally approximates \({\mathbf{L}}\)
in an appropriate norm. This claim can be viewed as an analogue of recent work
on sparse Cholesky factorizations of Laplacians of undirected graphs. We show
how to construct such factorizations in nearly-linear time and prove that, once
constructed, they yield nearly-linear time algorithms for solving directed
Laplacian systems.
We present an asymptotically faster algorithm for solving linear systems in
well-structured 3-dimensional truss stiffness matrices. These linear systems
arise from linear elasticity problems, and can be viewed as extensions of graph
Laplacians into higher dimensions. Faster solvers for the 2-D variants of such
systems have been studied using generalizations of tools for solving graph
Laplacians [Daitch-Spielman CSC'07, Shklarski-Toledo SIMAX'08].
Given a 3-dimensional truss over \(n\) vertices which is formed from a union of
\(k\) convex structures (tetrahedral meshes) with bounded aspect ratios, whose
individual tetrahedrons are also in some sense well-conditioned, our algorithm
solves a linear system in the associated stiffness matrix up to accuracy
\(ε\) in time \(O(k^{1/3} n^{5/3} \log (1 / ε))\). This
asymptotically improves the running time \(O(n^2)\) by Nested Dissection for all
\(k \ll n\).
We also give a result that improves on Nested Dissection even when we allow
any aspect ratio for each of the \(k\) convex structures (but we still require
well-conditioned individual tetrahedrons). In this regime, we improve on Nested
Dissection for \(k \ll n^{1/44}\).
The key idea of our algorithm is to combine nested dissection and support
theory. Both of these techniques for solving linear systems are well studied,
but usually separately. Our algorithm decomposes a 3-dimensional truss into
separate and balanced regions with small boundaries. We then bound the spectrum
of each such region separately, and utilize such bounds to obtain improved
algorithms by preconditioning with partial states of separator-based Gaussian
elimination.
We show that if the nearly-linear time solvers for Laplacian matrices and
their generalizations can be extended to solve just slightly larger families of
linear systems, then they can be used to quickly solve all systems of linear
equations over the reals. This result can be viewed either positively or
negatively: either we will develop nearly-linear time algorithms for solving
all systems of linear equations over the reals, or progress on the families we
can solve in nearly-linear time will soon halt.
We present an algorithm that, with high probability, generates a random
spanning tree from an edge-weighted undirected graph in
\(\tilde{O}(n^{4/3}m^{1/2}+n^{2})\) time (The \(\tilde{O}(\cdot)\) notation hides
\(\operatorname{polylog}(n)\) factors). The tree is sampled from a distribution
where the probability of each tree is proportional to the product of its edge
weights. This improves upon the previous best algorithm due to Colbourn et al.
that runs in matrix multiplication time, \(O(n^ω)\). For the special case of
unweighted graphs, this improves upon the best previously known running time of
\(\tilde{O}(\min\{n^ω,m\sqrt{n},m^{4/3}\})\) for \(m \gg n^{5/3}\) (Colbourn
et al. '96, Kelner-Madry '09, Madry et al. '15).
The effective resistance metric is essential to our algorithm, as in the work
of Madry et al., but we eschew determinant-based and random walk-based
techniques used by previous algorithms. Instead, our algorithm is based on
Gaussian elimination, and the fact that effective resistance is preserved in
the graph resulting from eliminating a subset of vertices (called a Schur
complement). As part of our algorithm, we show how to compute
\(ε\)-approximate effective resistances for a set \(S\) of vertex pairs via
approximate Schur complements in \(\tilde{O}(m+(n + |S|)ε^{-2})\) time,
without using the Johnson-Lindenstrauss lemma which requires \(\tilde{O}(
\min\{(m + |S|)ε^{-2}, m+nε^{-4} +|S|ε^{-2}\})\) time. We
combine this approximation procedure with an error correction procedure for
handing edges where our estimate isn't sufficiently accurate.
A spectral sparsifier of a graph \(G\) is a sparser graph \(H\) that
approximately preserves the quadratic form of \(G\), i.e. for all vectors \(x\),
\(x^T L_G x \approx x^T L_H x\), where \(L_G\) and \(L_H\) denote the respective
graph Laplacians. Spectral sparsifiers generalize cut sparsifiers, and have
found many applications in designing graph algorithms. In recent years, there
has been interest in computing spectral sparsifiers in semi-streaming and
dynamic settings. Natural algorithms in these settings often involve repeated
sparsification of a graph, and accumulation of errors across these steps. We
present a framework for analyzing algorithms that perform repeated
sparsifications that only incur error corresponding to a single sparsification
step, leading to better results for many resparsification-based algorithms. As
an application, we show how to maintain a spectral sparsifier in the
semi-streaming setting: We present a simple algorithm that, for a graph \(G\) on
\(n\) vertices and \(m\) edges, computes a spectral sparsifier of \(G\) with \(O(n
\log n)\) edges in a single pass over \(G\), using only \(O(n \log n)\) space, and
\(O(m \log^2 n)\) total time. This improves on previous best semi-streaming
algorithms for both spectral and cut sparsifiers by a factor of \(\log{n}\) in
both space and runtime. The algorithm extends to semi-streaming row sampling
for general PSD matrices. We also use our framework to combine a spectral
sparsification algorithm by Koutis with improved spanner constructions to give
a parallel algorithm for constructing \(O(n\log^2{n}\log\log{n})\) sized spectral
sparsifiers in \(O(m\log^2{n}\log\log{n})\) time. This is the best known
combinatorial graph sparsification algorithm.The size of the sparsifiers is
only a factor \(\log{n}\log\log{n}\) more than ones produced by numerical
routines.
We show how to perform sparse approximate Gaussian elimination for Laplacian
matrices. We present a simple, nearly linear time algorithm that approximates a
Laplacian by a matrix with a sparse Cholesky factorization, the version of
Gaussian elimination for symmetric matrices. This is the first nearly linear
time solver for Laplacian systems that is based purely on random sampling, and
does not use any graph theoretic constructions such as low-stretch trees,
sparsifiers, or expanders. The crux of our analysis is a novel concentration
bound for matrix martingales where the differences are sums of conditionally
independent variables.
We introduce the sparsified Cholesky and sparsified multigrid algorithms for
solving systems of linear equations. These algorithms accelerate Gaussian
elimination by sparsifying the nonzero matrix entries created by the
elimination process. We use these new algorithms to derive the first nearly
linear time algorithms for solving systems of equations in connection
Laplacians, a generalization of Laplacian matrices that arise in many problems
in image and signal processing. We also prove that every connection Laplacian
has a linear sized approximate inverse. This is an LU factorization with a
linear number of nonzero entries that is a strong approximation of the original
matrix. Using such a factorization one can solve systems of equations in a
connection Laplacian in linear time. Such a factorization was unknown even for
ordinary graph Laplacians.
independent variables.
Given a directed acyclic graph \(G,\) and a set of values \(y\) on the vertices,
the Isotonic Regression of \(y\) is a vector \(x\) that respects the partial order
described by \(G,\) and minimizes \(||x-y||,\) for a specified norm. This paper
gives improved algorithms for computing the Isotonic Regression for all
weighted \(\ell_{p}\)-norms with rigorous performance guarantees. Our algorithms
are quite practical, and their variants can be implemented to run fast in
practice.
We develop fast algorithms for solving regression problems on graphs where
one is given the value of a function at some vertices, and must find its
smoothest possible extension to all vertices. The extension we compute is the
absolutely minimal Lipschitz extension, and is the limit for large \(p\) of
\(p\)-Laplacian regularization. We present an algorithm that computes a minimal
Lipschitz extension in expected linear time, and an algorithm that computes an
absolutely minimal Lipschitz extension in expected time \(\widetilde{O} (m n)\).
The latter algorithm has variants that seem to run much faster in practice.
These extensions are particularly amenable to regularization: we can perform
\(l_{0}\)-regularization on the given values in polynomial time and
\(l_{1}\)-regularization on the initial function values and on graph edge weights
in time \(\widetilde{O} (m^{3/2})\).
We show an algorithm for solving symmetric diagonally dominant (SDD) linear systems
with m non-zero entries to a relative error of ε in O(m log1/2n
logcn log(1/ε)) time. Our approach follows the recursive preconditioning
framework, which aims to reduce graphs to trees using iterative methods. We improve
two key components of this framework: random sampling and tree embeddings. Both of
these components are used in a variety of other algorithms, and our approach also
extends to the dual problem of computing electrical flows.
We show that preconditioners constructed by random sampling can perform well without
meeting the standard requirements of iterative methods. In the graph setting, this
leads to ultra-sparsifiers that have optimal behavior in expectation.
The improved running time makes previous low stretch embedding algorithms the running
time bottleneck in this framework. In our analysis, we relax the requirement of
these embeddings to snowflake spaces. We then obtain a two-pass approach algorithm
for constructing optimal embeddings in snowflake spaces that runs in O(m log log n)
time. This algorithm is also readily parallelizable.
We show that preconditioners constructed by random sampling can perform well
without meeting the standard requirements of iterative methods. When applied to
graph Laplacians, this leads to ultra-sparsifiers that in expectation behave as
the nearly-optimal ones given by [Kolla-Makarychev-Saberi-Teng STOC`10].
Combining this with the recursive preconditioning framework by [Spielman-Teng
STOC`04] and improved embedding algorithms, this leads to algorithms that solve
symmetric diagonally dominant linear systems and electrical flow problems in
expected time close to \(m\log^{1/2}n\).
We give a generalized definition of stretch that simplifies the efficient
construction of low-stretch embeddings suitable for graph algorithms. The
generalization, based on discounting highly stretched edges by taking their
\(p\)-th power for some \(0 < p < 1\), is directly related to performances of
existing algorithms. This discounting of high-stretch edges allows us to treat
many classes of edges with coarser granularity. It leads to a two-pass approach
that combines bottom-up clustering and top-down decompositions to construct
these embeddings in \(\mathcal{O}(m\log\log{n})\) time. Our algorithm
parallelizes readily and can also produce generalizations of low-stretch
subgraphs.
Our implementations of the lex-minimization
algorithms from the paper
Algorithms for Lipschitz Learning on Graphs
.
The code was written by Anup Rao, Sushant Sachdeva,
Dan Spielman, and myself.
