Publications - The Year Before Last

Large networks are useful in a wide range of applications. Sometimes problem
instances are composed of billions of entities. Decomposing and analyzing these
structures helps us gain new insights about our surroundings. Even if the final
application concerns a different problem (such as traversal, finding paths,
trees, and flows), decomposing large graphs is often an important subproblem
for complexity reduction or parallelization. This report is a summary of
discussions that happened at Dagstuhl seminar 23331 on "Recent Trends in Graph
Decomposition" and presents currently open problems and future directions in
the area of (hyper)graph decomposition.

A major technique in learning-augmented online algorithms is combining
multiple algorithms or predictors. Since the performance of each predictor may
vary over time, it is desirable to use not the single best predictor as a
benchmark, but rather a dynamic combination which follows different predictors
at different times. We design algorithms that combine predictions and are
competitive against such dynamic combinations for a wide class of online
problems, namely, metrical task systems. Against the best (in hindsight)
unconstrained combination of $\ell$ predictors, we obtain a competitive ratio
of $O(\ell^2)$, and show that this is best possible. However, for a benchmark
with slightly constrained number of switches between different predictors, we
can get a $(1+\epsilon)$-competitive algorithm. Moreover, our algorithms can be
adapted to access predictors in a bandit-like fashion, querying only one
predictor at a time. An unexpected implication of one of our lower bounds is a
new structural insight about covering formulations for the $k$-server problem.

This paper presents parallel and distributed algorithms for single-source
shortest paths when edges can have negative weights (negative-weight SSSP). We
show a framework that reduces negative-weight SSSP in either setting to
$n^{o(1)}$ calls to any SSSP algorithm that works with a virtual source. More
specifically, for a graph with $m$ edges, $n$ vertices, undirected hop-diameter
$D$, and polynomially bounded integer edge weights, we show randomized
algorithms for negative-weight SSSP with (i) $W_{SSSP}(m,n)n^{o(1)}$ work and
$S_{SSSP}(m,n)n^{o(1)}$ span, given access to an SSSP algorithm with
$W_{SSSP}(m,n)$ work and $S_{SSSP}(m,n)$ span in the parallel model, (ii)
$T_{SSSP}(n,D)n^{o(1)}$, given access to an SSSP algorithm that takes
$T_{SSSP}(n,D)$ rounds in $\mathsf{CONGEST}$. This work builds off the recent
result of [Bernstein, Nanongkai, Wulff-Nilsen, FOCS'22], which gives a
near-linear time algorithm for negative-weight SSSP in the sequential setting.
Using current state-of-the-art SSSP algorithms yields randomized algorithms
for negative-weight SSSP with (i) $m^{1+o(1)}$ work and $n^{1/2+o(1)}$ span in
the parallel model, (ii) $(n^{2/5}D^{2/5} + \sqrt{n} + D)n^{o(1)}$ rounds in
$\mathsf{CONGEST}$.
Our main technical contribution is an efficient reduction for computing a
low-diameter decomposition (LDD) of directed graphs to computations of SSSP
with a virtual source. Efficiently computing an LDD has heretofore only been
known for undirected graphs in both the parallel and distributed models. The
LDD is a crucial step of the algorithm in [Bernstein, Nanongkai, Wulff-Nilsen,
FOCS'22], and we think that its applications to other problems in parallel and
distributed models are far from being exhausted.

We present a randomized algorithm that computes single-source shortest paths
(SSSP) in $O(m\log^8(n)\log W)$ time when edge weights are integral and can be
negative. This essentially resolves the classic negative-weight SSSP problem.
The previous bounds are $\tilde O((m+n^{1.5})\log W)$ [BLNPSSSW FOCS'20] and
$m^{4/3+o(1)}\log W$ [AMV FOCS'20]. Near-linear time algorithms were known
previously only for the special case of planar directed graphs [Fakcharoenphol
and Rao FOCS'01].
In contrast to all recent developments that rely on sophisticated continuous
optimization methods and dynamic algorithms, our algorithm is simple: it
requires only a simple graph decomposition and elementary combinatorial tools.
In fact, ours is the first combinatorial algorithm for negative-weight SSSP to
break through the classic $\tilde O(m\sqrt{n}\log W)$ bound from over three
decades ago [Gabow and Tarjan SICOMP'89].

We show a fully dynamic algorithm for maintaining $(1+\epsilon)$-approximate
\emph{size} of maximum matching of the graph with $n$ vertices and $m$ edges
using $m^{0.5-\Omega_{\epsilon}(1)}$ update time. This is the first polynomial
improvement over the long-standing $O(n)$ update time, which can be trivially
obtained by periodic recomputation. Thus, we resolve the value version of a
major open question of the dynamic graph algorithms literature (see, e.g.,
[Gupta and Peng FOCS'13], [Bernstein and Stein SODA'16],[Behnezhad and Khanna
SODA'22]).
Our key technical component is the first sublinear algorithm for $(1,\epsilon
n)$-approximate maximum matching with sublinear running time on dense graphs.
All previous algorithms suffered a multiplicative approximation factor of at
least $1.499$ or assumed that the graph has a very small maximum degree.

In the dynamic approximate maximum bipartite matching problem we are given
bipartite graph $G$ undergoing updates and our goal is to maintain a matching
of $G$ which is large compared the maximum matching size $\mu(G)$. We define a
dynamic matching algorithm to be $\alpha$ (respectively $(\alpha,
\beta)$)-approximate if it maintains matching $M$ such that at all times $|M |
\geq \mu(G) \cdot \alpha$ (respectively $|M| \geq \mu(G) \cdot \alpha -
\beta$).
We present the first deterministic $(1-\epsilon )$-approximate dynamic
matching algorithm with $O(poly(\epsilon ^{-1}))$ amortized update time for
graphs undergoing edge insertions. Previous solutions either required
super-constant [Gupta FSTTCS'14, Bhattacharya-Kiss-Saranurak SODA'23] or
exponential in $1/\epsilon $
[Grandoni-Leonardi-Sankowski-Schwiegelshohn-Solomon SODA'19] update time. Our
implementation is arguably simpler than the mentioned algorithms and its
description is self contained. Moreover, we show that if we allow for additive
$(1, \epsilon \cdot n)$-approximation our algorithm seamlessly extends to also
handle vertex deletions, on top of edge insertions. This makes our algorithm
one of the few small update time algorithms for $(1-\epsilon )$-approximate
dynamic matching allowing for updates both increasing and decreasing the
maximum matching size of $G$ in a fully dynamic manner.

Bridging geometry and topology, curvature is a powerful and expressive invariant. While the utility of curvature has been theoretically and empirically confirmed in the context of manifolds and graphs, its generalization to the emerging domain of hypergraphs has remained largely unexplored. On graphs, Ollivier-Ricci curvature measures differences between random walks via Wasserstein distances, thus grounding a geometric concept in ideas from probability and optimal transport. We develop ORCHID, a flexible framework generalizing Ollivier-Ricci curvature to hypergraphs, and prove that the resulting curvatures have favorable theoretical properties. Through extensive experiments on synthetic and real-world hypergraphs from different domains, we demonstrate that ORCHID curvatures are both scalable and useful to perform a variety of hypergraph tasks in practice.

We study two classic variants of block-structured integer programming.
Two-stage stochastic programs are integer programs of the form $\{A_i
\mathbf{x} + D_i \mathbf{y}_i = \mathbf{b}_i\textrm{ for all }i=1,\ldots,n\}$,
where $A_i$ and $D_i$ are bounded-size matrices. On the other hand, $n$-fold
programs are integer programs of the form $\{{\sum_{i=1}^n
C_i\mathbf{y}_i=\mathbf{a}} \textrm{ and } D_i\mathbf{y}_i=\mathbf{b}_i\textrm{
for all }i=1,\ldots,n\}$, where again $C_i$ and $D_i$ are bounded-size
matrices. It is known that solving these kind of programs is fixed-parameter
tractable when parameterized by the maximum dimension among the relevant
matrices $A_i,C_i,D_i$ and the maximum absolute value of any entry appearing in
the constraint matrix.
We show that the parameterized tractability results for two-stage stochastic
and $n$-fold programs persist even when one allows large entries in the global
part of the program. More precisely, we prove that:
- The feasibility problem for two-stage stochastic programs is
fixed-parameter tractable when parameterized by the dimensions of matrices
$A_i,D_i$ and by the maximum absolute value of the entries of matrices $D_i$.
That is, we allow matrices $A_i$ to have arbitrarily large entries.
- The linear optimization problem for $n$-fold integer programs that are
uniform -- all matrices $C_i$ are equal -- is fixed-parameter tractable when
parameterized by the dimensions of matrices $C_i$ and $D_i$ and by the maximum
absolute value of the entries of matrices $D_i$. That is, we require that
$C_i=C$ for all $i=1,\ldots,n$, but we allow $C$ to have arbitrarily large
entries.
In the second result, the uniformity assumption is necessary; otherwise the
problem is $\mathsf{NP}$-hard already when the parameters take constant values.
Both our algorithms are weakly polynomial: the running time is measured in the
total bitsize of the input.

Constraint satisfaction problems form a nicely behaved class of problems that
lends itself to complexity classification results. From the point of view of
parameterized complexity, a natural task is to classify the parameterized
complexity of MinCSP problems parameterized by the number of unsatisfied
constraints. In other words, we ask whether we can delete at most $k$
constraints, where $k$ is the parameter, to get a satisfiable instance. In this
work, we take a step towards classifying the parameterized complexity for an
important infinite-domain CSP: Allen's interval algebra (IA). This CSP has
closed intervals with rational endpoints as domain values and employs a set $A$
of 13 basic comparison relations such as ``precedes'' or ``during'' for
relating intervals. IA is a highly influential and well-studied formalism
within AI and qualitative reasoning that has numerous applications in, for
instance, planning, natural language processing and molecular biology. We
provide an FPT vs. W[1]-hard dichotomy for MinCSP$(\Gamma)$ for all $\Gamma
\subseteq A$. IA is sometimes extended with unions of the relations in $A$ or
first-order definable relations over $A$, but extending our results to these
cases would require first solving the parameterized complexity of Directed
Symmetric Multicut, which is a notorious open problem. Already in this limited
setting, we uncover connections to new variants of graph cut and separation
problems. This includes hardness proofs for simultaneous cuts or feedback arc
set problems in directed graphs, as well as new tractable cases with algorithms
based on the recently introduced flow augmentation technique. Given the
intractability of MinCSP$(A)$ in general, we then consider (parameterized)
approximation algorithms and present a factor-$2$ fpt-approximation algorithm.

In a recent work, Esmer et al. describe a simple method - Approximate
Monotone Local Search - to obtain exponential approximation algorithms from
existing parameterized exact algorithms, polynomial-time approximation
algorithms and, more generally, parameterized approximation algorithms. In this
work, we generalize those results to the weighted setting.
More formally, we consider monotone subset minimization problems over a
weighted universe of size $n$ (e.g., Vertex Cover, $d$-Hitting Set and Feedback
Vertex Set). We consider a model where the algorithm is only given access to a
subroutine that finds a solution of weight at most $\alpha \cdot W$ (and of
arbitrary cardinality) in time $c^k \cdot n^{O(1)}$ where $W$ is the minimum
weight of a solution of cardinality at most $k$. In the unweighted setting,
Esmer et al. determine the smallest value $d$ for which a $\beta$-approximation
algorithm running in time $d^n \cdot n^{O(1)}$ can be obtained in this model.
We show that the same dependencies also hold in a weighted setting in this
model: for every fixed $\varepsilon>0$ we obtain a $\beta$-approximation
algorithm running in time $O\left((d+\varepsilon)^{n}\right)$, for the same $d$
as in the unweighted setting.
Similarly, we also extend a $\beta$-approximate brute-force search (in a
model which only provides access to a membership oracle) to the weighted
setting. Using existing approximation algorithms and exact parameterized
algorithms for weighted problems, we obtain the first exponential-time
$\beta$-approximation algorithms that are better than brute force for a variety
of problems including Weighted Vertex Cover, Weighted $d$-Hitting Set, Weighted
Feedback Vertex Set and Weighted Multicut.

The goal of this paper is to understand how exponential-time approximation
algorithms can be obtained from existing polynomial-time approximation
algorithms, existing parameterized exact algorithms, and existing parameterized
approximation algorithms. More formally, we consider a monotone subset
minimization problem over a universe of size $n$ (e.g., Vertex Cover or
Feedback Vertex Set). We have access to an algorithm that finds an
$\alpha$-approximate solution in time $c^k \cdot n^{O(1)}$ if a solution of
size $k$ exists (and more generally, an extension algorithm that can
approximate in a similar way if a set can be extended to a solution with $k$
further elements). Our goal is to obtain a $d^n \cdot n^{O(1)}$ time
$\beta$-approximation algorithm for the problem with $d$ as small as possible.
That is, for every fixed $\alpha,c,\beta \geq 1$, we would like to determine
the smallest possible $d$ that can be achieved in a model where our
problem-specific knowledge is limited to checking the feasibility of a solution
and invoking the $\alpha$-approximate extension algorithm. Our results
completely resolve this question:
(1) For every fixed $\alpha,c,\beta \geq 1$, a simple algorithm
(``approximate monotone local search'') achieves the optimum value of $d$.
(2) Given $\alpha,c,\beta \geq 1$, we can efficiently compute the optimum $d$
up to any precision $\varepsilon > 0$.
Earlier work presented algorithms (but no lower bounds) for the special case
$\alpha = \beta = 1$ [Fomin et al., J. ACM 2019] and for the special case
$\alpha = \beta > 1$ [Esmer et al., ESA 2022]. Our work generalizes these
results and in particular confirms that the earlier algorithms are optimal in
these special cases.

The notion of Las Vegas algorithm was introduced by Babai (1979) and may be
defined in two ways:
* In Babai's original definition, a randomized algorithm is called Las Vegas
if it has finitely bounded running time and certifiable random failure.
* Alternatively, in a widely accepted definition today, Las Vegas algorithms
mean the zero-error randomized algorithms with random running time.
The equivalence between the two definitions is straightforward. In
particular, by repeatedly running the algorithm until no failure encountered,
one can simulate the correct output of a successful running.
We show that this can also be achieved for distributed local computation.
Specifically, we show that in the LOCAL model, any Las Vegas algorithm that
terminates in finite time with locally certifiable failures, can be converted
to a zero-error Las Vegas algorithm, at a polylogarithmic cost in the time
complexity, such that the resulting algorithm perfectly simulates the output of
the original algorithm on the same instance conditioned on that the algorithm
successfully returns without failure.

We introduce a new algorithm and software for solving linear equations in
symmetric diagonally dominant matrices with non-positive off-diagonal entries
(SDDM matrices), including Laplacian matrices. We use pre-conditioned conjugate
gradient (PCG) to solve the system of linear equations. Our preconditioner is a
variant of the Approximate Cholesky factorization of Kyng and Sachdeva (FOCS
2016). Our factorization approach is simple: we eliminate matrix rows/columns
one at a time and update the remaining matrix using sampling to approximate the
outcome of complete Cholesky factorization. Unlike earlier approaches, our
sampling always maintains a connectivity in the remaining non-zero structure.
Our algorithm comes with a tuning parameter that upper bounds the number of
samples made per original entry. We implement our algorithm in Julia, providing
two versions, AC and AC2, that respectively use 1 and 2 samples per original
entry. We compare their single-threaded performance to that of current
state-of-the-art solvers Combinatorial Multigrid (CMG),
BoomerAMG-preconditioned Krylov solvers from HyPre and PETSc, Lean Algebraic
Multigrid (LAMG), and MATLAB's 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 at: github.com/danspielman/Laplacians.jl/ Our
benchmarking data and tutorial are available at:
rjkyng.github.io/SDDM2023/

The problem of designing connectivity oracles supporting vertex failures is
one of the basic data structures problems for undirected graphs. It is already
well understood: previous works [Duan--Pettie STOC'10; Long--Saranurak FOCS'22]
achieve query time linear in the number of failed vertices, and it is
conditionally optimal as long as we require preprocessing time polynomial in
the size of the graph and update time polynomial in the number of failed
vertices.
We revisit this problem in the paradigm of algorithms with predictions: we
ask if the query time can be improved if the set of failed vertices can be
predicted beforehand up to a small number of errors. More specifically, we
design a data structure that, given a graph $G=(V,E)$ and a set of vertices
predicted to fail $\widehat{D} \subseteq V$ of size $d=|\widehat{D}|$,
preprocesses it in time $\tilde{O}(d|E|)$ and then can receive an update given
as the symmetric difference between the predicted and the actual set of failed
vertices $\widehat{D} \triangle D = (\widehat{D} \setminus D) \cup (D \setminus
\widehat{D})$ of size $\eta = |\widehat{D} \triangle D|$, process it in time
$\tilde{O}(\eta^4)$, and after that answer connectivity queries in $G \setminus
D$ in time $O(\eta)$. Viewed from another perspective, our data structure
provides an improvement over the state of the art for the \emph{fully dynamic
subgraph connectivity problem} in the \emph{sensitivity setting}
[Henzinger--Neumann ESA'16].
We argue that the preprocessing time and query time of our data structure are
conditionally optimal under standard fine-grained complexity assumptions.

In this work, we initiate the complexity study of Biclique Contraction and
Balanced Biclique Contraction. In these problems, given as input a graph G and
an integer k, the objective is to determine whether one can contract at most k
edges in G to obtain a biclique and a balanced biclique, respectively. We first
prove that these problems are NP-complete even when the input graph is
bipartite. Next, we study the parameterized complexity of these problems and
show that they admit single exponential-time FPT algorithms when parameterized
by the number k of edge contractions. Then, we show that Balanced Biclique
Contraction admits a quadratic vertex kernel while Biclique Contraction does
not admit any polynomial compression (or kernel) under standard
complexity-theoretic assumptions.

We study dynamic algorithms in the model of algorithms with predictions. We
assume the algorithm is given imperfect predictions regarding future updates,
and we ask how such predictions can be used to improve the running time. This
can be seen as a model interpolating between classic online and offline dynamic
algorithms. Our results give smooth tradeoffs between these two extreme
settings.
First, we give algorithms for incremental and decremental transitive closure
and approximate APSP that take as an additional input a predicted sequence of
updates (edge insertions, or edge deletions, respectively). They preprocess it
in $\tilde{O}(n^{(3+\omega)/2})$ time, and then handle updates in
$\tilde{O}(1)$ worst-case time and queries in $\tilde{O}(\eta^2)$ worst-case
time. Here $\eta$ is an error measure that can be bounded by the maximum
difference between the predicted and actual insertion (deletion) time of an
edge, i.e., by the $\ell_\infty$-error of the predictions.
The second group of results concerns fully dynamic problems with vertex
updates, where the algorithm has access to a predicted sequence of the next $n$
updates. We show how to solve fully dynamic triangle detection, maximum
matching, single-source reachability, and more, in $O(n^{\omega-1}+n\eta_i)$
worst-case update time. Here $\eta_i$ denotes how much earlier the $i$-th
update occurs than predicted.
Our last result is a reduction that transforms a worst-case incremental
algorithm without predictions into a fully dynamic algorithm which is given a
predicted deletion time for each element at the time of its insertion. As a
consequence we can, e.g., maintain fully dynamic exact APSP with such
predictions in $\tilde{O}(n^2)$ worst-case vertex insertion time and
$\tilde{O}(n^2 (1+\eta_i))$ worst-case vertex deletion time (for the prediction
error $\eta_i$ defined as above).

Dot-product attention mechanism plays a crucial role in modern deep
architectures (e.g., Transformer) for sequence modeling, however, na\"ive exact
computation of this model incurs quadratic time and memory complexities in
sequence length, hindering the training of long-sequence models. Critical
bottlenecks are due to the computation of partition functions in the
denominator of softmax function as well as the multiplication of the softmax
matrix with the matrix of values. Our key observation is that the former can be
reduced to a variant of the kernel density estimation (KDE) problem, and an
efficient KDE solver can be further utilized to accelerate the latter via
subsampling-based fast matrix products. Our proposed KDEformer can approximate
the attention in sub-quadratic time with provable spectral norm bounds, while
all prior results merely provide entry-wise error bounds. Empirically, we
verify that KDEformer outperforms other attention approximations in terms of
accuracy, memory, and runtime on various pre-trained models. On BigGAN image
generation, we achieve better generative scores than the exact computation with
over $4\times$ speedup. For ImageNet classification with T2T-ViT, KDEformer
shows over $18\times$ speedup while the accuracy drop is less than $0.5\%$.