Publications - Last Year

The Unbounded Subset Sum (USS) problem is an NP-hard computational problem
where the goal is to decide whether there exist non-negative integers $x_1,
\ldots, x_n$ such that $x_1 a_1 + \ldots + x_n a_n = b$, where $a_1 < \cdots <
a_n < b$ are distinct positive integers with $\text{gcd}(a_1, \ldots, a_n)$
dividing $b$. The problem can be solved in pseudopolynomial time, while
specialized cases, such as when $b$ exceeds the Frobenius number of $a_1,
\ldots, a_n$ simplify to a total problem where a solution always exists.
This paper explores the concept of totality in USS. The challenge in this
setting is to actually find a solution, even though we know its existence is
guaranteed. We focus on the instances of USS where solutions are guaranteed for
large $b$. We show that when $b$ is slightly greater than the Frobenius number,
we can find the solution to USS in polynomial time.
We then show how our results extend to Integer Programming with Equalities
(ILPE), highlighting conditions under which ILPE becomes total. We investigate
the diagonal Frobenius number, which is the appropriate generalization of the
Frobenius number to this context. In this setting, we give a polynomial-time
algorithm to find a solution of ILPE. The bound obtained from our algorithmic
procedure for finding a solution almost matches the recent existential bound of
Bach, Eisenbrand, Rothvoss, and Weismantel (2024).

We study the problem of allocating a set of indivisible goods among a set of
agents with \emph{2-value additive valuations}. In this setting, each good is
valued either $1$ or $\sfrac{p}{q}$, for some fixed co-prime numbers $p,q\in
\NN$ such that $1\leq q < p$. Our goal is to find an allocation maximizing the
\emph{Nash social welfare} (\NSW), i.e., the geometric mean of the valuations
of the agents. In this work, we give a complete characterization of
polynomial-time tractability of \NSW\ maximization that solely depends on the
values of $q$.
We start by providing a rather simple polynomial-time algorithm to find a
maximum \NSW\ allocation when the valuation functions are \emph{integral}, that
is, $q=1$. We then exploit more involved techniques to get an algorithm
producing a maximum \NSW\ allocation for the \emph{half-integral} case, that
is, $q=2$. Finally, we show it is \classNP-hard to compute an allocation with
maximum \NSW\ whenever $q\geq3$.

We prove a robust contraction decomposition theorem for $H$-minor-free
graphs, which states that given an $H$-minor-free graph $G$ and an integer $p$,
one can partition in polynomial time the vertices of $G$ into $p$ sets
$Z_1,\dots,Z_p$ such that $\operatorname{tw}(G/(Z_i \setminus Z')) = O(p +
|Z'|)$ for all $i \in [p]$ and $Z' \subseteq Z_i$. Here,
$\operatorname{tw}(\cdot)$ denotes the treewidth of a graph and $G/(Z_i
\setminus Z')$ denotes the graph obtained from $G$ by contracting all edges
with both endpoints in $Z_i \setminus Z'$.
Our result generalizes earlier results by Klein [SICOMP 2008] and Demaine et
al. [STOC 2011] based on partitioning $E(G)$, and some recent theorems for
planar graphs by Marx et al. [SODA 2022], for bounded-genus graphs (more
generally, almost-embeddable graphs) by Bandyapadhyay et al. [SODA 2022], and
for unit-disk graphs by Bandyapadhyay et al. [SoCG 2022].
The robust contraction decomposition theorem directly results in
parameterized algorithms with running time $2^{\widetilde{O}(\sqrt{k})} \cdot
n^{O(1)}$ or $n^{O(\sqrt{k})}$ for every vertex/edge deletion problems on
$H$-minor-free graphs that can be formulated as Permutation CSP Deletion or
2-Conn Permutation CSP Deletion. Consequently, we obtain the first
subexponential-time parameterized algorithms for Subset Feedback Vertex Set,
Subset Odd Cycle Transversal, Subset Group Feedback Vertex Set, 2-Conn
Component Order Connectivity on $H$-minor-free graphs. For other problems which
already have subexponential-time parameterized algorithms on $H$-minor-free
graphs (e.g., Odd Cycle Transversal, Vertex Multiway Cut, Vertex Multicut,
etc.), our theorem gives much simpler algorithms of the same running time.

Co-lex partial orders were recently introduced in (Cotumaccio et al., SODA
2021 and JACM 2023) as a powerful tool to index finite state automata, with
applications to regular expression matching. They generalize Wheeler orders
(Gagie et al., Theoretical Computer Science 2017) and naturally reflect the
co-lexicographic order of the strings labeling source-to-node paths in the
automaton. Briefly, the co-lex width $p$ of a finite-state automaton measures
how sortable its states are with respect to the co-lex order among the strings
they accept. Automata of co-lex width $p$ can be compressed to $O(\log p)$ bits
per edge and admit regular expression matching algorithms running in time
proportional to $p^2$ per matched character.
The deterministic co-lex width of a regular language $\mathcal L$ is the
smallest width of such a co-lex order, among all DFAs recognizing $\mathcal L$.
Since languages of small co-lex width admit efficient solutions to automata
compression and pattern matching, computing the co-lex width of a language is
relevant in these applications. The paper introducing co-lex orders determined
that the deterministic co-lex width $p$ of a language $\mathcal L$ can be
computed in time proportional to $m^{O(p)}$, given as input any DFA $\mathcal
A$ for $\mathcal L$, of size (number of transitions) $m =|\mathcal A|$.
In this paper, using new techniques, we show that it is possible to decide in
$O(m^p)$ time if the deterministic co-lex width of the language recognized by a
given minimum DFA is strictly smaller than some integer $p\ge 2$. We complement
this upper bound with a matching conditional lower bound based on the Strong
Exponential Time Hypothesis. The problem is known to be PSPACE-complete when
the input is an NFA (D'Agostino et al., Theoretical Computer Science 2023);
thus, together with that result, our paper essentially settles the complexity
of the problem.

Union volume estimation is a classical algorithmic problem. Given a family of
objects $O_1,\ldots,O_n \subseteq \mathbb{R}^d$, we want to approximate the
volume of their union. In the special case where all objects are boxes (also
known as hyperrectangles) this is known as Klee's measure problem. The
state-of-the-art algorithm [Karp, Luby, Madras '89] for union volume estimation
and Klee's measure problem in constant dimension $d$ computes a
$(1+\varepsilon)$-approximation with constant success probability by using a
total of $O(n/\varepsilon^2)$ queries of the form (i) ask for the volume of
$O_i$, (ii) sample a point uniformly at random from $O_i$, and (iii) query
whether a given point is contained in $O_i$.
We show that if one can only interact with the objects via the aforementioned
three queries, the query complexity of [Karp, Luby, Madras '89] is indeed
optimal, i.e., $\Omega(n/\varepsilon^2)$ queries are necessary. Our lower bound
already holds for estimating the union of equiponderous axis-aligned polygons
in $\mathbb{R}^2$, and even if the algorithm is allowed to inspect the
coordinates of the points sampled from the polygons, and still holds when a
containment query can ask containment of an arbitrary (not sampled) point.
Guided by the insights of the lower bound, we provide a more efficient
approximation algorithm for Klee's measure problem improving the
$O(n/\varepsilon^2)$ time to $O((n+\frac{1}{\varepsilon^2}) \cdot
\log^{O(d)}n)$. We achieve this improvement by exploiting the geometry of
Klee's measure problem in various ways: (1) Since we have access to the boxes'
coordinates, we can split the boxes into classes of boxes of similar shape. (2)
Within each class, we show how to sample from the union of all boxes, by using
orthogonal range searching. And (3) we exploit that boxes of different classes
have small intersection, for most pairs of classes.

Constrained Forest Problems (CFPs) as introduced by Goemans and Williamson in
1995 capture a wide range of network design problems with edge subsets as
solutions, such as Minimum Spanning Tree, Steiner Forest, and Point-to-Point
Connection. While individual CFPs have been studied extensively in individual
computational models, a unified approach to solving general CFPs in multiple
computational models has been lacking. Against this background, we present the
shell-decomposition algorithm, a model-agnostic meta-algorithm that efficiently
computes a $(2+\epsilon)$-approximation to CFPs for a broad class of forest
functions. To demonstrate the power and flexibility of this result, we
instantiate our algorithm for 3 fundamental, NP-hard CFPs in 3 different
computational models. For example, for constant $\epsilon$, we obtain the
following $(2+\epsilon)$-approximations in the Congest model:
1. For Steiner Forest specified via input components, where each node knows
the identifier of one of $k$ disjoint subsets of $V$, we achieve a
deterministic $(2+\epsilon)$-approximation in $O(\sqrt{n}+D+k)$ rounds, where
$D$ is the hop diameter of the graph.
2. For Steiner Forest specified via symmetric connection requests, where
connection requests are issued to pairs of nodes, we leverage randomized
equality testing to reduce the running time to $O(\sqrt{n}+D)$, succeeding with
high probability.
3. For Point-to-Point Connection, we provide a $(2+\epsilon)$-approximation
in $O(\sqrt{n}+D)$ rounds.
4. For Facility Placement and Connection, a relative of non-metric Facility
Location, we obtain a $(2+\epsilon)$-approximation in $O(\sqrt{n}+D)$ rounds.
We further show how to replace the $\sqrt{n}+D$ term by the complexity of
solving Partwise Aggregation, achieving (near-)universal optimality in any
setting in which a solution to Partwise Aggregation in near-shortcut-quality
time is known.

The task of min-plus matrix multiplication often arises in the context of
distances in graphs and is known to be fine-grained equivalent to the All-Pairs
Shortest Path problem. The non-crossing property of shortest paths in planar
graphs gives rise to Monge matrices; the min-plus product of $n\times n$ Monge
matrices can be computed in $O(n^2)$ time. Grid graphs arising in sequence
alignment problems, such as longest common subsequence or longest increasing
subsequence, are even more structured. Tiskin [SODA'10] modeled their behavior
using simple unit-Monge matrices and showed that the min-plus product of such
matrices can be computed in $O(n\log n)$ time. Russo [SPIRE'11] showed that the
min-plus product of arbitrary Monge matrices can be computed in time
$O((n+\delta)\log^3 n)$ parameterized by the core size $\delta$, which is
$O(n)$ for unit-Monge matrices.
In this work, we provide a linear bound on the core size of the product
matrix in terms of the core sizes of the input matrices and show how to solve
the core-sparse Monge matrix multiplication problem in $O((n+\delta)\log n)$
time, matching the result of Tiskin for simple unit-Monge matrices. Our
algorithm also allows $O(\log \delta)$-time witness recovery for any given
entry of the output matrix. As an application of this functionality, we show
that an array of size $n$ can be preprocessed in $O(n\log^3 n)$ time so that
the longest increasing subsequence of any sub-array can be reconstructed in
$O(l)$ time, where $l$ is the length of the reported subsequence; in
comparison, Karthik C. S. and Rahul [arXiv'24] recently achieved
$O(l+n^{1/2}\log^3 n)$-time reporting after $O(n^{3/2}\log^3 n)$-time
preprocessing. Our faster core-sparse Monge matrix multiplication also enabled
reducing two logarithmic factors in the running times of the recent algorithms
for edit distance with integer weights [Gorbachev & Kociumaka, arXiv'24].

The edit distance of two strings is the minimum number of insertions,
deletions, and substitutions needed to transform one string into the other. The
textbook algorithm determines the edit distance of length-$n$ strings in
$O(n^2)$ time, which is optimal up to subpolynomial factors under Orthogonal
Vectors Hypothesis. In the bounded version of the problem, parameterized by the
edit distance $k$, the algorithm of Landau and Vishkin [JCSS'88] achieves
$O(n+k^2)$ time, which is optimal as a function of $n$ and $k$.
The dynamic version of the problem asks to maintain the edit distance of two
strings that change dynamically, with each update modeled as an edit. A
folklore approach supports updates in $\tilde O(k^2)$ time, where $\tilde
O(\cdot)$ hides polylogarithmic factors. Recently, Charalampopoulos, Kociumaka,
and Mozes [CPM'20] showed an algorithm with update time $\tilde O(n)$, which is
optimal under OVH in terms of $n$. The update time of $\tilde O(\min\{n,k^2\})$
raised an exciting open question of whether $\tilde O(k)$ is possible; we
answer it affirmatively.
Our solution relies on tools originating from weighted edit distance, where
the weight of each edit depends on the edit type and the characters involved.
The textbook algorithm supports weights, but the Landau-Vishkin approach does
not, and a simple $O(nk)$-time procedure long remained the fastest for bounded
weighted edit distance. Only recently, Das et al. [STOC'23] provided an
$O(n+k^5)$-time algorithm, whereas Cassis, Kociumaka, and Wellnitz [FOCS'23]
presented an $\tilde O(n+\sqrt{nk^3})$-time solution and a matching conditional
lower bound. In this paper, we show that, for integer edit weights between $0$
and $W$, weighted edit distance can be computed in $\tilde O(n+Wk^2)$ time and
maintained dynamically in $\tilde O(W^2k)$ time per update. Our static
algorithm can also be implemented in $\tilde O(n+k^{2.5})$ time.

Lagarias and Odlyzko (J.~ACM~1985) proposed a polynomial time algorithm for
solving ``\emph{almost all}'' instances of the Subset Sum problem with $n$
integers of size $\Omega(\Gamma_{\text{LO}})$, where
$\log_2(\Gamma_{\text{LO}}) > n^2 \log_2(\gamma)$ and $\gamma$ is a parameter
of the lattice basis reduction ($\gamma > \sqrt{4/3}$ for LLL). The algorithm
of Lagarias and Odlyzko is a cornerstone result in cryptography. However, the
theoretical guarantee on the density of feasible instances has remained
unimproved for almost 40 years.
In this paper, we propose an algorithm to solve ``almost all'' instances of
Subset Sum with integers of size $\Omega(\sqrt{\Gamma_{\text{LO}}})$ after a
single call to the lattice reduction. Additionally, our argument allows us to
solve the Subset Sum problem for multiple targets while the previous approach
could only answer one target per call to lattice basis reduction. We introduce
a modular arithmetic approach to the Subset Sum problem. The idea is to use the
lattice reduction to solve a linear system modulo a suitably large prime. We
show that density guarantees can be improved, by analysing the lengths of the
LLL reduced basis vectors, of both the primal and the dual lattices
simultaneously.

Integer linear programs $\min\{c^T x : A x = b, x \in \mathbb{Z}^n_{\ge
0}\}$, where $A \in \mathbb{Z}^{m \times n}$, $b \in \mathbb{Z}^m$, and $c \in
\mathbb{Z}^n$, can be solved in pseudopolynomial time for any fixed number of
constraints $m = O(1)$. More precisely, in time $(m\Delta)^{O(m)}
\text{poly}(I)$, where $\Delta$ is the maximum absolute value of an entry in
$A$ and $I$ the input size.
Known algorithms rely heavily on dynamic programming, which leads to a space
complexity of similar order of magnitude as the running time. In this paper, we
present a polynomial space algorithm that solves integer linear programs in
$(m\Delta)^{O(m (\log m + \log\log\Delta))} \text{poly}(I)$ time, that is, in
almost the same time as previous dynamic programming algorithms.