Publications

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

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

This paper presents parallel and distributed algorithms for single-source
shortest paths when edges can have negative weights (negative-weight SSSP). We
show a framework that reduces negative-weight SSSP in either setting to
$n^{o(1)}$ calls to any SSSP algorithm that works with a virtual source. More
specifically, for a graph with $m$ edges, $n$ vertices, undirected hop-diameter
$D$, and polynomially bounded integer edge weights, we show randomized
algorithms for negative-weight SSSP with (i) $W_{SSSP}(m,n)n^{o(1)}$ work and
$S_{SSSP}(m,n)n^{o(1)}$ span, given access to an SSSP algorithm with
$W_{SSSP}(m,n)$ work and $S_{SSSP}(m,n)$ span in the parallel model, (ii)
$T_{SSSP}(n,D)n^{o(1)}$, given access to an SSSP algorithm that takes
$T_{SSSP}(n,D)$ rounds in $\mathsf{CONGEST}$. This work builds off the recent
result of [Bernstein, Nanongkai, Wulff-Nilsen, FOCS'22], which gives a
near-linear time algorithm for negative-weight SSSP in the sequential setting.
Using current state-of-the-art SSSP algorithms yields randomized algorithms
for negative-weight SSSP with (i) $m^{1+o(1)}$ work and $n^{1/2+o(1)}$ span in
the parallel model, (ii) $(n^{2/5}D^{2/5} + \sqrt{n} + D)n^{o(1)}$ rounds in
$\mathsf{CONGEST}$.
Our main technical contribution is an efficient reduction for computing a
low-diameter decomposition (LDD) of directed graphs to computations of SSSP
with a virtual source. Efficiently computing an LDD has heretofore only been
known for undirected graphs in both the parallel and distributed models. The
LDD is a crucial step of the algorithm in [Bernstein, Nanongkai, Wulff-Nilsen,
FOCS'22], and we think that its applications to other problems in parallel and
distributed models are far from being exhausted.

We present a randomized algorithm that computes single-source shortest paths
(SSSP) in $O(m\log^8(n)\log W)$ time when edge weights are integral and can be
negative. This essentially resolves the classic negative-weight SSSP problem.
The previous bounds are $\tilde O((m+n^{1.5})\log W)$ [BLNPSSSW FOCS'20] and
$m^{4/3+o(1)}\log W$ [AMV FOCS'20]. Near-linear time algorithms were known
previously only for the special case of planar directed graphs [Fakcharoenphol
and Rao FOCS'01].
In contrast to all recent developments that rely on sophisticated continuous
optimization methods and dynamic algorithms, our algorithm is simple: it
requires only a simple graph decomposition and elementary combinatorial tools.
In fact, ours is the first combinatorial algorithm for negative-weight SSSP to
break through the classic $\tilde O(m\sqrt{n}\log W)$ bound from over three
decades ago [Gabow and Tarjan SICOMP'89].

We show a fully dynamic algorithm for maintaining $(1+\epsilon)$-approximate
\emph{size} of maximum matching of the graph with $n$ vertices and $m$ edges
using $m^{0.5-\Omega_{\epsilon}(1)}$ update time. This is the first polynomial
improvement over the long-standing $O(n)$ update time, which can be trivially
obtained by periodic recomputation. Thus, we resolve the value version of a
major open question of the dynamic graph algorithms literature (see, e.g.,
[Gupta and Peng FOCS'13], [Bernstein and Stein SODA'16],[Behnezhad and Khanna
SODA'22]).
Our key technical component is the first sublinear algorithm for $(1,\epsilon
n)$-approximate maximum matching with sublinear running time on dense graphs.
All previous algorithms suffered a multiplicative approximation factor of at
least $1.499$ or assumed that the graph has a very small maximum degree.

In the dynamic approximate maximum bipartite matching problem we are given
bipartite graph $G$ undergoing updates and our goal is to maintain a matching
of $G$ which is large compared the maximum matching size $\mu(G)$. We define a
dynamic matching algorithm to be $\alpha$ (respectively $(\alpha,
\beta)$)-approximate if it maintains matching $M$ such that at all times $|M |
\geq \mu(G) \cdot \alpha$ (respectively $|M| \geq \mu(G) \cdot \alpha -
\beta$).
We present the first deterministic $(1-\epsilon )$-approximate dynamic
matching algorithm with $O(poly(\epsilon ^{-1}))$ amortized update time for
graphs undergoing edge insertions. Previous solutions either required
super-constant [Gupta FSTTCS'14, Bhattacharya-Kiss-Saranurak SODA'23] or
exponential in $1/\epsilon $
[Grandoni-Leonardi-Sankowski-Schwiegelshohn-Solomon SODA'19] update time. Our
implementation is arguably simpler than the mentioned algorithms and its
description is self contained. Moreover, we show that if we allow for additive
$(1, \epsilon \cdot n)$-approximation our algorithm seamlessly extends to also
handle vertex deletions, on top of edge insertions. This makes our algorithm
one of the few small update time algorithms for $(1-\epsilon )$-approximate
dynamic matching allowing for updates both increasing and decreasing the
maximum matching size of $G$ in a fully dynamic manner.

Bridging geometry and topology, curvature is a powerful and expressive invariant. While the utility of curvature has been theoretically and empirically confirmed in the context of manifolds and graphs, its generalization to the emerging domain of hypergraphs has remained largely unexplored. On graphs, Ollivier-Ricci curvature measures differences between random walks via Wasserstein distances, thus grounding a geometric concept in ideas from probability and optimal transport. We develop ORCHID, a flexible framework generalizing Ollivier-Ricci curvature to hypergraphs, and prove that the resulting curvatures have favorable theoretical properties. Through extensive experiments on synthetic and real-world hypergraphs from different domains, we demonstrate that ORCHID curvatures are both scalable and useful to perform a variety of hypergraph tasks in practice.

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

The notion of Las Vegas algorithm was introduced by Babai (1979) and may be
defined in two ways:
* In Babai's original definition, a randomized algorithm is called Las Vegas
if it has finitely bounded running time and certifiable random failure.
* Alternatively, in a widely accepted definition today, Las Vegas algorithms
mean the zero-error randomized algorithms with random running time.
The equivalence between the two definitions is straightforward. In
particular, by repeatedly running the algorithm until no failure encountered,
one can simulate the correct output of a successful running.
We show that this can also be achieved for distributed local computation.
Specifically, we show that in the LOCAL model, any Las Vegas algorithm that
terminates in finite time with locally certifiable failures, can be converted
to a zero-error Las Vegas algorithm, at a polylogarithmic cost in the time
complexity, such that the resulting algorithm perfectly simulates the output of
the original algorithm on the same instance conditioned on that the algorithm
successfully returns without failure.

We introduce a new algorithm and software for solving linear equations in
symmetric diagonally dominant matrices with non-positive off-diagonal entries
(SDDM matrices), including Laplacian matrices. We use pre-conditioned conjugate
gradient (PCG) to solve the system of linear equations. Our preconditioner is a
variant of the Approximate Cholesky factorization of Kyng and Sachdeva (FOCS
2016). Our factorization approach is simple: we eliminate matrix rows/columns
one at a time and update the remaining matrix using sampling to approximate the
outcome of complete Cholesky factorization. Unlike earlier approaches, our
sampling always maintains a connectivity in the remaining non-zero structure.
Our algorithm comes with a tuning parameter that upper bounds the number of
samples made per original entry. We implement our algorithm in Julia, providing
two versions, AC and AC2, that respectively use 1 and 2 samples per original
entry. We compare their single-threaded performance to that of current
state-of-the-art solvers Combinatorial Multigrid (CMG),
BoomerAMG-preconditioned Krylov solvers from HyPre and PETSc, Lean Algebraic
Multigrid (LAMG), and MATLAB's with Incomplete Cholesky Factorization (ICC).
Our evaluation uses a broad class of problems, including all large SDDM
matrices from the SuiteSparse collection and diverse programmatically generated
instances. Our experiments suggest that our algorithm attains a level of
robustness and reliability not seen before in SDDM solvers, while retaining
good performance across all instances. Our code and data are public, and we
provide a tutorial on how to replicate our tests. We hope that others will
adopt this suite of tests as a benchmark, which we refer to as SDDM2023. Our
solver code is available at: github.com/danspielman/Laplacians.jl/ Our
benchmarking data and tutorial are available at:
rjkyng.github.io/SDDM2023/

Dot-product attention mechanism plays a crucial role in modern deep
architectures (e.g., Transformer) for sequence modeling, however, na\"ive exact
computation of this model incurs quadratic time and memory complexities in
sequence length, hindering the training of long-sequence models. Critical
bottlenecks are due to the computation of partition functions in the
denominator of softmax function as well as the multiplication of the softmax
matrix with the matrix of values. Our key observation is that the former can be
reduced to a variant of the kernel density estimation (KDE) problem, and an
efficient KDE solver can be further utilized to accelerate the latter via
subsampling-based fast matrix products. Our proposed KDEformer can approximate
the attention in sub-quadratic time with provable spectral norm bounds, while
all prior results merely provide entry-wise error bounds. Empirically, we
verify that KDEformer outperforms other attention approximations in terms of
accuracy, memory, and runtime on various pre-trained models. On BigGAN image
generation, we achieve better generative scores than the exact computation with
over $4\times$ speedup. For ImageNet classification with T2T-ViT, KDEformer
shows over $18\times$ speedup while the accuracy drop is less than $0.5\%$.

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.

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 prove that for any triangle-free intersection graph of $n$ axis-parallel
segments in the plane, the independence number $\alpha$ of this graph is at
least $\alpha \ge n/4 + \Omega(\sqrt{n})$. We complement this with a
construction of a graph in this class satisfying $\alpha \le n/4 + c \sqrt{n}$
for an absolute constant $c$, which demonstrates the optimality of our result.

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.

In the Maximum Weight Independent Set of Rectangles problem (MWISR) we are
given a weighted set of $n$ axis-parallel rectangles in the plane. The task is
to find a subset of pairwise non-overlapping rectangles with the maximum
possible total weight. This problem is NP-hard and the best-known
polynomial-time approximation algorithm, due to by Chalermsook and Walczak
(SODA 2021), achieves approximation factor $O(\log\log n )$. While in the
unweighted setting, constant factor approximation algorithms are known, due to
Mitchell (FOCS 2021) and to G\'alvez et al. (SODA 2022), it remains open to
extend these techniques to the weighted setting.
In this paper, we consider MWISR through the lens of parameterized
approximation. Grandoni et al. (ESA 2019) gave a $(1-\epsilon)$-approximation
algorithm with running time $k^{O(k/\epsilon^8)} n^{O(1/\epsilon^8)}$ time,
where $k$ is the number of rectangles in an optimum solution. Unfortunately,
their algorithm works only in the unweighted setting and they left it as an
open problem to give a parameterized approximation scheme in the weighted
setting.
Our contribution is a partial answer to the open question of Grandoni et al.
(ESA 2019). We give a parameterized approximation algorithm for MWISR that
given a parameter $k$, finds a set of non-overlapping rectangles of weight at
least $(1-\epsilon) \text{opt}_k$ in $2^{O(k \log(k/\epsilon))}
n^{O(1/\epsilon)}$ time, where $\text{opt}_k$ is the maximum weight of a
solution of cardinality at most $k$. Note that thus, our algorithm may return a
solution consisting of more than $k$ rectangles. To complement this apparent
weakness, we also propose a parameterized approximation scheme with running
time $2^{O(k^2 \log(k/\epsilon))} n^{O(1)}$ that finds a solution with
cardinality at most $k$ and total weight at least $(1-\epsilon)\text{opt}_k$
for the special case of axis-parallel segments.

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

In a classical scheduling problem, we are given a set of $n$ jobs of unit
length along with precedence constraints and the goal is to find a schedule of
these jobs on $m$ identical machines that minimizes the makespan. This problem
is well-known to be NP-hard for an unbounded number of machines. Using standard
3-field notation, it is known as $P|\text{prec}, p_j=1|C_{\max}$.
We present an algorithm for this problem that runs in $O(1.995^n)$ time.
Before our work, even for $m=3$ machines the best known algorithms ran in
$O^\ast(2^n)$ time. In contrast, our algorithm works when the number of
machines $m$ is unbounded. A crucial ingredient of our approach is an algorithm
with a runtime that is only single-exponential in the vertex cover of the
comparability graph of the precedence constraint graph. This heavily relies on
insights from a classical result by Dolev and Warmuth (Journal of Algorithms
1984) for precedence graphs without long chains.

We study distributed systems, with a particular focus on graph problems and fault
tolerance.
Fault-tolerance in a microprocessor or even System-on-Chip can be improved by using
a fault-tolerant pulse propagation design. The existing design TRIX achieves this goal
by being a distributed system consisting of very simple nodes. We show that even in
the typical mode of operation without faults, TRIX performs significantly better than a
regular wire or clock tree: Statistical evaluation of our simulated experiments show that
we achieve a skew with standard deviation of O(log log H), where H is the height of the
TRIX grid.
The distance-r generalization of classic graph problems can give us insights on how
distance affects hardness of a problem. For the distance-r dominating set problem, we
present both an algorithmic upper and unconditional lower bound for any graph class
with certain high-girth and sparseness criteria. In particular, our algorithm achieves a
O(r · f(r))-approximation in time O(r), where f is the expansion function, which correlates
with density. For constant r, this implies a constant approximation factor, in constant
time. We also show that no algorithm can achieve a (2r + 1 − δ)-approximation for any
δ > 0 in time O(r), not even on the class of cycles of girth at least 5r. Furthermore, we
extend the algorithm to related graph cover problems and even to a different execution
model.
Furthermore, we investigate the problem of packet forwarding, which addresses the
question of how and when best to forward packets in a distributed system. These packets
are injected by an adversary. We build on the existing algorithm OED to handle more
than a single destination. In particular, we show that buffers of size O(log n) are sufficient
for this algorithm, in contrast to O(n) for the naive approach.

We propose an algorithm for robust recovery of the spherical harmonic
expansion of functions defined on the d-dimensional unit sphere
$\mathbb{S}^{d-1}$ using a near-optimal number of function evaluations. We show
that for any $f \in L^2(\mathbb{S}^{d-1})$, the number of evaluations of $f$
needed to recover its degree-$q$ spherical harmonic expansion equals the
dimension of the space of spherical harmonics of degree at most $q$ up to a
logarithmic factor. Moreover, we develop a simple yet efficient algorithm to
recover degree-$q$ expansion of $f$ by only evaluating the function on
uniformly sampled points on $\mathbb{S}^{d-1}$. Our algorithm is based on the
connections between spherical harmonics and Gegenbauer polynomials and leverage
score sampling methods. Unlike the prior results on fast spherical harmonic
transform, our proposed algorithm works efficiently using a nearly optimal
number of samples in any dimension d. We further illustrate the empirical
performance of our algorithm on numerical examples.

We consider the problem of maximizing the Nash social welfare when allocating
a set $\mathcal{G}$ of indivisible goods to a set $\mathcal{N}$ of agents. We
study instances, in which all agents have 2-value additive valuations: The
value of every agent $i \in \mathcal{N}$ for every good $j \in \mathcal{G}$ is
$v_{ij} \in \{p,q\}$, for $p,q \in \mathbb{N}$, $p \le q$. Maybe surprisingly,
we design an algorithm to compute an optimal allocation in polynomial time if
$p$ divides $q$, i.e., when $p=1$ and $q \in \mathbb{N}$ after appropriate
scaling. The problem is \classNP-hard whenever $p$ and $q$ are coprime and $p
\ge 3$.
In terms of approximation, we present positive and negative results for
general $p$ and $q$. We show that our algorithm obtains an approximation ratio
of at most 1.0345. Moreover, we prove that the problem is \classAPX-hard, with
a lower bound of $1.000015$ achieved at $p/q = 4/5$.

We study the problem of allocating a set of indivisible goods among agents
with 2-value additive valuations. Our goal is to find an allocation with
maximum Nash social welfare, i.e., the geometric mean of the valuations of the
agents. We give a polynomial-time algorithm to find a Nash social welfare
maximizing allocation when the valuation functions are integrally 2-valued,
i.e., each agent has a value either $1$ or $p$ for each good, for some positive
integer $p$. We then extend our algorithm to find a better approximation factor
for general 2-value instances.

The approximate uniform sampling of graphs with a given degree sequence is a
well-known, extensively studied problem in theoretical computer science and has
significant applications, e.g., in the analysis of social networks. In this
work we study an extension of the problem, where degree intervals are specified
rather than a single degree sequence. We are interested in sampling and
counting graphs whose degree sequences satisfy the degree interval constraints.
A natural scenario where this problem arises is in hypothesis testing on social
networks that are only partially observed.
In this work, we provide the first fully polynomial almost uniform sampler
(FPAUS) as well as the first fully polynomial randomized approximation scheme
(FPRAS) for sampling and counting, respectively, graphs with near-regular
degree intervals, in which every node $i$ has a degree from an interval not too
far away from a given $d \in \N$. In order to design our FPAUS, we rely on
various state-of-the-art tools from Markov chain theory and combinatorics. In
particular, we provide the first non-trivial algorithmic application of a
breakthrough result of Liebenau and Wormald (2017) regarding an asymptotic
formula for the number of graphs with a given near-regular degree sequence.
Furthermore, we also make use of the recent breakthrough of Anari et al. (2019)
on sampling a base of a matroid under a strongly log-concave probability
distribution.
As a more direct approach, we also study a natural Markov chain recently
introduced by Rechner, Strowick and M\"uller-Hannemann (2018), based on three
simple local operations: Switches, hinge flips, and additions/deletions of a
single edge. We obtain the first theoretical results for this Markov chain by
showing it is rapidly mixing for the case of near-regular degree intervals of
size at most one.

In this work we refine the analysis of the distributed Laplacian solver
recently established by Forster, Goranci, Liu, Peng, Sun, and Ye (FOCS '21),
via the Ghaffari-Haeupler framework (SODA '16) of low-congestion shortcuts.
Specifically, if $\epsilon > 0$ represents the error of the solver, we derive
two main results. First, for any $n$-node graph $G$ with hop-diameter $D$ and
treewidth bounded by $k$, we show the existence of a Laplacian solver with
round complexity $O(n^{o(1)}kD \log(1/\epsilon))$ in the CONGEST model. For
graphs with bounded treewidth this circumvents the notorious $\Omega(\sqrt{n})$
lower bound for "global" problems in general graphs. Moreover, following a
recent line of work in distributed algorithms, we consider a hybrid
communication model which enhances CONGEST with very limited global power in
the form of the recently introduced node-capacitated clique. In this model, we
show the existence of a Laplacian solver with round complexity $O(n^{o(1)}
\log(1/\epsilon))$. The unifying thread of these results is an application of
accelerated distributed algorithms for a congested variant of the standard
part-wise aggregation problem that we introduce. This primitive constitutes the
primary building block for simulating "local" operations on low-congestion
minors, and we believe that this framework could be more generally applicable.

We consider the online search problem in which a server starting at the
origin of a $d$-dimensional Euclidean space has to find an arbitrary
hyperplane. The best-possible competitive ratio and the length of the shortest
curve from which each point on the $d$-dimensional unit sphere can be seen are
within a constant factor of each other. We show that this length is in
$\Omega(d)\cap O(d^{3/2})$.

The Subgraph Isomorphism problem is of considerable importance in computer
science. We examine the problem when the pattern graph H is of bounded
treewidth, as occurs in a variety of applications. This problem has a
well-known algorithm via color-coding that runs in time $O(n^{tw(H)+1})$ [Alon,
Yuster, Zwick'95], where $n$ is the number of vertices of the host graph $G$.
While there are pattern graphs known for which Subgraph Isomorphism can be
solved in an improved running time of $O(n^{tw(H)+1-\varepsilon})$ or even
faster (e.g. for $k$-cliques), it is not known whether such improvements are
possible for all patterns. The only known lower bound rules out time
$n^{o(tw(H) / \log(tw(H)))}$ for any class of patterns of unbounded treewidth
assuming the Exponential Time Hypothesis [Marx'07].
In this paper, we demonstrate the existence of maximally hard pattern graphs
$H$ that require time $n^{tw(H)+1-o(1)}$. Specifically, under the Strong
Exponential Time Hypothesis (SETH), a standard assumption from fine-grained
complexity theory, we prove the following asymptotic statement for large
treewidth $t$: For any $\varepsilon > 0$ there exists $t \ge 3$ and a pattern
graph $H$ of treewidth $t$ such that Subgraph Isomorphism on pattern $H$ has no
algorithm running in time $O(n^{t+1-\varepsilon})$.
Under the more recent 3-uniform Hyperclique hypothesis, we even obtain tight
lower bounds for each specific treewidth $t \ge 3$: For any $t \ge 3$ there
exists a pattern graph $H$ of treewidth $t$ such that for any $\varepsilon>0$
Subgraph Isomorphism on pattern $H$ has no algorithm running in time
$O(n^{t+1-\varepsilon})$.
In addition to these main results, we explore (1) colored and uncolored
problem variants (and why they are equivalent for most cases), (2) Subgraph
Isomorphism for $tw < 3$, (3) Subgraph Isomorphism parameterized by pathwidth,
and (4) a weighted problem variant.

Fine-grained complexity theory is the area of theoretical computer science
that proves conditional lower bounds based on the Strong Exponential Time
Hypothesis and similar conjectures. This area has been thriving in the last
decade, leading to conditionally best-possible algorithms for a wide variety of
problems on graphs, strings, numbers etc. This article is an introduction to
fine-grained lower bounds in computational geometry, with a focus on lower
bounds for polynomial-time problems based on the Orthogonal Vectors Hypothesis.
Specifically, we discuss conditional lower bounds for nearest neighbor search
under the Euclidean distance and Fr\'echet distance.

Computing the similarity of two point sets is a ubiquitous task in medical
imaging, geometric shape comparison, trajectory analysis, and many more
settings. Arguably the most basic distance measure for this task is the
Hausdorff distance, which assigns to each point from one set the closest point
in the other set and then evaluates the maximum distance of any assigned pair.
A drawback is that this distance measure is not translational invariant, that
is, comparing two objects just according to their shape while disregarding
their position in space is impossible.
Fortunately, there is a canonical translational invariant version, the
Hausdorff distance under translation, which minimizes the Hausdorff distance
over all translations of one of the point sets. For point sets of size $n$ and
$m$, the Hausdorff distance under translation can be computed in time $\tilde
O(nm)$ for the $L_1$ and $L_\infty$ norm [Chew, Kedem SWAT'92] and $\tilde O(nm
(n+m))$ for the $L_2$ norm [Huttenlocher, Kedem, Sharir DCG'93].
As these bounds have not been improved for over 25 years, in this paper we
approach the Hausdorff distance under translation from the perspective of
fine-grained complexity theory. We show (i) a matching lower bound of
$(nm)^{1-o(1)}$ for $L_1$ and $L_\infty$ assuming the Orthogonal Vectors
Hypothesis and (ii) a matching lower bound of $n^{2-o(1)}$ for $L_2$ in the
imbalanced case of $m = O(1)$ assuming the 3SUM Hypothesis.

We consider the problem of computing the Boolean convolution (with
wraparound) of $n$~vectors of dimension $m$, or, equivalently, the problem of
computing the sumset $A_1+A_2+\ldots+A_n$ for $A_1,\ldots,A_n \subseteq
\mathbb{Z}_m$. Boolean convolution formalizes the frequent task of combining
two subproblems, where the whole problem has a solution of size $k$ if for some
$i$ the first subproblem has a solution of size~$i$ and the second subproblem
has a solution of size $k-i$. Our problem formalizes a natural generalization,
namely combining solutions of $n$ subproblems subject to a modular constraint.
This simultaneously generalises Modular Subset Sum and Boolean Convolution
(Sumset Computation). Although nearly optimal algorithms are known for special
cases of this problem, not even tiny improvements are known for the general
case.
We almost resolve the computational complexity of this problem, shaving
essentially a factor of $n$ from the running time of previous algorithms.
Specifically, we present a \emph{deterministic} algorithm running in
\emph{almost} linear time with respect to the input plus output size $k$. We
also present a \emph{Las Vegas} algorithm running in \emph{nearly} linear
expected time with respect to the input plus output size $k$. Previously, no
deterministic or randomized $o(nk)$ algorithm was known.
At the heart of our approach lies a careful usage of Kneser's theorem from
Additive Combinatorics, and a new deterministic almost linear output-sensitive
algorithm for non-negative sparse convolution. In total, our work builds a
solid toolbox that could be of independent interest.

We study the $c$-approximate near neighbor problem under the continuous
Fr\'echet distance: Given a set of $n$ polygonal curves with $m$ vertices, a
radius $\delta > 0$, and a parameter $k \leq m$, we want to preprocess the
curves into a data structure that, given a query curve $q$ with $k$ vertices,
either returns an input curve with Fr\'echet distance at most $c\cdot \delta$
to $q$, or returns that there exists no input curve with Fr\'echet distance at
most $\delta$ to $q$. We focus on the case where the input and the queries are
one-dimensional polygonal curves -- also called time series -- and we give a
comprehensive analysis for this case. We obtain new upper bounds that provide
different tradeoffs between approximation factor, preprocessing time, and query
time.
Our data structures improve upon the state of the art in several ways. We
show that for any $0 < \varepsilon \leq 1$ an approximation factor of
$(1+\varepsilon)$ can be achieved within the same asymptotic time bounds as the
previously best result for $(2+\varepsilon)$. Moreover, we show that an
approximation factor of $(2+\varepsilon)$ can be obtained by using
preprocessing time and space $O(nm)$, which is linear in the input size, and
query time in $O(\frac{1}{\varepsilon})^{k+2}$, where the previously best
result used preprocessing time in $n \cdot O(\frac{m}{\varepsilon k})^k$ and
query time in $O(1)^k$. We complement our upper bounds with matching
conditional lower bounds based on the Orthogonal Vectors Hypothesis.
Interestingly, some of our lower bounds already hold for any super-constant
value of $k$. This is achieved by proving hardness of a one-sided sparse
version of the Orthogonal Vectors problem as an intermediate problem, which we
believe to be of independent interest.

Computing the dominant Fourier coefficients of a vector is a common task in
many fields, such as signal processing, learning theory, and computational
complexity. In the Sparse Fast Fourier Transform (Sparse FFT) problem, one is
given oracle access to a $d$-dimensional vector $x$ of size $N$, and is asked
to compute the best $k$-term approximation of its Discrete Fourier Transform,
quickly and using few samples of the input vector $x$. While the sample
complexity of this problem is quite well understood, all previous approaches
either suffer from an exponential dependence of runtime on the dimension $d$ or
can only tolerate a trivial amount of noise. This is in sharp contrast with the
classical FFT algorithm of Cooley and Tukey, which is stable and completely
insensitive to the dimension of the input vector: its runtime is $O(N\log N)$
in any dimension $d$.
In this work, we introduce a new high-dimensional Sparse FFT toolkit and use
it to obtain new algorithms, both on the exact, as well as in the case of
bounded $\ell_2$ noise. This toolkit includes i) a new strategy for exploring a
pruned FFT computation tree that reduces the cost of filtering, ii) new
structural properties of adaptive aliasing filters recently introduced by
Kapralov, Velingker and Zandieh'SODA'19, and iii) a novel lazy estimation
argument, suited to reducing the cost of estimation in FFT tree-traversal
approaches. Our robust algorithm can be viewed as a highly optimized sparse,
stable extension of the Cooley-Tukey FFT algorithm.
Finally, we explain the barriers we have faced by proving a conditional
quadratic lower bound on the running time of the well-studied non-equispaced
Fourier transform problem. This resolves a natural and frequently asked
question in computational Fourier transforms. Lastly, we provide a preliminary
experimental evaluation comparing the runtime of our algorithm to FFTW and SFFT
2.0.

Computing the convolution $A\star B$ of two length-$n$ integer vectors $A,B$
is a core problem in several disciplines. It frequently comes up in algorithms
for Knapsack, $k$-SUM, All-Pairs Shortest Paths, and string pattern matching
problems. For these applications it typically suffices to compute convolutions
of nonnegative vectors. This problem can be classically solved in time $O(n\log
n)$ using the Fast Fourier Transform.
However, often the involved vectors are sparse and hence one could hope for
output-sensitive algorithms to compute nonnegative convolutions. This question
was raised by Muthukrishnan and solved by Cole and Hariharan (STOC '02) by a
randomized algorithm running in near-linear time in the (unknown) output-size
$t$. Chan and Lewenstein (STOC '15) presented a deterministic algorithm with a
$2^{O(\sqrt{\log t\cdot\log\log n})}$ overhead in running time and the
additional assumption that a small superset of the output is given; this
assumption was later removed by Bringmann and Nakos (ICALP '21).
In this paper we present the first deterministic near-linear-time algorithm
for computing sparse nonnegative convolutions. This immediately gives improved
deterministic algorithms for the state-of-the-art of output-sensitive Subset
Sum, block-mass pattern matching, $N$-fold Boolean convolution, and others,
matching up to log-factors the fastest known randomized algorithms for these
problems. Our algorithm is a blend of algebraic and combinatorial ideas and
techniques.
Additionally, we provide two fast Las Vegas algorithms for computing sparse
nonnegative convolutions. In particular, we present a simple $O(t\log^2t)$ time
algorithm, which is an accessible alternative to Cole and Hariharan's
algorithm. We further refine this new algorithm to run in Las Vegas time
$O(t\log t\cdot\log\log t)$, matching the running time of the dense case apart
from the $\log\log t$ factor.

In the classical Subset Sum problem we are given a set $X$ and a target $t$,
and the task is to decide whether there exists a subset of $X$ which sums to
$t$. A recent line of research has resulted in $\tilde{O}(t)$-time algorithms,
which are (near-)optimal under popular complexity-theoretic assumptions. On the
other hand, the standard dynamic programming algorithm runs in time $O(n \cdot
|\mathcal{S}(X,t)|)$, where $\mathcal{S}(X,t)$ is the set of all subset sums of
$X$ that are smaller than $t$. Furthermore, all known pseudopolynomial
algorithms actually solve a stronger task, since they actually compute the
whole set $\mathcal{S}(X,t)$.
As the aforementioned two running times are incomparable, in this paper we
ask whether one can achieve the best of both worlds: running time
$\tilde{O}(|\mathcal{S}(X,t)|)$. In particular, we ask whether
$\mathcal{S}(X,t)$ can be computed in near-linear time in the output-size.
Using a diverse toolkit containing techniques such as color coding, sparse
recovery, and sumset estimates, we make considerable progress towards this
question and design an algorithm running in time
$\tilde{O}(|\mathcal{S}(X,t)|^{4/3})$.
Central to our approach is the study of top-$k$-convolution, a natural
problem of independent interest: given sparse polynomials with non-negative
coefficients, compute the lowest $k$ non-zero monomials of their product. We
design an algorithm running in time $\tilde{O}(k^{4/3})$, by a combination of
sparse convolution and sumset estimates considered in Additive Combinatorics.
Moreover, we provide evidence that going beyond some of the barriers we have
faced requires either an algorithmic breakthrough or possibly new techniques
from Additive Combinatorics on how to pass from information on restricted
sumsets to information on unrestricted sumsets.

We initiate the study of fine-grained completeness theorems for exact and
approximate optimization in the polynomial-time regime. Inspired by the first
completeness results for decision problems in P (Gao, Impagliazzo, Kolokolova,
Williams, TALG 2019) as well as the classic class MaxSNP and
MaxSNP-completeness for NP optimization problems (Papadimitriou, Yannakakis,
JCSS 1991), we define polynomial-time analogues MaxSP and MinSP, which contain
a number of natural optimization problems in P, including Maximum Inner
Product, general forms of nearest neighbor search and optimization variants of
the $k$-XOR problem. Specifically, we define MaxSP as the class of problems
definable as $\max_{x_1,\dots,x_k} \#\{ (y_1,\dots,y_\ell) :
\phi(x_1,\dots,x_k, y_1,\dots,y_\ell) \}$, where $\phi$ is a quantifier-free
first-order property over a given relational structure (with MinSP defined
analogously). On $m$-sized structures, we can solve each such problem in time
$O(m^{k+\ell-1})$. Our results are:
- We determine (a sparse variant of) the Maximum/Minimum Inner Product
problem as complete under *deterministic* fine-grained reductions: A strongly
subquadratic algorithm for Maximum/Minimum Inner Product would beat the
baseline running time of $O(m^{k+\ell-1})$ for *all* problems in MaxSP/MinSP by
a polynomial factor.
- This completeness transfers to approximation: Maximum/Minimum Inner Product
is also complete in the sense that a strongly subquadratic $c$-approximation
would give a $(c+\varepsilon)$-approximation for all MaxSP/MinSP problems in
time $O(m^{k+\ell-1-\delta})$, where $\varepsilon > 0$ can be chosen
arbitrarily small. Combining our completeness with~(Chen, Williams, SODA 2019),
we obtain the perhaps surprising consequence that refuting the OV Hypothesis is
*equivalent* to giving a $O(1)$-approximation for all MinSP problems in
faster-than-$O(m^{k+\ell-1})$ time.

Computing the convolution $A\star B$ of two length-$n$ vectors $A,B$ is an
ubiquitous computational primitive. Applications range from string problems to
Knapsack-type problems, and from 3SUM to All-Pairs Shortest Paths. These
applications often come in the form of nonnegative convolution, where the
entries of $A,B$ are nonnegative integers. The classical algorithm to compute
$A\star B$ uses the Fast Fourier Transform and runs in time $O(n\log n)$.
However, often $A$ and $B$ satisfy sparsity conditions, and hence one could
hope for significant improvements. The ideal goal is an $O(k\log k)$-time
algorithm, where $k$ is the number of non-zero elements in the output, i.e.,
the size of the support of $A\star B$. This problem is referred to as sparse
nonnegative convolution, and has received considerable attention in the
literature; the fastest algorithms to date run in time $O(k\log^2 n)$.
The main result of this paper is the first $O(k\log k)$-time algorithm for
sparse nonnegative convolution. Our algorithm is randomized and assumes that
the length $n$ and the largest entry of $A$ and $B$ are subexponential in $k$.
Surprisingly, we can phrase our algorithm as a reduction from the sparse case
to the dense case of nonnegative convolution, showing that, under some mild
assumptions, sparse nonnegative convolution is equivalent to dense nonnegative
convolution for constant-error randomized algorithms. Specifically, if $D(n)$
is the time to convolve two nonnegative length-$n$ vectors with success
probability $2/3$, and $S(k)$ is the time to convolve two nonnegative vectors
with output size $k$ with success probability $2/3$, then
$S(k)=O(D(k)+k(\log\log k)^2)$.
Our approach uses a variety of new techniques in combination with some old
machinery from linear sketching and structured linear algebra, as well as new
insights on linear hashing, the most classical hash function.

We consider the classic problem of computing the Longest Common Subsequence
(LCS) of two strings of length $n$. While a simple quadratic algorithm has been
known for the problem for more than 40 years, no faster algorithm has been
found despite an extensive effort. The lack of progress on the problem has
recently been explained by Abboud, Backurs, and Vassilevska Williams [FOCS'15]
and Bringmann and K\"unnemann [FOCS'15] who proved that there is no
subquadratic algorithm unless the Strong Exponential Time Hypothesis fails.
This has led the community to look for subquadratic approximation algorithms
for the problem.
Yet, unlike the edit distance problem for which a constant-factor
approximation in almost-linear time is known, very little progress has been
made on LCS, making it a notoriously difficult problem also in the realm of
approximation. For the general setting, only a naive
$O(n^{\varepsilon/2})$-approximation algorithm with running time
$\tilde{O}(n^{2-\varepsilon})$ has been known, for any constant $0 <
\varepsilon \le 1$. Recently, a breakthrough result by Hajiaghayi, Seddighin,
Seddighin, and Sun [SODA'19] provided a linear-time algorithm that yields a
$O(n^{0.497956})$-approximation in expectation; improving upon the naive
$O(\sqrt{n})$-approximation for the first time.
In this paper, we provide an algorithm that in time $O(n^{2-\varepsilon})$
computes an $\tilde{O}(n^{2\varepsilon/5})$-approximation with high
probability, for any $0 < \varepsilon \le 1$. Our result (1) gives an
$\tilde{O}(n^{0.4})$-approximation in linear time, improving upon the bound of
Hajiaghayi, Seddighin, Seddighin, and Sun, (2) provides an algorithm whose
approximation scales with any subquadratic running time $O(n^{2-\varepsilon})$,
improving upon the naive bound of $O(n^{\varepsilon/2})$ for any $\varepsilon$,
and (3) instead of only in expectation, succeeds with high probability.