Publications - Current Year

We consider the problem of selecting a committee of $k$ alternatives among
$m$ alternatives, based on the ordinal rank list of voters. Our focus is on the
case where both voters and alternatives lie on a metric space-specifically, on
the line-and the objective is to minimize the additive social cost. The
additive social cost is the sum of the costs for all voters, where the cost for
each voter is defined as the sum of their distances to each member of the
selected committee.
We propose a new voting rule, the Polar Comparison Rule, which achieves upper
bounds of $1 + \sqrt{2} \approx 2.41$ and $7/3 \approx 2.33$ distortions for $k
= 2$ and $k = 3$, respectively, and we show that these bounds are tight.
Furthermore, we generalize this rule, showing that it maintains a distortion of
roughly $7/3$ based on the remainder of the committee size when divided by
three. We also establish lower bounds on the achievable distortion based on the
parity of $k$ and for both small and large committee sizes.

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 consider the problem of selecting a committee of $k$ alternatives among
$m$ alternatives, based on the ordinal rank list of voters. Our focus is on the
case where both voters and alternatives lie on a metric space-specifically, on
the line-and the objective is to minimize the additive social cost. The
additive social cost is the sum of the costs for all voters, where the cost for
each voter is defined as the sum of their distances to each member of the
selected committee.
We propose a new voting rule, the Polar Comparison Rule, which achieves upper
bounds of $1 + \sqrt{2} \approx 2.41$ and $7/3 \approx 2.33$ distortions for $k
= 2$ and $k = 3$, respectively, and we show that these bounds are tight.
Furthermore, we generalize this rule, showing that it maintains a distortion of
roughly $7/3$ based on the remainder of the committee size when divided by
three. We also establish lower bounds on the achievable distortion based on the
parity of $k$ and for both small and large committee sizes.

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.

Low Diameter Decompositions (LDDs) are invaluable tools in the design of
combinatorial graph algorithms. While historically they have been applied
mainly to undirected graphs, in the recent breakthrough for the negative-length
Single Source Shortest Path problem, Bernstein, Nanongkai, and Wulff-Nilsen
[FOCS '22] extended the use of LDDs to directed graphs for the first time.
Specifically, their LDD deletes each edge with probability at most
$O(\frac{1}{D} \cdot \log^2 n)$, while ensuring that each strongly connected
component in the remaining graph has a (weak) diameter of at most $D$.
In this work, we make further advancements in the study of directed LDDs. We
reveal a natural and intuitive (in hindsight) connection to Expander
Decompositions, and leveraging this connection along with additional
techniques, we establish the existence of an LDD with an edge-cutting
probability of $O(\frac{1}{D} \cdot \log n \log\log n)$. This improves the
previous bound by nearly a logarithmic factor and closely approaches the lower
bound of $\Omega(\frac{1}{D} \cdot \log n)$. With significantly more technical
effort, we also develop two efficient algorithms for computing our LDDs: a
deterministic algorithm that runs in time $\tilde O(m \cdot poly(D))$ and a
randomized algorithm that runs in near-linear time $\tilde O(m)$.
We believe that our work provides a solid conceptual and technical foundation
for future research relying on directed LDDs, which will undoubtedly follow
soon.

Computing shortest paths is one of the most fundamental algorithmic graph
problems. It is known since decades that this problem can be solved in
near-linear time if all weights are nonnegative. A recent break-through by
[Bernstein, Nanongkai, Wulff-Nilsen '22] presented a randomized near-linear
time algorithm for this problem. A subsequent improvement in [Bringmann,
Cassis, Fischer '23] significantly reduced the number of logarithmic factors
and thereby also simplified the algorithm. It is surprising and exciting that
both of these algorithms are combinatorial and do not contain any fundamental
obstacles for being practical.
We launch the, to the best of our knowledge, first extensive investigation
towards a practical implementation of [Bringmann, Cassis, Fischer '23]. To this
end, we give an accessible overview of the algorithm, discussing what adaptions
are necessary to obtain a fast algorithm in practice. We manifest these
adaptions in an efficient implementation. We test our implementation on a
benchmark data set that is adapted to be more difficult for our implementation
in order to allow for a fair comparison. As in [Bringmann, Cassis, Fischer '23]
as well as in our implementation there are multiple parameters to tune, we
empirically evaluate their effect and thereby determine the best choices. Our
implementation is then extensively compared to one of the state-of-the-art
algorithms for this problem [Goldberg, Radzik '93]. On the hardest instance
type, we are faster by up to almost two orders of magnitude.

We study polynomial-time approximation algorithms for two closely-related
problems, namely computing shortcuts and transitive-closure spanners (TC
spanner). For a directed unweighted graph $G=(V, E)$ and an integer $d$, a set
of edges $E'\subseteq V\times V$ is called a $d$-TC spanner of $G$ if the graph
$H:=(V, E')$ has (i) the same transitive-closure as $G$ and (ii) diameter at
most $d.$ The set $E''\subseteq V\times V$ is a $d$-shortcut of $G$ if $E\cup
E''$ is a $d$-TC spanner of $G$. Our focus is on the following $(\alpha_D,
\alpha_S)$-approximation algorithm: given a directed graph $G$ and integers $d$
and $s$ such that $G$ admits a $d$-shortcut (respectively $d$-TC spanner) of
size $s$, find a $(d\alpha_D)$-shortcut (resp. $(d\alpha_D)$-TC spanner) with
$s\alpha_S$ edges, for as small $\alpha_S$ and $\alpha_D$ as possible.
As our main result, we show that, under the Projection Game Conjecture (PGC),
there exists a small constant $\epsilon>0$, such that no polynomial-time
$(n^{\epsilon},n^{\epsilon})$-approximation algorithm exists for finding
$d$-shortcuts as well as $d$-TC spanners of size $s$. Previously,
super-constant lower bounds were known only for $d$-TC spanners with constant
$d$ and ${\alpha_D}=1$ [Bhattacharyya, Grigorescu, Jung, Raskhodnikova,
Woodruff 2009]. Similar lower bounds for super-constant $d$ were previously
known only for a more general case of directed spanners [Elkin, Peleg 2000]. No
hardness of approximation result was known for shortcuts prior to our result.
As a side contribution, we complement the above with an upper bound of the
form $(n^{\gamma_D}, n^{\gamma_S})$-approximation which holds for $3\gamma_D +
2\gamma_S > 1$ (e.g., $(n^{1/5+o(1)}, n^{1/5+o(1)})$-approximation).

Benchmark datasets have proved pivotal to the success of graph learning, and
good benchmark datasets are crucial to guide the development of the field.
Recent research has highlighted problems with graph-learning datasets and
benchmarking practices -- revealing, for example, that methods which ignore the
graph structure can outperform graph-based approaches on popular benchmark
datasets. Such findings raise two questions: (1) What makes a good
graph-learning dataset, and (2) how can we evaluate dataset quality in graph
learning? Our work addresses these questions. As the classic evaluation setup
uses datasets to evaluate models, it does not apply to dataset evaluation.
Hence, we start from first principles. Observing that graph-learning datasets
uniquely combine two modes -- the graph structure and the node features -- , we
introduce RINGS, a flexible and extensible mode-perturbation framework to
assess the quality of graph-learning datasets based on dataset ablations --
i.e., by quantifying differences between the original dataset and its perturbed
representations. Within this framework, we propose two measures -- performance
separability and mode complementarity -- as evaluation tools, each assessing,
from a distinct angle, the capacity of a graph dataset to benchmark the power
and efficacy of graph-learning methods. We demonstrate the utility of our
framework for graph-learning dataset evaluation in an extensive set of
experiments and derive actionable recommendations for improving the evaluation
of graph-learning methods. Our work opens new research directions in
data-centric graph learning, and it constitutes a first step toward the
systematic evaluation of evaluations.

Two fundamental classes of finite automata are deterministic and
nondeterministic ones (DFAs and NFAs). Natural intermediate classes arise from
bounds on an NFA's allowed ambiguity, i.e. number of accepting runs per word:
unambiguous, finitely ambiguous, and polynomially ambiguous finite automata. It
is known that deciding whether a given NFA is unambiguous and whether it is
polynomially ambiguous is possible in quadratic time, and deciding finite
ambiguity is possible in cubic time. We provide matching lower bounds showing
these running times to be optimal, assuming popular fine-grained complexity
hypotheses.
We improve the upper bounds for unary automata, which are essentially
directed graphs with a source and a target. In this view, unambiguity asks
whether all walks from the source to the target have different lengths. The
running time analysis of our algorithm reduces to bounding the entry-wise
1-norm of a GCD matrix, yielding a near-linear upper bound. For finite and
polynomial ambiguity, we provide simple linear-time algorithms in the unary
case.
Finally, we study the twins property for weighted automata over the tropical
semiring, which characterises the determinisability of unambiguous weighted
automata. It occurs naturally in our context as deciding the twins property is
an intermediate step in determinisability algorithms for weighted automata with
bounded ambiguity. We show that Allauzen and Mohri's quadratic-time algorithm
checking the twins property is optimal up to the same fine-grained hypotheses
as for unambiguity. For unary automata, we show that the problem can be
rephrased to whether all cycles in a weighted directed graph have the same
average weight and give a linear-time algorithm.

We investigate structural properties of the binary rank of Kronecker powers
of binary matrices, equivalently, the biclique partition numbers of the
corresponding bipartite graphs. To this end, we engineer a Column Generation
approach to solve linear optimization problems for the fractional biclique
partition number of bipartite graphs, specifically examining the Domino graph
and its Kronecker powers. We address the challenges posed by the double
exponential growth of the number of bicliques in increasing Kronecker powers.
We discuss various strategies to generate suitable initial sets of bicliques,
including an inductive method for increasing Kronecker powers. We show how to
manage the number of active bicliques to improve running time and to stay
within memory limits. Our computational results reveal that the fractional
binary rank is not multiplicative with respect to the Kronecker product. Hence,
there are binary matrices, and bipartite graphs, respectively, such as the
Domino, where the asymptotic fractional binary rank is strictly smaller than
the fractional binary rank. While we used our algorithm to reduce the upper
bound, we formally prove that the fractional biclique cover number is a lower
bound, which is at least as good as the widely used isolating (or fooling set)
bound. For the Domino, we obtain that the asymptotic fractional binary rank
lies in the interval $[2,2.373]$. Since our computational resources are not
sufficient to further reduce the upper bound, we encourage further exploration
using more substantial computing resources or further mathematical engineering
techniques to narrow the gap and advance our understanding of biclique
partitions, particularly, to settle the open question whether binary rank and
biclique partition number are multiplicative with respect to the Kronecker
product.