Publications

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.

We consider the well-studied Robust $(k, z)$-Clustering problem, which
generalizes the classic $k$-Median, $k$-Means, and $k$-Center problems. Given a
constant $z\ge 1$, the input to Robust $(k, z)$-Clustering is a set $P$ of $n$
weighted points in a metric space $(M,\delta)$ and a positive integer $k$.
Further, each point belongs to one (or more) of the $m$ many different groups
$S_1,S_2,\ldots,S_m$. Our goal is to find a set $X$ of $k$ centers such that
$\max_{i \in [m]} \sum_{p \in S_i} w(p) \delta(p,X)^z$ is minimized.
This problem arises in the domains of robust optimization [Anthony, Goyal,
Gupta, Nagarajan, Math. Oper. Res. 2010] and in algorithmic fairness. For
polynomial time computation, an approximation factor of $O(\log m/\log\log m)$
is known [Makarychev, Vakilian, COLT $2021$], which is tight under a plausible
complexity assumption even in the line metrics. For FPT time, there is a
$(3^z+\epsilon)$-approximation algorithm, which is tight under GAP-ETH [Goyal,
Jaiswal, Inf. Proc. Letters, 2023].
Motivated by the tight lower bounds for general discrete metrics, we focus on
\emph{geometric} spaces such as the (discrete) high-dimensional Euclidean
setting and metrics of low doubling dimension, which play an important role in
data analysis applications. First, for a universal constant $\eta_0 >0.0006$,
we devise a $3^z(1-\eta_{0})$-factor FPT approximation algorithm for discrete
high-dimensional Euclidean spaces thereby bypassing the lower bound for general
metrics. We complement this result by showing that even the special case of
$k$-Center in dimension $\Theta(\log n)$ is $(\sqrt{3/2}- o(1))$-hard to
approximate for FPT algorithms. Finally, we complete the FPT approximation
landscape by designing an FPT $(1+\epsilon)$-approximation scheme (EPAS) for
the metric of sub-logarithmic doubling dimension.

We explore the fair distribution of a set of $m$ indivisible chores among $n$
agents, where each agent's costs are evaluated using a monotone cost function.
Our focus lies on two fairness criteria: envy-freeness up to any item (EFX) and
a relaxed notion, namely envy-freeness up to the transfer of any item (tEFX).
We demonstrate that a 2-approximate EFX allocation exists and is computable in
polynomial time for three agents with subadditive cost functions, improving
upon the previous $(2 + \sqrt{6})$ approximation for additive cost functions.
This result requires extensive case analysis. Christoforidis et al. (IJCAI'24)
independently claim the same approximation for additive cost functions;
however, we provide a counter-example to their algorithm. We expand the number
of agents to any number to get the same approximation guarantee with the
assumption of partially identical ordering (IDO) for the cost functions.
Additionally, we establish that a tEFX allocation is achievable for three
agents if one has an additive 2-ratio bounded cost function, while the others
may have general monotone cost functions. This is an improvement from the prior
requirement of two agents with additive 2-ratio bounded cost functions. This
allocation can also be extended to agent groups with identical valuations.
Further, we show various analyses of EFX allocations for chores, such as the
relaxations for additive $\alpha$-ratio-bounded cost functions.

We study the problem of fairly allocating indivisible goods to a set of
agents with additive leveled valuations. A valuation function is called leveled
if and only if bundles of larger size have larger value than bundles of smaller
size. The economics literature has well studied such valuations.
We use the maximin-share (MMS) and EFX as standard notions of fairness. We
show that an algorithm introduced by Christodoulou et al. ([11]) constructs an
allocation that is EFX and $\frac{\lfloor \frac{m}{n} \rfloor}{\lfloor
\frac{m}{n} \rfloor + 1}\text{-MMS}$. In the paper, it was claimed that the
allocation is EFX and $\frac{2}{3}\text{-MMS}$. However, the proof of the
MMS-bound is incorrect. We give a counter-example to their proof and then prove
a stronger approximation of MMS.

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).

The immense success of ML systems relies heavily on large-scale, high-quality
data. The high demand for data has led to many paradigms that involve selling,
exchanging, and sharing data, motivating the study of economic processes with
data as an asset. However, data differs from classical economic assets in terms
of free duplication: there is no concept of limited supply since it can be
replicated at zero marginal cost. This distinction introduces fundamental
differences between economic processes involving data and those concerning
other assets.
We study a parallel to exchange (Arrow-Debreu) markets where data is the
asset. Here, agents with datasets exchange data fairly and voluntarily, aiming
for mutual benefit without monetary compensation. This framework is
particularly relevant for non-profit organizations that seek to improve their
ML models through data exchange, yet are restricted from selling their data for
profit.
We propose a general framework for data exchange, built on two core
principles: (i) fairness, ensuring that each agent receives utility
proportional to their contribution to others; contributions are quantifiable
using standard credit-sharing functions like the Shapley value, and (ii)
stability, ensuring that no coalition of agents can identify an exchange among
themselves which they unanimously prefer to the current exchange. We show that
fair and stable exchanges exist for all monotone continuous utility functions.
Next, we investigate the computational complexity of finding approximate fair
and stable exchanges. We present a local search algorithm for instances with
monotone submodular utility functions, where each agent contributions are
measured using the Shapley value. We prove that this problem lies in CLS under
mild assumptions. Our framework opens up several intriguing theoretical
directions for research in data economics.

It is known since 1975 (\cite{HK75}) that maximum cardinality matchings in
bipartite graphs with $n$ nodes and $m$ edges can be computed in time
$O(\sqrt{n} m)$. Asymptotically faster algorithms were found in the last decade
and maximum cardinality bipartite matchings can now be computed in near-linear
time~\cite{NearlyLinearTimeBipartiteMatching,
AlmostLinearTimeMaxFlow,AlmostLinearTimeMinCostFlow}. For general graphs, the
problem seems harder. Algorithms with running time $O(\sqrt{n} m)$ were given
in~\cite{MV80,Vazirani94,Vazirani12,Vazirani20,Vazirani23,Goldberg-Karzanov,GT91,Gabow:GeneralMatching}.
Mattingly and Ritchey~\cite{Mattingly-Ritchey} and Huang and
Stein~\cite{Huang-Stein} discuss implementations of the Micali-Vazirani
Algorithm. We describe an implementation of Gabow's
algorithm~\cite{Gabow:GeneralMatching} in C++ based on
LEDA~\cite{LEDAsystem,LEDAbook} and report on running time experiments. On
worst-case graphs, the asymptotic improvement pays off dramatically. On random
graphs, there is no improvement with respect to algorithms that have a
worst-case running time of $O(n m)$. The performance seems to be near-linear.
The implementation is available open-source.

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.

We study dynamic $(1-\epsilon)$-approximate rounding of fractional matchings
-- a key ingredient in numerous breakthroughs in the dynamic graph algorithms
literature. Our first contribution is a surprisingly simple deterministic
rounding algorithm in bipartite graphs with amortized update time
$O(\epsilon^{-1} \log^2 (\epsilon^{-1} \cdot n))$, matching an (unconditional)
recourse lower bound of $\Omega(\epsilon^{-1})$ up to logarithmic factors.
Moreover, this algorithm's update time improves provided the minimum (non-zero)
weight in the fractional matching is lower bounded throughout. Combining this
algorithm with novel dynamic \emph{partial rounding} algorithms to increase
this minimum weight, we obtain several algorithms that improve this dependence
on $n$. For example, we give a high-probability randomized algorithm with
$\tilde{O}(\epsilon^{-1}\cdot (\log\log n)^2)$-update time against adaptive
adversaries. (We use Soft-Oh notation, $\tilde{O}$, to suppress polylogarithmic
factors in the argument, i.e., $\tilde{O}(f)=O(f\cdot \mathrm{poly}(\log f))$.)
Using our rounding algorithms, we also round known $(1-\epsilon)$-decremental
fractional bipartite matching algorithms with no asymptotic overhead, thus
improving on state-of-the-art algorithms for the decremental bipartite matching
problem. Further, we provide extensions of our results to general graphs and to
maintaining almost-maximal matchings.

We study online bipartite edge coloring, with nodes on one side of the graph
revealed sequentially. The trivial greedy algorithm is $(2-o(1))$-competitive,
which is optimal for graphs of low maximum degree, $\Delta=O(\log n)$ [BNMN
IPL'92]. Numerous online edge-coloring algorithms outperforming the greedy
algorithm in various settings were designed over the years (e.g., AGKM FOCS'03,
BMM SODA'10, CPW FOCS'19, BGW SODA'21, KLSST STOC'22, BSVW STOC'24), all
crucially relying on randomization. A commonly-held belief, first stated by
[BNMN IPL'92], is that randomization is necessary to outperform greedy.
Surprisingly, we refute this belief, by presenting a deterministic algorithm
that beats greedy for sufficiently large $\Delta=\Omega(\log n)$, and in
particular has competitive ratio $\frac{e}{e-1}+o(1)$ for all
$\Delta=\omega(\log n)$. We obtain our result via a new and surprisingly simple
randomized algorithm that works against adaptive adversaries (as opposed to
oblivious adversaries assumed by prior work), which implies the existence of a
similarly-competitive deterministic algorithm [BDBKTW STOC'90].

Given two matroids $\mathcal{M}_1$ and $\mathcal{M}_2$ over the same
$n$-element ground set, the matroid intersection problem is to find a largest
common independent set, whose size we denote by $r$. We present a simple and
generic auction algorithm that reduces $(1-\varepsilon)$-approximate matroid
intersection to roughly $1/\varepsilon^2$ rounds of the easier problem of
finding a maximum-weight basis of a single matroid. Plugging in known
primitives for this subproblem, we obtain both simpler and improved algorithms
in two models of computation, including:
* The first near-linear time/independence-query
$(1-\varepsilon)$-approximation algorithm for matroid intersection. Our
randomized algorithm uses $\tilde{O}(n/\varepsilon + r/\varepsilon^5)$
independence queries, improving upon the previous $\tilde{O}(n/\varepsilon +
r\sqrt{r}/{\varepsilon^3})$ bound of Quanrud (2024).
* The first sublinear exact parallel algorithms for weighted matroid
intersection, using $O(n^{2/3})$ rounds of rank queries or $O(n^{5/6})$ rounds
of independence queries. For the unweighted case, our results improve upon the
previous $O(n^{3/4})$-round rank-query and $O(n^{7/8})$-round
independence-query algorithms of Blikstad (2022).

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].

For the vertex selection problem $(\sigma,\rho)$-DomSet one is given two
fixed sets $\sigma$ and $\rho$ of integers and the task is to decide whether we
can select vertices of the input graph, such that, for every selected vertex,
the number of selected neighbors is in $\sigma$ and, for every unselected
vertex, the number of selected neighbors is in $\rho$. This framework covers
Independent Set and Dominating Set for example.
We investigate the case when $\sigma$ and $\rho$ are periodic sets with the
same period $m\ge 2$, that is, the sets are two (potentially different) residue
classes modulo $m$. We study the problem parameterized by treewidth and present
an algorithm that solves in time $m^{tw} \cdot n^{O(1)}$ the decision,
minimization and maximization version of the problem. This significantly
improves upon the known algorithms where for the case $m \ge 3$ not even an
explicit running time is known. We complement our algorithm by providing
matching lower bounds which state that there is no $(m-\epsilon)^{pw} \cdot
n^{O(1)}$ unless SETH fails. For $m = 2$, we extend these bound to the
minimization version as the decision version is efficiently solvable.

We initiate the study of the following general clustering problem. We seek to
partition a given set $P$ of data points into $k$ clusters by finding a set $X$
of $k$ centers and assigning each data point to one of the centers. The cost of
a cluster, represented by a center $x\in X$, is a monotone, symmetric norm $f$
(inner norm) of the vector of distances of points assigned to $x$. The goal is
to minimize a norm $g$ (outer norm) of the vector of cluster costs. This
problem, which we call $(f,g)$-Clustering, generalizes many fundamental
clustering problems such as $k$-Center, $k$-Median , Min-Sum of Radii, and
Min-Load $k$-Clustering . A recent line of research (Chakrabarty, Swamy
[STOC'19]) studies norm objectives that are oblivious to the cluster structure
such as $k$-Median and $k$-Center. In contrast, our problem models
cluster-aware objectives including Min-Sum of Radii and Min-Load
$k$-Clustering.
Our main results are as follows. First, we design a constant-factor
approximation algorithm for $(\textsf{top}_\ell,\mathcal{L}_1)$-Clustering
where the inner norm ($\textsf{top}_\ell$) sums over the $\ell$ largest
distances. Second, we design a constant-factor approximation\ for
$(\mathcal{L}_\infty,\textsf{Ord})$-Clustering where the outer norm is a convex
combination of $\textsf{top}_\ell$ norms (ordered weighted norm).

In this paper, we study the problem of finding an envy-free allocation of
indivisible goods among multiple agents. EFX, which stands for envy-freeness up
to any good, is a well-studied relaxation of the envy-free allocation problem
and has been shown to exist for specific scenarios. For instance, EFX is known
to exist when there are only three agents [Chaudhury et al, EC 2020], and for
any number of agents when there are only two types of valuations [Mahara,
Discret. Appl. Math 2023].
We show that EFX allocations exist for any number of agents when there are at
most three types of additive valuations.

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.

A set of $m$ indivisible goods is to be allocated to a set of $n$ agents.
Each agent $i$ has an additive valuation function $v_i$ over goods. The value
of a good $g$ for agent $i$ is either $1$ or $s$, where $s$ is a fixed rational
number greater than one, and the value of a bundle of goods is the sum of the
values of the goods in the bundle. An \emph{allocation} $X$ is a partition of
the goods into bundles $X_1$, \ldots, $X_n$, one for each agent. The \emph{Nash
Social Welfare} ($\NSW$) of an allocation $X$ is defined as \[ \NSW(X) = \left(
\prod_i v_i(X_i) \right)^{\sfrac{1}{n}}.\] The \emph{$\NSW$-allocation}
maximizes the Nash Social Welfare. In~\cite{NSW-twovalues-halfinteger} it was
shown that the $\NSW$-allocation can be computed in polynomial time, if $s$ is
an integer or a half-integer, and that the problem is NP-complete otherwise.
The proof for the half-integer case is quite involved. In this note we give a
simpler and shorter proof

A binary code Enc$:\{0,1\}^k \to \{0,1\}^n$ is $(0.5-\epsilon,L)$-list
decodable if for all $w \in \{0,1\}^n$, the set List$(w)$ of all messages $m
\in \{0,1\}^k$ such that the relative Hamming distance between Enc$(m)$ and $w$
is at most $0.5 -\epsilon$, has size at most $L$. Informally, a $q$-query local
list-decoder for Enc is a randomized procedure Dec$:[k]\times [L] \to \{0,1\}$
that when given oracle access to a string $w$, makes at most $q$ oracle calls,
and for every message $m \in \text{List}(w)$, with high probability, there
exists $j \in [L]$ such that for every $i \in [k]$, with high probability,
Dec$^w(i,j)=m_i$.
We prove lower bounds on $q$, that apply even if $L$ is huge (say
$L=2^{k^{0.9}}$) and the rate of Enc is small (meaning that $n \ge 2^{k}$):
1. For $\epsilon \geq 1/k^{\nu}$ for some universal constant $0< \nu < 1$, we
prove a lower bound of $q=\Omega(\frac{\log(1/\delta)}{\epsilon^2})$, where
$\delta$ is the error probability of the local list-decoder. This bound is
tight as there is a matching upper bound by Goldreich and Levin (STOC 1989) of
$q=O(\frac{\log(1/\delta)}{\epsilon^2})$ for the Hadamard code (which has
$n=2^k$). This bound extends an earlier work of Grinberg, Shaltiel and Viola
(FOCS 2018) which only works if $n \le 2^{k^{\gamma}}$ for some universal
constant $0<\gamma <1$, and the number of coins tossed by Dec is small (and
therefore does not apply to the Hadamard code, or other codes with low rate).
2. For smaller $\epsilon$, we prove a lower bound of roughly $q =
\Omega(\frac{1}{\sqrt{\epsilon}})$. To the best of our knowledge, this is the
first lower bound on the number of queries of local list-decoders that gives $q
\ge k$ for small $\epsilon$.
We also prove black-box limitations for improving some of the parameters of
the Goldreich-Levin hard-core predicate construction.

The traveling salesman (or salesperson) problem, short TSP, is a problem of
strong interest to many researchers from mathematics, economics, and computer
science. Manifold TSP variants occur in nearly every scientific field and
application domain: engineering, physics, biology, life sciences, and
manufacturing just to name a few. Several thousand papers are published on
theoretical research or application-oriented results each year. This paper
provides the first systematic survey on the best currently known
approximability and inapproximability results for well-known TSP variants such
as the "standard" TSP, Path TSP, Bottleneck TSP, Maximum Scatter TSP,
Generalized TSP, Clustered TSP, Traveling Purchaser Problem, Profitable Tour
Problem, Quota TSP, Prize-Collecting TSP, Orienteering Problem, Time-dependent
TSP, TSP with Time Windows, and the Orienteering Problem with Time Windows. The
foundation of our survey is the definition scheme T3CO, which we propose as a
uniform, easy-to-use and extensible means for the formal and precise definition
of TSP variants. Applying T3CO to formally define the variant studied by a
paper reveals subtle differences within the same named variant and also brings
out the differences between the variants more clearly. We achieve the first
comprehensive, concise, and compact representation of approximability results
by using T3CO definitions. This makes it easier to understand the
approximability landscape and the assumptions under which certain results hold.
Open gaps become more evident and results can be compared more easily.

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

The existence of EFX allocations is a fundamental open problem in discrete
fair division. Given a set of agents and indivisible goods, the goal is to
determine the existence of an allocation where no agent envies another
following the removal of any single good from the other agent's bundle. Since
the general problem has been illusive, progress is made on two fronts: $(i)$
proving existence when the number of agents is small, $(ii)$ proving existence
of relaxations of EFX. In this paper, we improve results on both fronts (and
simplify in one of the cases).
We prove the existence of EFX allocations with three agents, restricting only
one agent to have an MMS-feasible valuation function (a strict generalization
of nice-cancelable valuation functions introduced by Berger et al. which
subsumes additive, budget-additive and unit demand valuation functions). The
other agents may have any monotone valuation functions. Our proof technique is
significantly simpler and shorter than the proof by Chaudhury et al. on
existence of EFX allocations when there are three agents with additive
valuation functions and therefore more accessible.
Secondly, we consider relaxations of EFX allocations, namely, approximate-EFX
allocations and EFX allocations with few unallocated goods (charity). Chaudhury
et al. showed the existence of $(1-\epsilon)$-EFX allocation with
$O((n/\epsilon)^{\frac{4}{5}})$ charity by establishing a connection to a
problem in extremal combinatorics. We improve their result and prove the
existence of $(1-\epsilon)$-EFX allocations with $\tilde{O}((n/
\epsilon)^{\frac{1}{2}})$ charity. In fact, some of our techniques can be used
to prove improved upper-bounds on a problem in zero-sum combinatorics
introduced by Alon and Krivelevich.

We consider the problem of maximizing the Nash social welfare when allocating
a set $G$ of indivisible goods to a set $N$ of agents. We study instances, in
which all agents have 2-value additive valuations: The value of a good $g \in
G$ for an agent $i \in N$ is either $1$ or $s$, where $s$ is an odd multiple of
$\frac{1}{2}$ larger than one. We show that the problem is solvable in
polynomial time. Akrami et at. showed that this problem is solvable in
polynomial time if $s$ is integral and is NP-hard whenever $s = \frac{p}{q}$,
$p \in \mathbb{N}$ and $q\in \mathbb{N}$ are co-prime and $p > q \ge 3$. For
the latter situation, an approximation algorithm was also given. It obtains an
approximation ratio of at most $1.0345$. Moreover, the problem is APX-hard,
with a lower bound of $1.000015$ achieved at $\frac{p}{q} = \frac{5}{4}$. The
case $q = 2$ and odd $p$ was left open.
In the case of integral $s$, the problem is separable in the sense that the
optimal allocation of the heavy goods (= value $s$ for some agent) is
independent of the number of light goods (= value $1$ for all agents). This
leads to an algorithm that first computes an optimal allocation of the heavy
goods and then adds the light goods greedily. This separation no longer holds
for $s = \frac{3}{2}$; a simple example is given in the introduction. Thus an
algorithm has to consider heavy and light goods together. This complicates
matters considerably. Our algorithm is based on a collection of improvement
rules that transfers any allocation into an optimal allocation and exploits a
connection to matchings with parity constraints.

We study the problem of fairly allocating a set of $m$ indivisible goods to a
set of $n$ agents. Envy-freeness up to any good (EFX) criteria -- which
requires that no agent prefers the bundle of another agent after removal of any
single good -- is known to be a remarkable analogous of envy-freeness when the
resource is a set of indivisible goods. In this paper, we investigate EFX
notion for the restricted additive valuations, that is, every good has some
non-negative value, and every agent is interested in only some of the goods.
We introduce a natural relaxation of EFX called EFkX which requires that no
agent envies another agent after removal of any $k$ goods. Our main
contribution is an algorithm that finds a complete (i.e., no good is discarded)
EF2X allocation for the restricted additive valuations. In our algorithm we
devise new concepts, namely "configuration" and "envy-elimination" that might
be of independent interest.
We also use our new tools to find an EFX allocation for restricted additive
valuations that discards at most $\lfloor n/2 \rfloor -1$ goods. This improves
the state of the art for the restricted additive valuations by a factor of $2$.

Given the rapid rise in energy demand by data centers and computing systems
in general, it is fundamental to incorporate energy considerations when
designing (scheduling) algorithms. Machine learning can be a useful approach in
practice by predicting the future load of the system based on, for example,
historical data. However, the effectiveness of such an approach highly depends
on the quality of the predictions and can be quite far from optimal when
predictions are sub-par. On the other hand, while providing a worst-case
guarantee, classical online algorithms can be pessimistic for large classes of
inputs arising in practice.
This paper, in the spirit of the new area of machine learning augmented
algorithms, attempts to obtain the best of both worlds for the classical,
deadline based, online speed-scaling problem: Based on the introduction of a
novel prediction setup, we develop algorithms that (i) obtain provably low
energy-consumption in the presence of adequate predictions, and (ii) are robust
against inadequate predictions, and (iii) are smooth, i.e., their performance
gradually degrades as the prediction error increases.

Paging is a prototypical problem in the area of online algorithms. It has
also played a central role in the development of learning-augmented algorithms
-- a recent line of research that aims to ameliorate the shortcomings of
classical worst-case analysis by giving algorithms access to predictions. Such
predictions can typically be generated using a machine learning approach, but
they are inherently imperfect. Previous work on learning-augmented paging has
investigated predictions on (i) when the current page will be requested again
(reoccurrence predictions), (ii) the current state of the cache in an optimal
algorithm (state predictions), (iii) all requests until the current page gets
requested again, and (iv) the relative order in which pages are requested.
We study learning-augmented paging from the new perspective of requiring the
least possible amount of predicted information. More specifically, the
predictions obtained alongside each page request are limited to one bit only.
We consider two natural such setups: (i) discard predictions, in which the
predicted bit denotes whether or not it is ``safe'' to evict this page, and
(ii) phase predictions, where the bit denotes whether the current page will be
requested in the next phase (for an appropriate partitioning of the input into
phases). We develop algorithms for each of the two setups that satisfy all
three desirable properties of learning-augmented algorithms -- that is, they
are consistent, robust and smooth -- despite being limited to a one-bit
prediction per request. We also present lower bounds establishing that our
algorithms are essentially best possible.

We study sublinear time algorithms for estimating the size of maximum
matching. After a long line of research, the problem was finally settled by
Behnezhad [FOCS'22], in the regime where one is willing to pay an approximation
factor of $2$. Very recently, Behnezhad et al.[SODA'23] improved the
approximation factor to $(2-\frac{1}{2^{O(1/\gamma)}})$ using $n^{1+\gamma}$
time. This improvement over the factor $2$ is, however, minuscule and they
asked if even $1.99$-approximation is possible in $n^{2-\Omega(1)}$ time. We
give a strong affirmative answer to this open problem by showing
$(1.5+\epsilon)$-approximation algorithms that run in
$n^{2-\Theta(\epsilon^{2})}$ time. Our approach is conceptually simple and
diverges from all previous sublinear-time matching algorithms: we show a
sublinear time algorithm for computing a variant of the edge-degree constrained
subgraph (EDCS), a concept that has previously been exploited in dynamic
[Bernstein Stein ICALP'15, SODA'16], distributed [Assadi et al. SODA'19] and
streaming [Bernstein ICALP'20] settings, but never before in the sublinear
setting. Independent work: Behnezhad, Roghani and Rubinstein [BRR'23]
independently showed sublinear algorithms similar to our Theorem 1.2 in both
adjacency list and matrix models. Furthermore, in [BRR'23], they show
additional results on strictly better-than-1.5 approximate matching algorithms
in both upper and lower bound sides.

The circumference of a graph $G$ is the length of a longest cycle in $G$, or
$+\infty$ if $G$ has no cycle. Birmel\'e (2003) showed that the treewidth of a
graph $G$ is at most its circumference minus one. We strengthen this result for
$2$-connected graphs as follows: If $G$ is $2$-connected, then its treedepth is
at most its circumference. The bound is best possible and improves on an
earlier quadratic upper bound due to Marshall and Wood (2015).

We consider the approximate pattern matching problem under the edit distance.
Given a text $T$ of length $n$, a pattern $P$ of length $m$, and a threshold
$k$, the task is to find the starting positions of all substrings of $T$ that
can be transformed to $P$ with at most $k$ edits. More than 20 years ago, Cole
and Hariharan [SODA'98, J. Comput.'02] gave an $\mathcal{O}(n+k^4 \cdot n/
m)$-time algorithm for this classic problem, and this runtime has not been
improved since.
Here, we present an algorithm that runs in time $\mathcal{O}(n+k^{3.5}
\sqrt{\log m \log k} \cdot n/m)$, thus breaking through this long-standing
barrier. In the case where $n^{1/4+\varepsilon} \leq k \leq
n^{2/5-\varepsilon}$ for some arbitrarily small positive constant
$\varepsilon$, our algorithm improves over the state-of-the-art by polynomial
factors: it is polynomially faster than both the algorithm of Cole and
Hariharan and the classic $\mathcal{O}(kn)$-time algorithm of Landau and
Vishkin [STOC'86, J. Algorithms'89].
We observe that the bottleneck case of the alternative $\mathcal{O}(n+k^4
\cdot n/m)$-time algorithm of Charalampopoulos, Kociumaka, and Wellnitz
[FOCS'20] is when the text and the pattern are (almost) periodic. Our new
algorithm reduces this case to a new dynamic problem (Dynamic Puzzle Matching),
which we solve by building on tools developed by Tiskin [SODA'10,
Algorithmica'15] for the so-called seaweed monoid of permutation matrices. Our
algorithm relies only on a small set of primitive operations on strings and
thus also applies to the fully-compressed setting (where text and pattern are
given as straight-line programs) and to the dynamic setting (where we maintain
a collection of strings under creation, splitting, and concatenation),
improving over the state of the art.

We introduce Hyperbard, a dataset of diverse relational data representations
derived from Shakespeare's plays. Our representations range from simple graphs
capturing character co-occurrence in single scenes to hypergraphs encoding
complex communication settings and character contributions as hyperedges with
edge-specific node weights. By making multiple intuitive representations
readily available for experimentation, we facilitate rigorous representation
robustness checks in graph learning, graph mining, and network analysis,
highlighting the advantages and drawbacks of specific representations.
Leveraging the data released in Hyperbard, we demonstrate that many solutions
to popular graph mining problems are highly dependent on the representation
choice, thus calling current graph curation practices into question. As an
homage to our data source, and asserting that science can also be art, we
present all our points in the form of a play.

We introduce seven foundational principles for creating a culture of
constructive criticism in computational legal studies. Beginning by challenging
the current perception of papers as the primary scholarly output, we call for a
more comprehensive interpretation of publications. We then suggest to make
these publications computationally reproducible, releasing all of the data and
all of the code all of the time, on time, and in the most functioning form
possible. Subsequently, we invite constructive criticism in all phases of the
publication life cycle. We posit that our proposals will help form our field,
and float the idea of marking this maturity by the creation of a modern
flagship publication outlet for computational legal studies.

How does neural connectivity in autistic children differ from neural
connectivity in healthy children or autistic youths? What patterns in global
trade networks are shared across classes of goods, and how do these patterns
change over time? Answering questions like these requires us to differentially
describe groups of graphs: Given a set of graphs and a partition of these
graphs into groups, discover what graphs in one group have in common, how they
systematically differ from graphs in other groups, and how multiple groups of
graphs are related. We refer to this task as graph group analysis, which seeks
to describe similarities and differences between graph groups by means of
statistically significant subgraphs. To perform graph group analysis, we
introduce Gragra, which uses maximum entropy modeling to identify a
non-redundant set of subgraphs with statistically significant associations to
one or more graph groups. Through an extensive set of experiments on a wide
range of synthetic and real-world graph groups, we confirm that Gragra works
well in practice.

Makespan minimization on parallel identical machines is a classical and
intensively studied problem in scheduling, and a classic example for online
algorithm analysis with Graham's famous list scheduling algorithm dating back
to the 1960s. In this problem, jobs arrive over a list and upon an arrival, the
algorithm needs to assign the job to a machine. The goal is to minimize the
makespan, that is, the maximum machine load. In this paper, we consider the
variant with an additional cardinality constraint: The algorithm may assign at
most $k$ jobs to each machine where $k$ is part of the input. While the offline
(strongly NP-hard) variant of cardinality constrained scheduling is well
understood and an EPTAS exists here, no non-trivial results are known for the
online variant. We fill this gap by making a comprehensive study of various
different online models. First, we show that there is a constant competitive
algorithm for the problem and further, present a lower bound of $2$ on the
competitive ratio of any online algorithm. Motivated by the lower bound, we
consider a semi-online variant where upon arrival of a job of size $p$, we are
allowed to migrate jobs of total size at most a constant times $p$. This
constant is called the migration factor of the algorithm. Algorithms with small
migration factors are a common approach to bridge the performance of online
algorithms and offline algorithms. One can obtain algorithms with a constant
migration factor by rounding the size of each incoming job and then applying an
ordinal algorithm to the resulting rounded instance. With this in mind, we also
consider the framework of ordinal algorithms and characterize the competitive
ratio that can be achieved using the aforementioned approaches.

We generalize the monotone local search approach of Fomin, Gaspers,
Lokshtanov and Saurabh [J.ACM 2019], by establishing a connection between
parameterized approximation and exponential-time approximation algorithms for
monotone subset minimization problems. In a monotone subset minimization
problem the input implicitly describes a non-empty set family over a universe
of size $n$ which is closed under taking supersets. The task is to find a
minimum cardinality set in this family. Broadly speaking, we use approximate
monotone local search to show that a parameterized $\alpha$-approximation
algorithm that runs in $c^k \cdot n^{O(1)}$ time, where $k$ is the solution
size, can be used to derive an $\alpha$-approximation randomized algorithm that
runs in $d^n \cdot n^{O(1)}$ time, where $d$ is the unique value in $d \in
(1,1+\frac{c-1}{\alpha})$ such that
$\mathcal{D}(\frac{1}{\alpha}\|\frac{d-1}{c-1})=\frac{\ln c}{\alpha}$ and
$\mathcal{D}(a \|b)$ is the Kullback-Leibler divergence. This running time
matches that of Fomin et al. for $\alpha=1$, and is strictly better when
$\alpha >1$, for any $c > 1$. Furthermore, we also show that this result can be
derandomized at the expense of a sub-exponential multiplicative factor in the
running time.
We demonstrate the potential of approximate monotone local search by deriving
new and faster exponential approximation algorithms for Vertex Cover,
$3$-Hitting Set, Directed Feedback Vertex Set, Directed Subset Feedback Vertex
Set, Directed Odd Cycle Transversal and Undirected Multicut. For instance, we
get a $1.1$-approximation algorithm for Vertex Cover with running time $1.114^n
\cdot n^{O(1)}$, improving upon the previously best known $1.1$-approximation
running in time $1.127^n \cdot n^{O(1)}$ by Bourgeois et al. [DAM 2011].

The Edge Multicut problem is a classical cut problem where given an
undirected graph $G$, a set of pairs of vertices $\mathcal{P}$, and a budget
$k$, the goal is to determine if there is a set $S$ of at most $k$ edges such
that for each $(s,t) \in \mathcal{P}$, $G-S$ has no path from $s$ to $t$. Edge
Multicut has been relatively recently shown to be fixed-parameter tractable
(FPT), parameterized by $k$, by Marx and Razgon [SICOMP 2014], and
independently by Bousquet et al. [SICOMP 2018]. In the weighted version of the
problem, called Weighted Edge Multicut one is additionally given a weight
function $\mathtt{wt} : E(G) \to \mathbb{N}$ and a weight bound $w$, and the
goal is to determine if there is a solution of size at most $k$ and weight at
most $w$. Both the FPT algorithms for Edge Multicut by Marx et al. and Bousquet
et al. fail to generalize to the weighted setting. In fact, the weighted
problem is non-trivial even on trees and determining whether Weighted Edge
Multicut on trees is FPT was explicitly posed as an open problem by Bousquet et
al. [STACS 2009]. In this article, we answer this question positively by
designing an algorithm which uses a very recent result by Kim et al. [STOC
2022] about directed flow augmentation as subroutine.
We also study a variant of this problem where there is no bound on the size
of the solution, but the parameter is a structural property of the input, for
example, the number of leaves of the tree. We strengthen our results by stating
them for the more general vertex deletion version.

The leafage of a chordal graph G is the minimum integer l such that G can be
realized as an intersection graph of subtrees of a tree with l leaves. We
consider structural parameterization by the leafage of classical domination and
cut problems on chordal graphs. Fomin, Golovach, and Raymond [ESA 2018,
Algorithmica 2020] proved, among other things, that Dominating Set on chordal
graphs admits an algorithm running in time $2^{O(l^2)} n^{O(1)}$. We present a
conceptually much simpler algorithm that runs in time $2^{O(l)} n^{O(1)}$. We
extend our approach to obtain similar results for Connected Dominating Set and
Steiner Tree. We then consider the two classical cut problems MultiCut with
Undeletable Terminals and Multiway Cut with Undeletable Terminals. We prove
that the former is W[1]-hard when parameterized by the leafage and complement
this result by presenting a simple $n^{O(l)}$-time algorithm. To our surprise,
we find that Multiway Cut with Undeletable Terminals on chordal graphs can be
solved, in contrast, in $n^{O(1)}$-time.

For a graph $G$, a subset $S \subseteq V(G)$ is called a \emph{resolving set}
if for any two vertices $u,v \in V(G)$, there exists a vertex $w \in S$ such
that $d(w,u) \neq d(w,v)$. The {\sc Metric Dimension} problem takes as input a
graph $G$ and a positive integer $k$, and asks whether there exists a resolving
set of size at most $k$. This problem was introduced in the 1970s and is known
to be NP-hard~[GT~61 in Garey and Johnson's book]. In the realm of
parameterized complexity, Hartung and Nichterlein~[CCC~2013] proved that the
problem is W[2]-hard when parameterized by the natural parameter $k$. They also
observed that it is FPT when parameterized by the vertex cover number and asked
about its complexity under \emph{smaller} parameters, in particular the
feedback vertex set number. We answer this question by proving that {\sc Metric
Dimension} is W[1]-hard when parameterized by the feedback vertex set number.
This also improves the result of Bonnet and Purohit~[IPEC 2019] which states
that the problem is W[1]-hard parameterized by the treewidth. Regarding the
parameterization by the vertex cover number, we prove that {\sc Metric
Dimension} does not admit a polynomial kernel under this parameterization
unless $NP\subseteq coNP/poly$. We observe that a similar result holds when the
parameter is the distance to clique. On the positive side, we show that {\sc
Metric Dimension} is FPT when parameterized by either the distance to cluster
or the distance to co-cluster, both of which are smaller parameters than the
vertex cover number.

In the Directed Steiner Network problem, the input is a directed graph G, a
subset T of k vertices of G called the terminals, and a demand graph D on T.
The task is to find a subgraph H of G with the minimum number of edges such
that for every edge (s,t) in D, the solution H contains a directed s to t path.
In this paper we investigate how the complexity of the problem depends on the
demand pattern when G is planar. Formally, if \mathcal{D} is a class of
directed graphs closed under identification of vertices, then the
\mathcal{D}-Steiner Network (\mathcal{D}-SN) problem is the special case where
the demand graph D is restricted to be from \mathcal{D}. For general graphs,
Feldmann and Marx [ICALP 2016] characterized those families of demand graphs
where the problem is fixed-parameter tractable (FPT) parameterized by the
number k of terminals. They showed that if \mathcal{D} is a superset of one of
the five hard families, then \mathcal{D}-SN is W[1]-hard parameterized by k,
otherwise it can be solved in time f(k)n^{O(1)}.
For planar graphs an interesting question is whether the W[1]-hard cases can
be solved by subexponential parameterized algorithms. Chitnis et al. [SICOMP
2020] showed that, assuming the ETH, there is no f(k)n^{o(k)} time algorithm
for the general \mathcal{D}-SN problem on planar graphs, but the special case
called Strongly Connected Steiner Subgraph can be solved in time f(k)
n^{O(\sqrt{k})} on planar graphs. We present a far-reaching generalization and
unification of these two results: we give a complete characterization of the
behavior of every $\mathcal{D}$-SN problem on planar graphs. We show that
assuming ETH, either the problem is (1) solvable in time 2^{O(k)}n^{O(1)}, and
not in time 2^{o(k)}n^{O(1)}, or (2) solvable in time f(k)n^{O(\sqrt{k})}, but
not in time f(k)n^{o(\sqrt{k})}, or (3) solvable in time f(k)n^{O(k)}, but not
in time f(k)n^{o({k})}.

Physarum Polycephalum is a Slime mold that can solve the shortest path
problem. A mathematical model based on the Physarum's behavior, known as the
Physarum Directed Dynamics, can solve positive linear programs. In this paper,
we will propose a Physarum based dynamic based on the previous work and
introduce a new way to solve positive Semi-Definite Programming (SDP) problems,
which are more general than positive linear programs. Empirical results suggest
that this extension of the dynamic can solve the positive SDP showing that the
nature-inspired algorithm can solve one of the hardest problems in the
polynomial domain. In this work, we will formulate an accurate algorithm to
solve positive and some non-negative SDPs and formally prove some key
characteristics of this solver thus inspiring future work to try and refine
this method.

We study the online Traveling Salesman Problem (TSP) on the line augmented
with machine-learned predictions. In the classical problem, there is a stream
of requests released over time along the real line. The goal is to minimize the
makespan of the algorithm. We distinguish between the open variant and the
closed one, in which we additionally require the algorithm to return to the
origin after serving all requests. The state of the art is a $1.64$-competitive
algorithm and a $2.04$-competitive algorithm for the closed and open variants,
respectively \cite{Bjelde:1.64}. In both cases, a tight lower bound is known
\cite{Ausiello:1.75, Bjelde:1.64}.
In both variants, our primary prediction model involves predicted positions
of the requests. We introduce algorithms that (i) obtain a tight 1.5
competitive ratio for the closed variant and a 1.66 competitive ratio for the
open variant in the case of perfect predictions, (ii) are robust against
unbounded prediction error, and (iii) are smooth, i.e., their performance
degrades gracefully as the prediction error increases.
Moreover, we further investigate the learning-augmented setting in the open
variant by additionally considering a prediction for the last request served by
the optimal offline algorithm. Our algorithm for this enhanced setting obtains
a 1.33 competitive ratio with perfect predictions while also being smooth and
robust, beating the lower bound of 1.44 we show for our original prediction
setting for the open variant. Also, we provide a lower bound of 1.25 for this
enhanced setting.

A mixed graph has a set of vertices, a set of undirected egdes, and a set of
directed arcs. A proper coloring of a mixed graph $G$ is a function $c$ that
assigns to each vertex in $G$ a positive integer such that, for each edge $uv$
in $G$, $c(u) \ne c(v)$ and, for each arc $uv$ in $G$, $c(u) < c(v)$. For a
mixed graph $G$, the chromatic number $\chi(G)$ is the smallest number of
colors in any proper coloring of $G$. A directional interval graph is a mixed
graph whose vertices correspond to intervals on the real line. Such a graph has
an edge between every two intervals where one is contained in the other and an
arc between every two overlapping intervals, directed towards the interval that
starts and ends to the right.
Coloring such graphs has applications in routing edges in layered orthogonal
graph drawing according to the Sugiyama framework; the colors correspond to the
tracks for routing the edges. We show how to recognize directional interval
graphs, and how to compute their chromatic number efficiently. On the other
hand, for mixed interval graphs, i.e., graphs where two intersecting intervals
can be connected by an edge or by an arc in either direction arbitrarily, we
prove that computing the chromatic number is NP-hard.

We show fixed-parameter tractability of the Directed Multicut problem with
three terminal pairs (with a randomized algorithm). This problem, given a
directed graph $G$, pairs of vertices (called terminals) $(s_1,t_1)$,
$(s_2,t_2)$, and $(s_3,t_3)$, and an integer $k$, asks to find a set of at most
$k$ non-terminal vertices in $G$ that intersect all $s_1t_1$-paths, all
$s_2t_2$-paths, and all $s_3t_3$-paths. The parameterized complexity of this
case has been open since Chitnis, Cygan, Hajiaghayi, and Marx proved
fixed-parameter tractability of the 2-terminal-pairs case at SODA 2012, and
Pilipczuk and Wahlstr\"{o}m proved the W[1]-hardness of the 4-terminal-pairs
case at SODA 2016.
On the technical side, we use two recent developments in parameterized
algorithms. Using the technique of directed flow-augmentation [Kim, Kratsch,
Pilipczuk, Wahlstr\"{o}m, STOC 2022] we cast the problem as a CSP problem with
few variables and constraints over a large ordered domain.We observe that this
problem can be in turn encoded as an FO model-checking task over a structure
consisting of a few 0-1 matrices. We look at this problem through the lenses of
twin-width, a recently introduced structural parameter [Bonnet, Kim,
Thomass\'{e}, Watrigant, FOCS 2020]: By a recent characterization [Bonnet,
Giocanti, Ossona de Mendes, Simon, Thomass\'{e}, Toru\'{n}czyk, STOC 2022] the
said FO model-checking task can be done in FPT time if the said matrices have
bounded grid rank. To complete the proof, we show an irrelevant vertex rule: If
any of the matrices in the said encoding has a large grid minor, a vertex
corresponding to the ``middle'' box in the grid minor can be proclaimed
irrelevant -- not contained in the sought solution -- and thus reduced.

We show that the $b$-Coloring problem is complete for the class XNLP when
parameterized by the pathwidth of the input graph. Besides determining the
precise parameterized complexity of this problem, this implies that b-Coloring
parameterized by pathwidth is $W[t]$-hard for all $t$, and resolves the
parameterized complexity of $b$-Coloring parameterized by treewidth.

One of the first application of the recently introduced technique of
\emph{flow-augmentation} [Kim et al., STOC 2022] is a fixed-parameter algorithm
for the weighted version of \textsc{Directed Feedback Vertex Set}, a landmark
problem in parameterized complexity. In this note we explore applicability of
flow-augmentation to other weighted graph separation problems parameterized by
the size of the cutset. We show the following. -- In weighted undirected graphs
\textsc{Multicut} is FPT, both in the edge- and vertex-deletion version. -- The
weighted version of \textsc{Group Feedback Vertex Set} is FPT, even with an
oracle access to group operations. -- The weighted version of \textsc{Directed
Subset Feedback Vertex Set} is FPT. Our study reveals \textsc{Directed
Symmetric Multicut} as the next important graph separation problem whose
parameterized complexity remains unknown, even in the unweighted setting.

Formal models of learning from teachers need to respect certain criteria to
avoid collusion. The most commonly accepted notion of collusion-freeness was
proposed by Goldman and Mathias (1996), and various teaching models obeying
their criterion have been studied. For each model $M$ and each concept class
$\mathcal{C}$, a parameter $M$-$\mathrm{TD}(\mathcal{C})$ refers to the
teaching dimension of concept class $\mathcal{C}$ in model $M$---defined to be
the number of examples required for teaching a concept, in the worst case over
all concepts in $\mathcal{C}$.
This paper introduces a new model of teaching, called no-clash teaching,
together with the corresponding parameter $\mathrm{NCTD}(\mathcal{C})$.
No-clash teaching is provably optimal in the strong sense that, given any
concept class $\mathcal{C}$ and any model $M$ obeying Goldman and Mathias's
collusion-freeness criterion, one obtains $\mathrm{NCTD}(\mathcal{C})\le
M$-$\mathrm{TD}(\mathcal{C})$. We also study a corresponding notion
$\mathrm{NCTD}^+$ for the case of learning from positive data only, establish
useful bounds on $\mathrm{NCTD}$ and $\mathrm{NCTD}^+$, and discuss relations
of these parameters to the VC-dimension and to sample compression.
In addition to formulating an optimal model of collusion-free teaching, our
main results are on the computational complexity of deciding whether
$\mathrm{NCTD}^+(\mathcal{C})=k$ (or $\mathrm{NCTD}(\mathcal{C})=k$) for given
$\mathcal{C}$ and $k$. We show some such decision problems to be equivalent to
the existence question for certain constrained matchings in bipartite graphs.
Our NP-hardness results for the latter are of independent interest in the study
of constrained graph matchings.

For a positive integer $\ell \geq 3$, the $C_\ell$-Contractibility problem
takes as input an undirected simple graph $G$ and determines whether $G$ can be
transformed into a graph isomorphic to $C_\ell$ (the induced cycle on $\ell$
vertices) using only edge contractions. Brouwer and Veldman [JGT 1987] showed
that $C_4$-Contractibility is NP-complete in general graphs. It is easy to
verify that $C_3$-Contractibility is polynomial-time solvable. Dabrowski and
Paulusma [IPL 2017] showed that $C_{\ell}$-Contractibility is \NP-complete\ on
bipartite graphs for $\ell = 6$ and posed as open problems the status of the
problem when $\ell$ is 4 or 5. In this paper, we show that both
$C_5$-Contractibility and $C_4$-Contractibility are NP-complete on bipartite
graphs.

We introduce the notion of {\em fair cuts} as an approach to leverage
approximate $(s,t)$-mincut (equivalently $(s,t)$-maxflow) algorithms in
undirected graphs to obtain near-linear time approximation algorithms for
several cut problems. Informally, for any $\alpha\geq 1$, an $\alpha$-fair
$(s,t)$-cut is an $(s,t)$-cut such that there exists an $(s,t)$-flow that uses
$1/\alpha$ fraction of the capacity of \emph{every} edge in the cut. (So, any
$\alpha$-fair cut is also an $\alpha$-approximate mincut, but not vice-versa.)
We give an algorithm for $(1+\epsilon)$-fair $(s,t)$-cut in
$\tilde{O}(m)$-time, thereby matching the best runtime for
$(1+\epsilon)$-approximate $(s,t)$-mincut [Peng, SODA '16]. We then demonstrate
the power of this approach by showing that this result almost immediately leads
to several applications:
- the first nearly-linear time $(1+\epsilon)$-approximation algorithm that
computes all-pairs maxflow values (by constructing an approximate Gomory-Hu
tree). Prior to our work, such a result was not known even for the special case
of Steiner mincut [Dinitz and Vainstein, STOC '94; Cole and Hariharan, STOC
'03];
- the first almost-linear-work subpolynomial-depth parallel algorithms for
computing $(1+\epsilon)$-approximations for all-pairs maxflow values (again via
an approximate Gomory-Hu tree) in unweighted graphs;
- the first near-linear time expander decomposition algorithm that works even
when the expansion parameter is polynomially small; this subsumes previous
incomparable algorithms [Nanongkai and Saranurak, FOCS '17; Wulff-Nilsen, FOCS
'17; Saranurak and Wang, SODA '19].