Publications - Current Year

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 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/

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\%$.