Publications - The Year Before Last

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.

The fractional knapsack problem is one of the classical problems in
combinatorial optimization, which is well understood in the offline setting.
However, the corresponding online setting has been handled only briefly in the
theoretical computer science literature so far, although it appears in several
applications. Even the previously best known guarantee for the competitive
ratio was worse than the best known for the integral problem in the popular
random order model. We show that there is an algorithm for the online
fractional knapsack problem that admits a competitive ratio of 4.39. Our result
significantly improves over the previously best known competitive ratio of 9.37
and surpasses the current best 6.65-competitive algorithm for the integral
case. Moreover, our algorithm is deterministic in contrast to the randomized
algorithms achieving the results mentioned above.

We give tight bounds on the relation between the primal and dual of various
combinatorial dimensions, such as the pseudo-dimension and fat-shattering
dimension, for multi-valued function classes. These dimensional notions play an
important role in the area of learning theory. We first review some (folklore)
results that bound the dual dimension of a function class in terms of its
primal, and after that give (almost) matching lower bounds. In particular, we
give an appropriate generalization to multi-valued function classes of a
well-known bound due to Assouad (1983), that relates the primal and dual
VC-dimension of a binary function class.

Logit dynamics is a form of randomized game dynamics where players have a
bias towards strategic deviations that give a higher improvement in cost. It is
used extensively in practice. In congestion (or potential) games, the dynamics
converges to the so-called Gibbs distribution over the set of all strategy
profiles, when interpreted as a Markov chain. In general, logit dynamics might
converge slowly to the Gibbs distribution, but beyond that, not much is known
about their algorithmic aspects, nor that of the Gibbs distribution. In this
work, we are interested in the following two questions for congestion games: i)
Is there an efficient algorithm for sampling from the Gibbs distribution? ii)
If yes, do there also exist natural randomized dynamics that converges quickly
to the Gibbs distribution?
We first study these questions in extension parallel congestion games, a
well-studied special case of symmetric network congestion games. As our main
result, we show that there is a simple variation on the logit dynamics (in
which we in addition are allowed to randomly interchange the strategies of two
players) that converges quickly to the Gibbs distribution in such games. This
answers both questions above affirmatively. We also address the first question
for the class of so-called capacitated $k$-uniform congestion games.
To prove our results, we rely on the recent breakthrough work of Anari, Liu,
Oveis-Gharan and Vinzant (2019) concerning the approximate sampling of the base
of a matroid according to strongly log-concave probability distribution.

We revisit the classical problem of determining the largest copy of a simple
polygon $P$ that can be placed into a simple polygon $Q$. Despite significant
effort, known algorithms require high polynomial running times. (Barequet and
Har-Peled, 2001) give a lower bound of $n^{2-o(1)}$ under the 3SUM conjecture
when $P$ and $Q$ are (convex) polygons with $\Theta(n)$ vertices each. This
leaves open whether we can establish (1) hardness beyond quadratic time and (2)
any superlinear bound for constant-sized $P$ or $Q$.
In this paper, we affirmatively answer these questions under the $k$SUM
conjecture, proving natural hardness results that increase with each degree of
freedom (scaling, $x$-translation, $y$-translation, rotation): (1) Finding the
largest copy of $P$ that can be $x$-translated into $Q$ requires time
$n^{2-o(1)}$ under the 3SUM conjecture. (2) Finding the largest copy of $P$
that can be arbitrarily translated into $Q$ requires time $n^{2-o(1)}$ under
the 4SUM conjecture. (3) The above lower bounds are almost tight when one of
the polygons is of constant size: we obtain an $\tilde O((pq)^{2.5})$-time
algorithm for orthogonal polygons $P,Q$ with $p$ and $q$ vertices,
respectively. (4) Finding the largest copy of $P$ that can be arbitrarily
rotated and translated into $Q$ requires time $n^{3-o(1)}$ under the 5SUM
conjecture.
We are not aware of any other such natural $($degree of freedom $+ 1)$-SUM
hardness for a geometric optimization problem.

We study the problem of fairly allocating a set of indivisible goods among
$n$ agents with additive valuations. Envy-freeness up to any good (EFX) is
arguably the most compelling fairness notion in this context. However, the
existence of EFX allocations has not been settled and is one of the most
important problems in fair division. Towards resolving this problem, many
impressive results show the existence of its relaxations, e.g., the existence
of $0.618$-EFX allocations, and the existence of EFX at most $n-1$ unallocated
goods. The latter result was recently improved for three agents, in which the
two unallocated goods are allocated through an involved procedure. Reducing the
number of unallocated goods for arbitrary number of agents is a systematic way
to settle the big question. In this paper, we develop a new approach, and show
that for every $\varepsilon \in (0,1/2]$, there always exists a
$(1-\varepsilon)$-EFX allocation with sublinear number of unallocated goods and
high Nash welfare.
For this, we reduce the EFX problem to a novel problem in extremal graph
theory. We introduce the notion of rainbow cycle number $R(\cdot)$. For all $d
\in \mathbb{N}$, $R(d)$ is the largest $k$ such that there exists a $k$-partite
digraph $G =(\cup_{i \in [k]} V_i, E)$, in which
1) each part has at most $d$ vertices, i.e., $\lvert V_i \rvert \leq d$ for
all $i \in [k]$,
2) for any two parts $V_i$ and $V_j$, each vertex in $V_i$ has an incoming
edge from some vertex in $V_j$ and vice-versa, and
3) there exists no cycle in $G$ that contains at most one vertex from each
part.
We show that any upper bound on $R(d)$ directly translates to a sublinear
bound on the number of unallocated goods. We establish a polynomial upper bound
on $R(d)$, yielding our main result. Furthermore, our approach is constructive,
which also gives a polynomial-time algorithm for finding such an allocation.