Publications - Last Year

We study the fundamental problem of fairly allocating a set of indivisible
goods among $n$ agents with additive valuations using the desirable fairness
notion of maximin share (MMS). MMS is the most popular share-based notion, in
which an agent finds an allocation fair to her if she receives goods worth at
least her MMS value. An allocation is called MMS if all agents receive at least
their MMS value. Since MMS allocations need not exist when $n>2$, a series of
works showed the existence of approximate MMS allocations with the current best
factor of $\frac34 + O(\frac{1}{n})$. However, a simple example in [DFL82,
BEF21, AGST23] showed the limitations of existing approaches and proved that
they cannot improve this factor to $3/4 + \Omega(1)$. In this paper, we bypass
these barriers to show the existence of $(\frac{3}{4} + \frac{3}{3836})$-MMS
allocations by developing new reduction rules and analysis techniques.

We consider fair division of a set of indivisible goods among $n$ agents with
additive valuations using the fairness notion of maximin share (MMS). MMS is
the most popular share-based notion, in which an agent finds an allocation fair
to her if she receives goods worth at least her ($1$-out-of-$n$) MMS value. An
allocation is called MMS if all agents receive their MMS values. However, since
MMS allocations do not always exist, the focus shifted to investigating its
ordinal and multiplicative approximations.
In the ordinal approximation, the goal is to show the existence of
$1$-out-of-$d$ MMS allocations (for the smallest possible $d>n$). A series of
works led to the state-of-the-art factor of $d=\lfloor3n/2\rfloor$ [Hosseini et
al.'21]. We show that $1$-out-of-$4\lceil n/3\rceil$ MMS allocations always
exist, thereby improving the state-of-the-art of ordinal approximation.
In the multiplicative approximation, the goal is to show the existence of
$\alpha$-MMS allocations (for the largest possible $\alpha < 1$), which
guarantees each agent at least $\alpha$ times her MMS value. We introduce a
general framework of "approximate MMS with agent priority ranking". An
allocation is said to be $T$-MMS, for a non-increasing sequence $T = (\tau_1,
\ldots, \tau_n)$ of numbers, if the agent at rank $i$ in the order gets a
bundle of value at least $\tau_i$ times her MMS value. This framework captures
both ordinal approximation and multiplicative approximation as special cases.
We show the existence of $T$-MMS allocations where $\tau_i \ge \max(\frac{3}{4}
+ \frac{1}{12n}, \frac{2n}{2n+i-1})$ for all $i$. Furthermore, we can get
allocations that are $(\frac{3}{4} + \frac{1}{12n})$-MMS ex-post and $(0.8253 +
\frac{1}{36n})$-MMS ex-ante. We also prove that our algorithm does not give
better than $(0.8631 + \frac{1}{2n})$-MMS ex-ante.

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 the parameterized complexity of #IndSub($\Phi$), where given a graph
$G$ and an integer $k$, the task is to count the number of induced subgraphs on
$k$ vertices that satisfy the graph property $\Phi$. Focke and Roth [STOC 2022]
completely characterized the complexity for each $\Phi$ that is a hereditary
property (that is, closed under vertex deletions): #IndSub($\Phi$) is
#W[1]-hard except in the degenerate cases when every graph satisfies $\Phi$ or
only finitely many graphs satisfy $\Phi$. We complement this result with a
classification for each $\Phi$ that is edge monotone (that is, closed under
edge deletions): #IndSub($\Phi$) is #W[1]-hard except in the degenerate case
when there are only finitely many integers $k$ such that $\Phi$ is nontrivial
on $k$-vertex graphs. Our result generalizes earlier results for specific
properties $\Phi$ that are related to the connectivity or density of the graph.
Further, we extend the #W[1]-hardness result by a lower bound which shows
that #IndSub($\Phi$) cannot be solved in time $f(k) \cdot |V(G)|^{o(\sqrt{\log
k/\log\log k})}$ for any function $f$, unless the Exponential-Time Hypothesis
(ETH) fails. For many natural properties, we obtain even a tight bound $f(k)
\cdot |V(G)|^{o(k)}$; for example, this is the case for every property $\Phi$
that is nontrivial on $k$-vertex graphs for each $k$ greater than some $k_0$.

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/

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