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 along with other topics in theoretical computer science
and applications in machine learning.
You can write to me to apply for a PhD or apply to our
Direct Doctorate
Program (joint Master's and PhD).
Candidates should have a strong background in theoretical computer science or mathematics.
My research is supported in part by grant no. 200021 204787 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" (June 8th, 2022).
This is based on joint work with with Li Chen, Yang Liu, Maximilian Probst Gutenberg, Richard
Peng, and Sushant Sachdeva.
See also publications below.
Group
Teaching
Thesis and project supervision
My 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

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.

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.
Quanta coverage

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

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. It was started by
Dan Spielman, and has contributions from Dan, Serban
Stan, myself and several others.

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