About Me
I am an assistant professor at
the Department of Computer Science, ETH
Zurich,
where I joined in the fall 2019.
My research focuses on fast algorithms for graph problems and convex optimization,
on probability and discrepancy theory, finegrained complexity theory, and applications in
machine learning.
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.
You can read about my work on almostlinear time algorithms for maximum
and minimum cost flow in this
Quanta article "Researchers Achieve ‘Absurdly Fast’ Algorithm for Network
Flow" (Jun 8th, 2022).
ShangHua Teng wrote an excellent technical perspective on this work for
Communications of the ACM (Dec 13th, 2023).
Nikhil Srivastava wrote another very informative discussion
of our minimumcost flow algorithm and our recent work on almostlinear time algorithms
for many problems in 'incremental graphs' in the Simons Institute Newsletter (Jan 22nd, 2024).
ETH Zurich News has also written about my flow algorithms and algorithms for 'partially dynamic' graphs
here (Jun 28th, 2024).
See also publications below.
My CV.
PhD and Postdoc Applications
PhD openings
If you're interested in applying to do a PhD in our group,
you can send an email to applicationskyng@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 twoyear 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 applicationskyng@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.
Group

Maximilian
Probst Gutenberg, established researcher, Fall 2020present

Ming Ding, PhD candidate, Fall 2020present

Federico Soldà, PhD candidate, Fall 2020present

Simon Meierhans, PhD candidate,
Fall 2021present

Aurelio Sulser, PhD candidate, Fall 2022present
Teaching

ETH Zurich; Advanced Graph Algorithms and Optimization, Spring
2023,
2022,
2021,
2020.

ETH Zurich; Algorithms, Probability, and Computing, Fall
2022,
2021,
2020.

Harvard; AM 221: Advanced Optimization, Spring 2018.
Thesis and project supervision
Our group supervises bachelor and master's theses of students in ETHZ DINFK, 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.
Learn more about our thesis and project
supervision here.
Papers

AlmostLinear Time Algorithms for Decremental Graphs:
MinCost Flow and More via Duality

with Jan van den Brand, Li Chen, Yang P. Liu, Maximilian Probst Gutenberg, and
Sushant Sachdeva.

To appear in FOCS 2024.

We give the first almostlinear 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 almostlinear time algorithms for approximating the minimumcost flow value and \(s\)\(t\) distance on such decremental graphs.
Our framework additionally allows us to maintain decremental strongly connected components in almostlinear time deterministically.
These algorithms also improve over the current best known runtimes for statically computing minimumcost flow, in both the randomized and deterministic settings.
We obtain our algorithms by taking the dual perspective, which yields cutbased algorithms.
More precisely, our algorithm computes the flow via a sequence of \(m^{1+o(1)}\) dynamic minratio cut problems, the dual analog of the dynamic minratio cycle problem that underlies recent fast algorithms for minimumcost flow. Our main technical contribution is a new data structure that returns an approximately optimal minratio cut in amortized \(m^{o(1)}\) time by maintaining a treecut sparsifier. This is achieved by devising a new algorithm to maintain the dynamic expander hierarchy of [GoranciRäckeSaranurakTan, 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.

Optimal Electrical Oblivious Routing on Expanders

with Cella Florescu, Maximilian Probst Gutenberg, and Sushant Sachdeva.

In ICALP 2024.

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 wellmotivated by the current stateoftheart of fast algorithms for \(\ell_{\infty}\) oblivious routings that reduce to the expandercase 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^{(12/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^{(12/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)\).

A Framework for Parallelizing Approximate Gaussian Elimination

with Yves Baumann.

In SPAA 2024.

In a breakthrough result, Spielman and Teng (2004) developed a nearlylinear time solver for Laplacian linear equations, i.e. equations where the coefficient matrix is symmetric with nonnegative diagonals and zero row sums. Since the development of the SpielmanTeng 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 nearlylinear work and sublinear depth. Our framework allows us to parallelize any Laplacian solver based on repeated singlevertex 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 workefficient in the sense of matching the sequential work of these algorithms.
Our parallelization framework is very simple: We sample a subset of the current lowdegree 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 singlevertex 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 nearlylinear work.

AlmostLinear Time Algorithms for Incremental Graphs:
Cycle Detection, SCCs, st Shortest Path, and MinimumCost Flow

with Li Chen, Yang P. Liu, Simon Meierhans, and Maximilian Probst Gutenberg.

In STOC 2024.


We give the first almostlinear time algorithms for several problems in incremental
graphs
including cycle detection, strongly connected component maintenance, \(s\)\(t\)
shortest path, maximum flow, and minimumcost flow.
To solve these problems, we give a deterministic data structure that returns a
\(m^{o(1)}\)approximate minimumratio cycle in fully dynamic graphs in amortized
\(m^{o(1)}\) time per update.
Combining this with the interior point method framework of BrandLiuSidford (STOC
2023) gives the first almostlinear time algorithm for deciding the first update in
an incremental graph after which the cost of the minimumcost flow attains value at
most some given threshold \(F\).
By rather direct reductions to minimumcost 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 almostlinear time
algorithm for minimumcost flow by removing the need for complicated modeling of a
restricted adversary, in contrast to recent randomized and deterministic algorithms
for minimumcost flow in
ChenKyngLiuPengProbst GutenbergSachdeva (FOCS 2022) &
BrandChenKyngLiuPengProbst GutenbergSachdevaSidford (FOCS 2023).
At a high level, our algorithm dynamizes the \(\ell_1\) oblivious routing of
Rozho\v{n}GrunauHaeuplerZuzicLi (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
KyngMeierhansProbst 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 ChenKyngLiuPengProbst GutenbergSachdeva (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öferDasDobkinJosephSoares
(Discrete & Computational Geometry 1993).

A Dynamic Shortest Paths Toolbox: LowCongestion Vertex Sparsifiers and their
Applications

with Simon Meierhans and Maximilian Probst Gutenberg.

In STOC 2024.

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
allpairs shortest paths (APSP) with \emph{worstcase} 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 singlesource
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 flowrouting 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 \(Am^{o(1)}\) vertices and edges, and can be updated in
worstcase time \(m^{o(1)}\).
Crucially, our vertex sparsifier construction allows us to maintain a low
edgecongestion embedding of \(H\) into \(G\), which is needed for our applications.

Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update
Time

with Jan van den Brand, Li Chen, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg,
Sushant Sachdeva, and Aaron Sidford.

In SODA 2024.

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
edgeinsertion 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 minimumratio cycle problem that underlie previous advances on the
maximum flow problem [ChenKyngLiuPengProbst GutenbergSachdeva, FOCS '22] as
well as recent dynamic maximum flow algorithms [v.d.BrandLiuSidford, 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 minimumratio cycle subproblems that
allows us to apply known data structures and bypass issues arising from adaptive
queries.

A Deterministic AlmostLinear Time Algorithm for MinimumCost Flow

with Jan van den Brand, Li Chen, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg,
Sushant Sachdeva, and Aaron Sidford.

In FOCS 2023.

We give a deterministic algorithm that computes exact maximum flows and minimumcost
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
maximumflow in graphs with polynomial bounded capacities since the work of
GoldbergRao [J.ACM '98].
Our algorithm is based on the flow framework of
ChenKyngLiuPengGutenbergSachdeva [FOCS '22] that computes the optimal flow
through a sequence of \(m^{1+o(1)}\) approximate undirected minimumratio cycles. We
obtain a deterministic dynamic graph datastructure to process such a sequence of
minimumratio 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 datastructure from Chen et al. that was
based on sampling random lowstretch 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 lowstretch spanning tree on graphs
with polynomially large lengths, with subpolynomial average stretch and requiring
only subpolynomial amortized update time.

Robust and Practical Solution of Laplacian Equations by Approximate Elimination

with Yuan Gao and Daniel A. Spielman.

Manuscript.

We introduce a new algorithm and software for solving linear equations in symmetric
diagonally dominant matrices with nonpositive offdiagonal entries (SDDM matrices),
including Laplacian matrices. We use preconditioned 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 nonzero 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
singlethreaded performance to that of current stateoftheart solvers
Combinatorial Multigrid (CMG), BoomerAMGpreconditioned 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.
Arxiv

This paper describes ApproxChol, the Laplacian solver in
Laplacians.jl.

Maintaining Expander Decompositions via Sparse Cuts

with Yiding Hua, Maximilian Probst Gutenberg, and Zihang Wu.

In SODA 2023.

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 metaalgorithm 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 stateoftheart work. In
all settings, our algorithm matches the runtimes 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 StronglyConnected Components (SCCs) in directed graphs undergoing
edge deletions, and for maintaining connectivity in undirected fullydynamic
graphs, both matching the current stateoftheart runtimes up to
subpolynomial factors.
Arxiv

A Simple Framework for Finding Balanced Sparse Cuts via APSP

with Li Chen, Maximilian Probst Gutenberg, and Sushant Sachdeva.

In SOSA 2023.

We present a very simple and intuitive algorithm to find balanced sparse cuts
in a graph via shortestpaths. Our algorithm combines a new
multiplicativeweights framework for solving unitweight multicommodity 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 datastructures 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 almostlinear time algorithm matches the stateoftheart in
randomized and deterministic settings up to subpolynomial factors, while being
significantly simpler to understand and analyze, especially compared to the
only almostlinear time deterministic algorithm, a recent breakthrough by
ChuzhoyGaoLiNanongkaiPengSaranurak (FOCS 2020).
Arxiv

Maximum Flow and MinimumCost Flow in AlmostLinear Time

with Li Chen, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva.

In FOCS 2022.
Won the FOCS Best Paper Award.

Won an inaugural ICBS Frontiers of Science Award in Theoretical Computer Science.


We give an algorithm that computes exact maximum flows and minimumcost 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 minimumratio 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 edgeseparable convex functions to high
accuracy. This gives an almostlinear time algorithm for several problems
including entropyregularized optimal transport, matrix scaling, \(p\)norm
flows, and isotonic regression.

Derandomizing Random Walks in AlmostLinear Time

with Simon Meierhans and Maximilian Probst Gutenberg.

In FOCS 2022.

In this article, we present the first deterministic directed Laplacian L
systems solver that runs in time almostlinear in the number of nonzero
entries of L. Previous reductions imply the first deterministic almostlinear
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 almostlinear 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 squaringbased framework of Cohen, Kelner,
Peebles, Peng, Rao, Sidford and Vladu (STOC 2017) and the sparsified
Choleskybased framework of Peng and Song (STOC 2022).
Arxiv

Scalar and Matrix Chernoff Bounds from \(\ell_{\infty}\)Independence

with Tali Kaufman and Federico Solda.

In SODA 2022.

We present new scalar and matrix Chernoffstyle 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(\logV)\) 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.
Arxiv

Incremental SSSP for Sparse Digraphs Beyond the Hopset Barrier

with Simon Meierhans and Maximilian Probst Gutenberg.

In SODA 2022.

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 runtime \(\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 partiallydynamic 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 buildup 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
partiallydynamic SSSP algorithm in sparse graphs to bypass the notorious
directed hopset barrier which is often seen as the fundamental challenge
towards achieving truly nearlinear time algorithms.
Arxiv

Hardness Results for Laplacians of Simplicial Complexes via SparseLinear Equation
Complete Gadgets

with Ming Ding, Maximilian Probst Gutenberg, and Peng Zhang.

In ICALP 2022.

We study linear equations in combinatorial Laplacians of kdimensional simplicial
complexes (kcomplexes), 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 nearlylinear time solvers exist for graph Laplacians.
However, nearlylinear time solvers for combinatorial Laplacians are only known for
restricted classes of complexes.
This paper shows that linear equations in combinatorial Laplacians of 2complexes
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 2complexes 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 nearlylinear time reduction from general
linear equations to combinatorial Laplacians of 2complexes. Our reduction preserves
the sparsity of the problem instances up to polylogarithmic factors.
Arxiv

TwoCommodity Flow is as Hard as Linear Programming

with Ming Ding and Peng Zhang.

In ICALP 2022.

We give a nearlylinear time reduction that encodes any linear
program as a 2commodity flow problem with only a polylogarithmic
blowup in size.
Our reduction applies to highaccuracy approximation algorithms and
exact algorithms.
Given an approximate solution to the 2commodity 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 2commodity flow problem can solve linear
programs in essentially the same time.
Given a directed graph with edge capacities and two sourcesink pairs, the goal of
the 2commodity flow problem is to maximize the sum of the flows routed between the
two sourcesink pairs subject to edge capacities and flow conservation.
A 2commodity flow problem can be formulated as a linear program,
which can be solved to high accuracy in almost the current matrix
multiplication time (CohenLeeSong JACM'21). In this paper, we show
that linear programs can be approximately solved, to high accuracy,
using 2commodity flow as well. As a corollary, if a 2commodity flow
problem can be approximately solved in time \(O(E^c
\operatorname{polylog}(UE\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 2commodity 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 polynomialtime reduction of a linear program to a 2commodity flow
problem (JACM’78). Itai's reduction shows that exactly solving 2commodity flow
and exactly solving linear programming are polynomialtime 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 2commodity flow and linear
programming are equivalent in strongly polynomial time.
Arxiv

Faster Sparse Matrix Inversion and Rank Computation in Finite Fields

with Sílvia Casacuberta.

In ITCS 2022.

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 Toeplitzlike and block Hankellike matrices,
as well as for explicit inversion of block Vandermondelike matrices with
structured blocks. As a further application, we improve the complexity of
several algorithms in topological data analysis and in finite group theory.
Arxiv

On the Oracle Complexity of HigherOrder Smooth NonConvex FiniteSum Optimization

with Nicolas Emmenegger and Ahad N. Zehmakan.

In AISTATS 2022 and in
the ICML 2021 workshop 'Beyond firstorder methods in ML systems'.

We prove lower bounds for higherorder methods in smooth nonconvex finitesum
optimization.
Our contribution is threefold: We first show that a deterministic algorithm cannot
profit
from the finitesum structure of the objective, and that simulating a pthorder
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 secondorder smoothness
assumption that can be
seen as an analogue of the firstorder meansquared smoothness assumption. We prove
that it is sufficient
to ensure stateoftheart convergence guarantees, while allowing for a sharper
lower bound.
Arxiv

Almostlineartime Weighted \(\ell_p\)norm Solvers in Slightly Dense Graphs via
Sparsification

with Deeksha Adil, Brian Bullins, and Sushant Sachdeva.

In ICALP 2021.

We give almostlineartime 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
multiplicativeweights based constantapproximation algorithm for
mixedobjective 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
almostlinear for graphs that are slightly dense
(\(m \ge n^{4/3 + o(1)}\)).
Arxiv

Four Deviations Suffice for Rank 1 Matrices

with Kyle Luh and Zhao Song.

In Advances in Mathematics, Volume 375, 2 December 2020.

We prove a matrix discrepancy bound that strengthens the famous
KadisonSinger 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 Lyapunovtype theorem
of Akemann and Weaver.

Packing LPs are Hard to Solve Accurately, Assuming Linear Equations are Hard

with Di Wang and Peng Zhang.

In SODA 2020.

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 nonzeros 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(n^{10})
can be solved to ϵ accuracy faster than Õ(n^{2.01} log(1/ϵ)), no algorithm
(1−ϵ)approximately
solves a O(n)×O(n) packing LPs (where N = O(n^{2}))
in time Õ(n^{2}ϵ^{−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(n^{1.5}) can be solved to ϵ accuracy faster than Õ(n^{2.372}
log(1/ϵ)), no
algorithm (1 – ϵ)approximately solves packing LPs in time
Õ(n^{2}ϵ^{−0.067}).
Thus smaller improvements in the exponent for ϵ in the running time of Packing LP
solvers also imply improvements in the current
stateoftheart 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 wellconditioned sparse systems
of linear equations can be solved faster than Õ((no. nonzeros of matrix) ),
no algorithm (1 – ϵ)approximately solves packing LPs with N nonzeros in time
Õ(Nϵ^{−0.165}). This
running time of Õ((no. nonzeros 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
longstanding bestknown bound on the running time for solving wellconditioned
systems of linear equations is suboptimal. 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.
Conference

Flows in Almost Linear Time via Adaptive Preconditioning

with Richard Peng, Sushant
Sachdeva, and Di Wang.

In STOC 2019.

We present algorithms for solving a large class of flow and regression
problems on unit weighted graphs to \((1 + 1 / poly(n))\) accuracy in
almostlinear 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 semisupervised learning for \(p\) close to \(1\).
As \(p\) tends to infinity, \(\ell_p\)norm flow and its dual tend to maxflow
and mincut respectively. Using this connection and our algorithms, we give an
alternate approach for approximating undirected maxflow, and the first
almostlinear 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 routingbased solver for Laplacian linear
systems by Spielman and Teng (STOC '04, SIMAX '14), but require several new
tools: adaptive nonlinear preconditioning, treerouting based
ultrasparsification for mixed \(\ell_2\) and \(\ell_p\) norm objectives, and
decomposing graphs into uniform expanders.

Iterative Refinement for \(\ell_p\)norm Regression

with Deeksha Adil, Richard Peng, and Sushant Sachdeva.

In SODA 2019.

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{p2}{2p
+ p2}}) \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{p2}{2p + p2}}) \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
[BubeckCohenLeeLi STOC`18] and generalpurpose 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 quadraticallysmoothed \(\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.

A Matrix Chernoff Bound for Strongly Rayleigh Distributions and Spectral Sparsifiers
from a few Random Spanning Trees

with Zhao Song.

In FOCS 2018.

Strongly Rayleigh distributions are a class of negatively dependent
distributions of binaryvalued 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.

Solving Directed Laplacians in Nearly Linear Time
through Sparse LU Factorizations

with Michael B. Cohen, Jonathan Kelner, John Peebles,
Richard Peng, Anup B. Rao, Aaron Sidford.

In FOCS 2018.

We show how to solve directed Laplacian systems in nearlylinear 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 nearlylinear 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
almostlinear 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 LUfactorizations. 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 nearlylinear time and prove that, once
constructed, they yield nearlylinear time algorithms for solving directed
Laplacian systems.

Incomplete Nested Dissection

with Richard Peng, Robert
Schwieterman, and Peng Zhang.

In STOC 2018.

We present an asymptotically faster algorithm for solving linear systems in
wellstructured 3dimensional 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 2D variants of such
systems have been studied using generalizations of tools for solving graph
Laplacians [DaitchSpielman CSC'07, ShklarskiToledo SIMAX'08].
Given a 3dimensional 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 wellconditioned, 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
wellconditioned 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 3dimensional 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 separatorbased Gaussian
elimination.

Approximate Gaussian Elimination

Rasmus Kyng.

My PhD dissertation, 2017.


Hardness Results for Structured Linear Systems

with Peng Zhang.

In FOCS 2017. Won the Machtey Award for Best Student
Paper.

In the SIAM Journal on Computing, Special Section FOCS 2017.

We show that if the nearlylinear 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 nearlylinear time algorithms for solving
all systems of linear equations over the reals, or progress on the families we
can solve in nearlylinear time will soon halt.

Sampling Random Spanning Trees Faster than Matrix Multiplication

with David Durfee, John Peebles, Anup B. Rao, and Sushant Sachdeva.

In STOC 2017.

We present an algorithm that, with high probability, generates a random
spanning tree from an edgeweighted 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, KelnerMadry '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 determinantbased and random walkbased
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 JohnsonLindenstrauss 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 Framework for Analyzing Resparsification Algorithms

with Jakub Pachocki, Richard Peng, and Sushant Sachdeva.

In SODA 2017.

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 semistreaming 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 resparsificationbased algorithms. As
an application, we show how to maintain a spectral sparsifier in the
semistreaming 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 semistreaming
algorithms for both spectral and cut sparsifiers by a factor of \(\log{n}\) in
both space and runtime. The algorithm extends to semistreaming 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.

Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple

with
Sushant Sachdeva.

In FOCS 2016.

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 lowstretch 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.

Sparsified Cholesky and Multigrid Solvers for Connection Laplacians

with
Yin Tat Lee,
Richard Peng,
Sushant Sachdeva, and
Daniel A. Spielman.

In STOC 2016.

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.

Fast, Provable Algorithms for Isotonic Regression in all \(\ell_p\)norms

with
Anup B. Rao and
Sushant Sachdeva.

In NIPS 2015.

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 \(xy,\) 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.

Our implementation of the
leastsquares Isotonic regression algorithm is available on
the Isotonic Github repository.

Algorithms for Lipschitz Learning on Graphs

with
Anup B. Rao,
Daniel A. Spielman, and
Sushant Sachdeva.

In COLT 2015.

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})\).

Our implementations of the lexminimization algorithms are available on
the YINSlex Github repository.

Solving SDD Linear Systems in Nearly \( m\log^{1/2}n \) Time

with
Michael B. Cohen,
Gary L. Miller,
Jakub W. Pachocki,
Richard Peng,
Anup B. Rao
and Shen Chen Xu.

In STOC 2014.

We show an algorithm for solving symmetric diagonally dominant (SDD) linear systems
with m nonzero entries to a relative error of ε in O(m log^{1/2}n
log^{c}n 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 ultrasparsifiers 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 twopass approach algorithm
for constructing optimal embeddings in snowflake spaces that runs in O(m log log n)
time. This algorithm is also readily parallelizable.
The paper Solving SDD Linear Systems in Nearly \( m\log^{1/2}n \) Time was a merged submission of
the following two papers:

Preconditioning in Expectation

with
Michael B. Cohen,
Jakub W. Pachocki,
Richard Peng,
and Anup B. Rao.

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 ultrasparsifiers that in expectation behave as
the nearlyoptimal ones given by [KollaMakarychevSaberiTeng STOC`10].
Combining this with the recursive preconditioning framework by [SpielmanTeng
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\).

Stretching Stretch

Michael B. Cohen,
Gary L. Miller,
Jakub W. Pachocki,
Richard Peng,
and Shen Chen Xu.

We give a generalized definition of stretch that simplifies the efficient
construction of lowstretch 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 highstretch edges allows us to treat
many classes of edges with coarser granularity. It leads to a twopass approach
that combines bottomup clustering and topdown decompositions to construct
these embeddings in \(\mathcal{O}(m\log\log{n})\) time. Our algorithm
parallelizes readily and can also produce generalizations of lowstretch
subgraphs.
Recent and Upcoming Talks

MPI Informatics Seminar;
Saarbrücken,
Winter, 2024.

Tutorial: Recent Results on Maximum and Minimumcost Flow.


Informal Blackboard Talks;
Simons Institute, Berkeley,
November
2023.

AlmostLinear Time Algorithms for Incremental Graphs:
Cycle Detection, SCCs, st Shortest Path, and MinimumCost Flow.


Georgia Tech College of Computing Seminar;
Atlanta,
September 2023.

Robust and Practical Solution of Laplacian Equations by Approximate Elimination.


ICALP;
Paderborn,
July, 2023.

Invited Plenary Talk, An AlmostLinear Time Algorithm for Maximum Flow and More.


DIMACS Workshop on Modern Techniques in Graph Algorithms;
New Brunswick,
June, 2023.

Tutorial: Maximum Flow and MinimumCost Flow in AlmostLinear Time.


Highlights of Algorithms;
Prague,
June, 2023.

Maximum Flow and MinimumCost Flow in AlmostLinear Time.


Seminar on Scalable Data Structures;
Dagstuhl,
June, 2023.

Dynamic spanners.


Perspectives on Matrix Computations: Theoretical Computer Science Meets Numerical
Analysis, BIRS Workshop;
Banff, January, 2023.

Robust and Practical Solution of Laplacian Equations by Approximate Elimination
(Video).
(Slides).


Swiss Winter School on Theoretical Computer Science;
EPFL and ETHZ,
January, 2023.

Lecture series: Maximum Flow and MinimumCost Flow in AlmostLinear Time.

Notes and problem sets.


Department of Computer Science Colloquium;
Yale University,
November, 2022.

Maximum Flow and MinimumCost Flow in AlmostLinear Time.


Columbia Theory Seminar;
Columbia University,
November, 2022.

Maximum Flow and MinimumCost Flow in AlmostLinear Time.


Bernoulli Center Workshop: Modern Trends in Combinatorial Optimization;
EPFL,
July, 2022.

Maximum Flow and MinimumCost Flow in AlmostLinear Time.


Milan Theory Workshop: Spectral and Convex Optimization Techniques in Graph
Algorithms;
Bocconi University,
June, 2022.

Maximum Flow and MinimumCost Flow in AlmostLinear Time.


Algorithms and Foundations for Data Science Workshop;
Nanyang Technological University and Carnegie Mellon University,
June, 2022.

Scalar and Matrix Chernoff Bounds from \(\ell_{\infty}\)Independence.


European Meeting on Algorithmic Challenges of Big Data;
Warsaw,
May, 2022.

AlmostLinear Time Algorithms for Maximum Flow and More.


TCS+ Talk;
April, 2022.

AlmostLinear Time Algorithms for Maximum Flow and More.
(Video).


Hausdorff Program on Discrete Optimization, Workshop: Approximation and Relaxation;
November, 2021.

TwoCommodity Flow is as Hard as Linear Programming.


INFORMS 2021 Session on Bridging Discrete and Continuous Optimization;
October, 2021.

A Numerical Analysis Approach to Convex Optimization.


Hausdorff Program on Discrete Optimization, Workshop: Continuous Approaches to Discrete
Optimization;
October, 2021.

A Numerical Analysis Approach to Convex Optimization.


CMC Seminar; Panel Discussion,
September, 2021.

Laplacian Solvers.


WALD(O);
Virtual Conference,
August,
2021.

Hardness Results for Structured Linear Equations and Programs.


ADFOCS;
Virtual summer school,
JulyAugust,
2021.

Graphs, Sampling, and Iterative methods (three lectures).


SIAM Annual Meeting;
Virtual conference,
July,
2021.

TwoCommodity Flow is as Hard as Linear Programming.


Georgetown University Computer Science Colloquium;
Georgetown,
April
2021.

A Numerical Analysis Approach to Convex Optimization
(Video).


Hebrew University Theory Seminar;
Jerusalem,
January
2021.

A Numerical Analysis Approach to Convex Optimization
(Slides).


EPFL Theory Seminar;
Lausanne,
March
2020.

A Numerical Analysis Approach to Convex Optimization
(Slides).


ICCOPT;
Berlin,
August
2019.

Optimization on Graphs
(Slides).


UT Austin Theory Seminar;
May
2019.

A Numerical Analysis Approach to Convex Optimization.


Harvard Theory of Computation Seminar;
February
2019.

A Numerical Analysis Approach to Convex Optimization.


Beyond Randomized Rounding and the Probabilistic
Method Workshop;
Simons Institute, Berkeley,
February
2019.

A Matrix Chernoff Bound for Strongly Rayleigh
Distributions and Spectral Sparsifiers from a few Random Spanning Trees
(Video),
(Slides).


SODA 2019;
San Diego,
January
2019.

Iterative Refinement for \(\ell_p\)norm Regression.


Bridging Continuous and Discrete Optimization Reunion Workshop;
Simons Institute, Berkeley,
December
2018.

Iterative Refinement for \(\ell_p\)norm Regression.


Caltech Theory Seminar;
November
2018.

Approximate Gaussian Elimination
(Slides).


Northwestern Quarterly Theory Workshop;
Northwestern,
November
2018.

Analysis Using Matrix Martingales
(Slides).


FOCS;
Paris,
October
2018.

A Matrix Chernoff Bound for Strongly Rayleigh
Distributions and Spectral Sparsifiers from a few Random Spanning Trees.


FOCS;
Paris,
October
2018.

Solving Directed Laplacians in Nearly Linear Time through Sparse LU Factorizations.


Laplacian 2.0 Workshop;
FOCS, Paris,
October
2018.

Analysis Using Matrix Martingales
(Slides).


RNLA Workshop;
Simons Institute, Berkeley,
September
2018.

Matrix Martingales in Randomized Numerical
Linear Algebra
(Video).


HighPerformance Graph Algorithms Seminar;
Dagstuhl,
June 2018.

Optimization on Graphs.


Discrepancy & IP Workshop;
CWI Amsterdam, June 2018.

Matrix
Approximation by Row Sampling
(Notes).


GraphXD Workshop;
UC Berkeley,
March 2018.

Optimization on Graphs
(Video),
(Slides).


Michael Cohen Memorial Symposium;
Simons Institute, Berkeley,
November 2017.

Michael Cohen and Directed Laplacians
(Video).

More Talks

Stanford Theory Seminar; October 2017.
Approximate Gaussian Elimination.

FOCS, Berkeley; October 2017.
Hardness Results for Structured Linear Systems.

UC Berkeley; September 2017.
Hardness Results for Structured Linear Systems.

Google Research Mountain View; August 2017.
Hardness Results for Structured Linear Systems.

YPNG Seminar, Yale Dept. of Statistics and Data
Science; July 2017.
Approximate Gaussian Elimination.

MSR Redmond; January 2017.
Regression, Elimination, and Sampling on Graphs.

University of Copenhagen; January 2017.
Approximate Gaussian Elimination.

CMU; December 2016.
Approximate Gaussian Elimination.

Georgia Tech; November 2016.
Approximate Gaussian Elimination.

Princeton; October 2016.
Approximate Gaussian Elimination.

UC Berkeley; October 2016.
Approximate Gaussian Elimination.

Google Research NYC; October 2016.
Approximate Gaussian Elimination.

FOCS, New Brunswick; October 2016.
Approximate Gaussian Elimination.

MIT A&C Seminar; September 2016.
Approximate Gaussian Elimination.

Aarhus University; September 2016.
Lipschitz Learning on Graphs.

China Theory Week, Hong Kong; August 2016.
Approximate Gaussian Elimination.

SIAM Annual Meeting, Boston; July 2016.
Approximate Cholesky Factorization

STOC, Boston; June 2016.
Sparsified Cholesky and Multigrid Solvers for Connection Laplacians.

IT University of Copenhagen; December 2015.
Lipschitz Learning and Isotonic Regression on
Graphs
Code

Laplacians.jl

Laplacians.jl is a Julia package containing graph
algorithms, especially ones related to
spectral and algebraic graph theory, run by Dan Spielman.
The repo contains ApproxChol, our Laplacian solver from the paper
Robust and Practical Solution of Laplacian Equations by Approximate Elimination.

YINSlex Github Repository

Our implementations of the lexminimization
algorithms from the paper
Algorithms for Lipschitz Learning on Graphs
.
The code was written by Anup Rao, Sushant Sachdeva,
Dan Spielman, and myself.

Isotonic Github Repository

An implementation of the
leastsquares Isotonic regression algorithm
from the paper
Fast, Provable Algorithms for Isotonic Regression in all \(\ell_p\)norms
.
The code was written by Anup Rao, Sushant Sachdeva, and myself.
Contact
I can be reached by email at
[last name] @ inf.ethz.ch
[last name] = kyng