# On Complexity of 1-Center in Various Metrics

Amir Abboud111Supported by an Alon scholarship and a research grant from the
Center for New Scientists at the Weizmann Institute of Science.
Weizmann Institute of Science
<EMAIL_ADDRESS>MohammadHossein Bateni
Google Research
<EMAIL_ADDRESS>Vincent Cohen-Addad
Google Research
<EMAIL_ADDRESS>Karthik C. S.222This work was supported by Subhash Khot’s
Simons Investigator Award and by a grant from the Simons Foundation, Grant
Number 825876, Awardee Thu D. Nguyen.
Rutgers University
<EMAIL_ADDRESS>Saeed Seddighin333Supported by a Google research gift.
Toyota Technological Institute at Chicago
<EMAIL_ADDRESS>
###### Abstract

We consider the classic 1-center problem: Given a set $P$ of $n$ points in a
metric space find the point in $P$ that minimizes the maximum distance to the
other points of $P$. We study the complexity of this problem in
$d$-dimensional $\ell_{p}$-metrics and in edit and Ulam metrics over strings
of length $d$. Our results for the 1-center problem may be classified based on
$d$ as follows.

  * •

Small $d$. We provide the first linear-time algorithm for 1-center problem in
fixed-dimensional $\ell_{1}$ metrics. On the other hand, assuming the hitting
set conjecture ($\mathsf{HSC}$), we show that when $d=\omega(\log n)$, no
subquadratic algorithm can solve 1-center problem in any of the
$\ell_{p}$-metrics, or in edit or Ulam metrics.

  * •

Large $d$. When $d=\Omega(n)$, we extend our conditional lower bound to rule
out sub _quartic_ algorithms for 1-center problem in edit metric (assuming
Quantified SETH). On the other hand, we give a $(1+\epsilon)$-approximation
for 1-center in Ulam metric with running time
$\widetilde{O_{\varepsilon}}(nd+n^{2}\sqrt{d})$.

We also strengthen some of the above lower bounds by allowing approximations
or by reducing the dimension $d$, but only against a weaker class of
algorithms which list all requisite solutions. Moreover, we extend one of our
hardness results to rule out subquartic algorithms for the well-studied
1-median problem in the edit metric, where given a set of $n$ strings each of
length $n$, the goal is to find a string in the set that minimizes the sum of
the edit distances to the rest of the strings in the set.

##  1 Introduction

Given a set of points $P$ in a metric space, finding the point that “best”
represents $P$ is a fundamental question in both discrete and continuous
optimization. Motivated by applications ranging from machine learning to
computational biology, this question has naturally received a large amount of
attention through the years.

The objective can be phrased in various ways: In the median problem, the goal
is to find the point $p$ that minimizes the sum of the distances to the points
in $P$; in the mean problem, it is the point that minimizes the sum of
distances squared; while in the center problem, it is the point $p$ that
minimizes the maximum distance from a point of $P$ to $p$. When the metric is
the $\ell_{2}$ (Euclidean) metric, the question of computing the geometric
median dates back to the 17th century, when Torricelli was looking for a
solution for the case $|P|=3$, and to whom Fermat described an explicit
solution. More recently, the question of computing the center has also become
central in applications arising, e.g., in machine learning [CHW10], to compute
the minimum enclosing ball of a set of points, or in computational biology, to
find a good representative of a set of strings (representing molecular
sequences) (e.g., [NR05]). This fundamental computational geometry problem
which has applications to various domains, is the problem we consider in this
paper.

Formally, in the (often referred to as _discrete_) 1-center problem, the input
is a set of points $P$ in a metric space, and the goal is to find a point of
$P$ that minimizes the maximum distance to the points in $P$. When doing data
summarization or compression, the discrete version often makes more sense:
Given a set of, say $n$ strings, taking the most representative string among
the input strings, or at least in the set of grammatically (or semantically)
meaningful strings is much more insightful than taking an arbitrary string as
representative. This also applies more globally, outputting a data element
that has been observed provides a better summary than a data element that has
been forged by the algorithm and that may be unlikely to exist in the real-
world. From a computational complexity standpoint, this problem can be easily
solved in time $O(|P|^{2}f(d))$ where $f(d)$ is the time required to compute
the distance of two points. This can be done by enumerating all possible
choices for the center; and for each choice computing the distance from each
point in $P$; then outputting the best center. However, is this naïve
algorithm the best we can do?

The computational geometry community has done extensive work on the above
question since the 80s. For metrics such as $\ell_{1}$ or $\ell_{2}$,
computing the center has received a large deal of attention. When the
dimension is assumed to be a constant, there exist _barely subquadratic_
algorithms for the $\ell_{2}$ metric, while there exists near-linear time
algorithms for the $\ell_{1}$ case (for a discussion on this we refer the
reader to [Wil18a]). For the case of string metrics, such as Ulam or Edit
distance metrics, nothing better than the $O(|P|^{2}f(d))$ (where $d$ is the
string length) “brute-force” algorithm is known.

Understanding how fast the 1-center problem can be solved in these different
metrics is not only interesting from a computational complexity point of view,
but also from the perspective of an improved understanding of the geometry of
these metrics. For example, is the geometry of the $\ell_{1}$ metric “more
amenable” for designing algorithms than the $\ell_{2}$ one? Is the Edit
distance metric hard for such problems? We also believe that understanding the
geometry of the Ulam and Edit distance metrics, which one may interpret as
generalization of the Hamming metric, is not only a very basic computational
geometry question, but also would likely lead to better algorithms for these
widely-studied problems. We thus ask:

_How fast can the 1-center problem be solved or approximated in
$\ell_{p}$-metrics and stringology metrics such as Ulam or Edit distance?_

###  1.1 Our Results

In this paper, we take a step towards answering the above question by
providing lower and upper bounds on solving the 1-center problem in
$\ell_{p}$, Ulam, and Edit distance metrics.

Our first result is to give the first linear time algorithm for the 1-center
problem in $\ell_{1}$ metrics of fixed dimension. This generalizes the linear
time algorithm of Schuierer [Sch94] for 2-dimensional inputs to any low-
dimensional inputs.

######  Theorem 1.1.

Given $n$ points $p_{1},p_{2},\ldots,p_{n}$ in dimension $d$, we can find
their 1-center in time $O(2^{d}nd)$ under $\ell_{1}$ metric.

As a byproduct, Theorem 1.1 immediately leads to the first linear-time
algorithm for computing the diameter (i.e., the farthest pair among a set of
given points) in $\ell_{1}$ metric of low dimension. This improves upon the
nearly 40-year old near-linear time algorithms, with running time $O((d\log
n)^{O(d)}n)$, of Yao [Yao82] and Gabow et al. [GBT84], and so generalizes the
result for the 2-dimensional case of Schuierer [Sch94].

######  Corollary 1.2.

Given $n$ points $p_{1},p_{2},\ldots,p_{n}$ in dimension $d$, we can find the
farthest pair in time $O(2^{d}nd)$ under $\ell_{1}$ metric.

We note that the results in [Wil18a, Che20] show that there is no such
algorithm for farthest pair in $\ell_{2}$ metric assuming the strong
exponential time hypothesis (SETH). Next, assuming the Hitting Set Conjecture
($\mathsf{HSC}$), we complement Theorem 1.1 by providing a strong conditional
lower bound for 1-center problem, in a pleathora of metrics, albeit in higher
dimensions.

######  Theorem 1.3.

(see Theorem 4.3, Corollary 4.6, and Corollary 4.8 for formal statement)
Assuming $\mathsf{HSC}$, no algorithm running in time $n^{1.99}$ can given as
input a set of points/strings $P$ of dimension/length $d$ solve the discrete
1-center problem in Edit/Ulam/$\ell_{p}$ metric, where $|P|=n$,
$d=\widetilde{\Omega}(\log n)$, and $p\in\mathbb{R}_{\geq 1}\cup\\{0\\}$.

Moreover, by assuming a stronger complexity theoretic assumption we can
strengthen this lower bound in the case when $d=\text{poly}(n)$ for the Edit
metric. For the sake of presentation, we state our result below when $d=n$.

######  Theorem 1.4.

(see Theorem 4.9) Assuming Quantified SETH, no algorithm running in time
$n^{3.99}$ can given as input a set of $n$ strings of length $d$ each, solve
the discrete 1-center problem in Edit metric.

Note that we cannot expect such lower bounds for 1-center problem in
$\ell_{p}$-metrics when $d=n$, as one can compute all pairwise distances
within a point-set in subcubic time using fast matrix multiplication.

Next, we complement the lower bounds by the following subcubic approximation
scheme for 1-center in Ulam metric.

######  Theorem 1.5.

There exists a $1+\epsilon$ approximation algorithm for 1-center under Ulam
metric that runs in time $\widetilde{O}_{\epsilon}(nd+n^{2}\sqrt{d})$.

It is worth emphasizing here that for the (discrete) 1-center problem in any
metric space, an arbitrary point in the input is a 2-approximate solution.
Also note that exact $1$-center in Ulam metric can be solved in $O(n^{2}d)$
time. It remains an open problem to show a conditional lower bound of
$n^{2.99}$ for computing 1-center in Ulam metric for $n$ strings each of
length $n$.

Finally, we strengthen some of the lower bounds above, but against a weaker
class of algorithms, specifically, against algorithms which list all requisite
solutions. Using the ideas in [Wil18a, Che20], assuming $\mathsf{HSC}$, we
rule out subquadratic algorithms that can list all optimal solutions to
1-center problem in the Euclidean metric even for very low $d=o(\log{n})$
dimensions.

######  Theorem 1.6 (see Theorem 4.1 for formal statement).

Assuming $\mathsf{HSC}$, there is no $n^{1.99}$-time algorithm listing all
optimal solutions to 1-center problem in $7^{\log^{*}n}$ dimensions in the
Euclidean metric.

In the same spirit as above, by applying the distributed PCP framework [ARW17,
Rub18] we extend the lower bound in Theorem 1.3 against approximation
algorithms which list all approximately optimal 1-centers.

######  Theorem 1.7 (see Theorem 6.4 for formal statement).

Assuming $\mathsf{HSC}$, there is some $\delta>0$, such that no
$n^{1.99}$-time algorithm can given as input a set of points/strings $P$ of
dimension/length $d$, list all $(1+\delta)$-approximate solutions to 1-center
problem in Edit/Ulam/$\ell_{p}$ metric, where $|P|=n$,
$d=\widetilde{\Omega}(\log n)$, and $p\in\mathbb{R}_{\geq 1}\cup\\{0\\}$.

One may compute all pairwise distances in $\widetilde{O}(n^{2})$ time for the
inputs in Theorems 1.6 and 1.7, and then obtain the list of all optimal and
approximately optimal solutions efficiently. Our theorems above say that one
cannot do much better. It remains an intriguing open problem to extend the
above two conditional lower bounds but against standard decision algorithms.
We note that this involves breaking some technical barriers and in particular,
developing techniques that go beyond the dimensionality reduction techniques
of [Wil18a, Che20] and the distributed PCP framework [ARW17, Rub18]
respectively.

We close this subsection by a short discussion about the Discrete 1-median
problem in $\ell_{p}$-metrics and string metrics. For the case when $d=n$, we
can prove a result similar to Theorem 1.4 (see Remark 4.12). On the other hand
for $\ell_{p}$-metrics, one cannot prove a result similar to Theorem 1.3 for
the 1-median problem, because the 1-median problem in Hamming and
$\ell_{1}$-metrics admits a near linear time algorithm and for the Euclidean
metric, it is even unclear if the problem is in NP! (see discussion in
[GGJ76].) Also note that by subsampling coordinates, we can approximate
1-median in all $\ell_{p}$-metrics to $(1+\varepsilon)$ factor, for any
$\varepsilon>0$ in near linear time.

###  1.2 Related Work

We now review the related work on the 1-center problem, and the related
1-median problem. Both problems may be considered in the _discrete_ or
_continuous_ settings. The discrete444Sometimes called the medoid problem in
contrast to median, _generalized_ median, or _Steiner_ string. version asks
the center or median to be picked from an input set of points, while in the
continuous version, the “center” is an arbitrary element of the metric. See
[CKL21] for a discussion on these two settings.

Below, we mainly discuss 1-center problem in stringology metrics as the
literature on related work in $\ell_{p}$ metrics is too vast to survey.

##### Metrics arising in stringology

We now review results on the 1-center problem in metric spaces arising from
stringology applications. Let $\Sigma$ be an alphabet, often the binary
alphabet $\\{0,1\\}$. Consider the set of strings $\Sigma^{*}=\Sigma^{L}$ of
length $L$, with a metric distance
$D:\Sigma^{*}\times\Sigma^{*}\mapsto\mathbb{R}$. Researchers have mainly
considered the following metrics defined over this space:

  * •

Edit distance (ED or Levenshtein distance): The minimum number of single-
character insertions, deletions, and substitutions required to change one
string to the other.

  * •

Hamming distance or $\ell_{1}$ over binary alphabets (HD): A special case of
edit distance, where only substitutions are allowed.

  * •

Ulam distance (UD): Same as edit distance with the restriction that the input
strings may not contain any character more than once.

For most of the above metrics, one need to incorporate into the running times
obtained for simpler metric such as $\ell_{1}$ or $\ell_{2}$ the time it takes
to compute the exact or approximate distance between any two points of the
space. Naumovitz et al. [NSS17b] show how to approximate UD within factor
$1+\varepsilon$ in time $\widetilde{O}(d/\eta+\sqrt{d})$ if the distance is
$\eta$. This result is tight up to log factors.

Turning back to the 1-center and 1-median problem, note the _discrete_
versions can be solved exactly via $O(n^{2})$ distance computations, giving
trivial $\widetilde{O}(n^{2}d)$-time algorithms for the case of UD. In Section
5, we show that this can be improved to $\widetilde{O}(n^{2}\sqrt{d})$ for
$1+\varepsilon$ approximation if we combine two algorithms [MS20, NSS17b] for
computations of UD. Note that a 2-approximation is trivial, as we can output
any string as the hub in the case of 1-center or a random string in the case
of 1-median.

Recently [CDK21] made progress on obtaining better approximation algorithms
for the continuous 1-Median problem in UD, where the median can be picked from
anywhere in space, by presenting the first polynomial-time constant-factor
approximation algorithm with approximation guarantee smaller than 2 as well as
an exact algorithm for the case where the input contains _three_ strings. They
observe that if the average distance to median is $\Omega(d)$, picking the
best string as the median already gives an approximation better than two. Now
the problem is reduced to the above case if the total cost is mostly due to a
small subset of characters. Otherwise, they argue that one can deduce the
relative ordering of a good portion of the optimal median by looking at pairs
of characters whose relative order is consistent in _most_ input strings.

Note that in the continuous case, for constant $d$ or constant $n$, the median
and center problems are both solvable in polynomial time for string problems.
De la Higuera and Casacuberta [dlHC00] prove that median and center are both
NP-hard. Nicolas and Rivals [NR03] lift the restrictions and show that median
and center are both NP-hard and $W[1]$-hard (when parameterized by $n$, the
number of strings), even for binary alphabets. Prior to these works, NP-
hardness of median was only known for ED when the substitutions have specific
costs for each pair of characters [SP03]. Li et al. [LMW02a, LMW02b] give a
PTAS for the HD 1-center problem,555This is the closest string problem. They
also give a PTAS for the closest substring problem, which assumes that the
cost of deletions from the input strings ($\infty$ for HD) is zero. augmenting
the LP-based PTAS for super-logarithmic $d$ [BLPR97]. The HD 1-center problem
is known to be NP-hard [FL97, LLM+03].666Note that median is solvable exactly
for HD. Previously the best polynomial-time approximation ratio was
$\frac{4}{3}+\varepsilon$ in general [LLM+03, GJL99], with an exact algorithm
known for constant $d$ (optimal value) [SBG+97].

###  1.3 Organization of the Paper

In Section 2, we provide the formal definition of 1-center problem and the
various hypotheses used in the paper. In Section 3, we provide a linear time
algorithm for 1-center in fixed dimensional $\ell_{1}$-metric. In Section 4,
we provide conditional lower bounds against exact algorithms that compute
1-center when $d=\omega(\log n)$. Next, in Section 5, we provide a subcubic
approximation algorithm for 1-center in Ulam metric when $d=n$. Finally, in
Section 6, we provide some hardness of approximation results (Theorem 1.7).

##  2 Preliminaries

######  Definition 2.1 (Discrete 1-center).

Let $(X,\Delta)$ be a metric space. Given a set of points $P\subseteq X$ in
the metric space, find $x$ in $P$ which minimizes the maximum distance to
every other point.

Perhaps the most popular assumption for proving conditional lower bounds for
polynomial time problems is the Orthogonal Vectors Hypothesis (OVH) that is
implied by the Strong Exponential Time Hypothesis (SETH). Unfortunately, the
logical structure of these problems makes reductions to our 1-center problems
difficult. This was observed already by Abboud, Vassilevska Williams, and Wang
[AWW16] in the context of 1-center in _graphs_ (known as the Graph Radius
problem) and has lead them to introduce the hitting set conjecture
($\mathsf{HSC}$): a stronger variant of OVH that facilitates reductions to
problems with different structure. A formal barrier for establishing
$\mathsf{HSC}$ (and similarly also any hardness results for 1-center) under
SETH was presented by Carmosino et al. [CGI+16].

######  Definition 2.2 ($\mathsf{HSC}$).

For every $\varepsilon>0$ there exists $c>1$ such that no algorithm running in
time $n^{2-\varepsilon}$ can, given as input two collections of $n$-many
subsets $\mathcal{A}$ and $\mathcal{B}$ of the universe $U:=[c\log n]$,
determine if there exists $S$ in $\mathcal{A}$ which has non-empty
intersection with every subset in $\mathcal{B}$.

The difference between $\mathsf{HSC}$ and OVH is in the quantifiers:
$\exists\forall$ versus $\exists\exists$. Studying the _polyline
simplification_ problem, Bringmann and Chaudhury [BC19] proposed a further
strengthening with more quantifiers. Just like OVH is implied by SETH, an
assumption about $k$-SAT, so too can $\mathsf{HSC}$ and its generalizations
with more quantifiers be based on the hardness of a quantified version of
$k$-SAT; an assumption called _Quantified-SETH_. Interestingly, the previous
papers using Quantified-SETH [BC19, ABHS20] only needed its special case where
the quantifier structure is $\forall\exists$; whereas in this paper we benefit
from a $\exists\forall\exists$ structure that has one more alternation.

The specific hardness assumption (implied by Quantified SETH) that we need is
the following; we refer to [BC19, ABHS20] for further discussion on
Quantified-SETH and to [AWW16, Wil18b] for further discussion on
$\mathsf{HSC}$ and on the need for assumptions with other quantifier
structures.

######  Definition 2.3 ($\exists\forall\exists\exists\mathsf{OVH}$).

For every $\varepsilon>0$ there exists $c>1$ such that no algorithm running in
time $n^{4-\varepsilon}$ can, given as input four collections of $n$-many
subsets $\mathcal{A},\mathcal{B},\mathcal{C},$ and $\mathcal{D}$ of the
universe $U:=[c\log n]$, determine if there exists $S_{A}$ in $\mathcal{A}$
such that for all $S_{B}$ in $\mathcal{B}$ there exist $S_{C}\in\mathcal{C}$
and $S_{D}\in\mathcal{D}$ such that the intersection $S_{A}\cap S_{B}\cap
S_{C}\cap S_{D}=\emptyset$ is empty.

##  3 1-Center for $\ell_{1}$ Metric in Low Dimension

In this section, we give an algorithm that runs in time $O(2^{d}nd)$ and
solves 1-center exactly in $\ell_{1}$-metric when the dimension is $d$ and the
number of points is $n$. Our algorithm is based on a very simple observation:
Let $v^{0},v^{1},\ldots,v^{2^{d}-1}$ be $2^{d}$ vectors of size $d$ such that
each vector $v^{i}$ is the bit representation of value $i$ in base $2$. We
define $2^{d}$ functions $f_{0},f_{1},f_{2},\ldots,f_{2^{d}-1}$ such that the
input to every function $f_{i}$ is a $d$-dimensional point $u$ and its output
is determined in the following way:

$f_{i}(u)=\sum_{1\leq j\leq d,v^{i}_{j}=1}u_{j}-\sum_{1\leq j\leq
d,v^{i}_{j}=0}u_{j}.$

It follows from the definition that for any two points $x$ and $y$ the
following conditions hold:

  * •

$\forall 0\leq i<2^{d},\ell_{1}(x,y)\geq f_{i}(x)-f_{i}(y)$.

  * •

$\exists 0\leq i<2^{d}$ such that $\ell_{1}(x,y)=f_{i}(x)-f_{i}(y)$.

where $\ell_{1}(x,y)$ is the distance of points $x$ and $y$ under $\ell_{1}$
metric. Let $p_{1},p_{2},\ldots,p_{n}$ be the input points. It follows that
for each point $x$ on the plane, the point $p_{j}$ that maximizes its distance
from $x$ has the highest value for at least one $f_{i}$. Based on this fact,
our algorithm is as follows: we iterate over all $n$ points and for each
function $f_{i}$ we find the point that maximizes the value of $f_{i}$. Next,
for each of the $n$ points we find the farthest point to it by computing its
distance to $2^{d}$ points that are the extreme points for the functions. Our
algorithm takes time $O(2^{d}nd)$.

###### Proof of Theorem 1.1.

The runtime of the algorithm is trivially bounded by $O(2^{d}nd)$. Here we
give a formal proof for the properties that we mentioned earlier. We first
show that for each pair of points $x$ and $y$, and any $0\leq i<2^{d}$, the
$\ell_{1}$ distance of $x$ and $y$ is lower bounded by $f_{i}(x)-f_{i}(y)$.
This follows from the following inequalities:

$\begin{split}f_{i}(x)-f_{i}(y)&=\sum_{1\leq j\leq
d,v^{i}_{j}=1}x_{j}-\sum_{1\leq j\leq d,v^{i}_{j}=0}x_{j}-\sum_{1\leq j\leq
d,v^{i}_{j}=1}y_{j}+\sum_{1\leq j\leq d,v^{i}_{j}=0}y_{j}\\\ &=\sum_{1\leq
j\leq d,v^{i}_{j}=1}(x_{j}-y_{j})+\sum_{1\leq j\leq
d,v^{i}_{j}=0}(y_{j}-x_{j})\\\ &\leq\sum_{1\leq j\leq d}|x_{j}-y_{j}|\\\
&=\ell_{1}(x,y).\end{split}$

To prove the second property, let for a point $x$ and a point $y$, $v$ be a
0/1 bit vector such that $v_{j}=1$ if $x_{j}\geq y_{j}$ and $v_{j}=0$
otherwise. Let the base-10 value of vector $v$ be $i$ and thus $v^{i}=v$. We
then show that $\ell_{1}(x,y)=f_{i}(x)-f_{i}(y)$ as follows:

$\begin{split}f_{i}(x)-f_{i}(y)&=\sum_{1\leq j\leq
d,v^{i}_{j}=1}x_{j}-\sum_{1\leq j\leq d,v^{i}_{j}=0}x_{j}-\sum_{1\leq j\leq
d,v^{i}_{j}=1}y_{j}+\sum_{1\leq j\leq d,v^{i}_{j}=0}y_{j}\\\ &=\sum_{1\leq
j\leq d,v^{i}_{j}=1}(x_{j}-y_{j})+\sum_{1\leq j\leq
d,v^{i}_{j}=0}(y_{j}-x_{j})\\\ &=\sum_{1\leq j\leq d}|x_{j}-y_{j}|\\\
&=\ell_{1}(x,y).\end{split}$

To show that for each point $x$, the farthest point from $x$ is the extreme
point for one function $f_{i}$ we bring the following argument: Let $p_{j}$ be
the point that is the farthest from $x$ and $f_{i}$ be the function such that
$f_{i}(p_{j})-f_{i}(x)=\ell_{1}(p_{j},x)$. Now, consider a point
$p_{j^{\prime}}$ that maximizes the value of $f_{i}$. Thus, we have:

$\begin{split}f_{i}(p_{j^{\prime}})-f_{i}(x)&\geq f_{i}(p_{j})-f_{i}(x)\\\
&=\ell_{1}(p_{j},x).\end{split}$

which implies that the distance of $p_{j^{\prime}}$ and $x$ is at least as
large as the distance of $p_{j}$ and $x$ by
$\ell_{1}(p_{j^{\prime}},x)\geq|f_{i}(p_{j^{\prime}})-f_{i}(x)|$. ∎

As a corollary of Theorem 1.1, one can find the farthest pair of the points
with the same algorithm.

See 1.2

###### Proof of Corollary 1.2.

The algorithm is the same as the algorithm of Theorem 1.1 except that instead
of finding a point that minimizes the distance to the farthest point, we find
the point that maximizes the distance to the farthest point. The proof is
exactly the same. ∎

##  4 Exact Lower Bounds for 1-center

In this section, we prove conditional lower bounds for the 1-center problem.
We start with some high-level remarks about the reductions and our
contributions.

Previous work has already designed reductions from SETH and OVH to _closest
pair_ kinds of questions for the metrics we consider, and our work can be
viewed as lifting these results to the 1-center question. As discussed in
Section 2 this requires a new starting assumption (either Quantified SETH or
the Hitting Set Conjecture) that has a different structure. Thus, technically,
the main contribution is to adapt the gadgetry of previous work into new
reductions with a different structure. In some cases, fundamental difficulties
arise and we can only resolve them by requiring that the algorithm lists all
solutions.

In all our reductions, we first reduce to the _Discrete 1-center with
Facilities_ , where given a set of clients $C\subseteq X$ and a set of
facilities $F\subseteq X$ in the metric space, the goal is to find $x$ in $F$
which minimizes the maximum distance to every point in $C$. We then reduce a
hard instance $(F,C)$ of the Discrete 1-center with Facilities problem to an
instance $P$ of the standard Discrete 1-center problem (without facilities) by
adding a few additional coordinates to points in $F\cup C$ and then
introducing a new point/string $s$ such that it is far from every point in $C$
(in comparison to its distance from the points/strings in $F$). Thus we
ensured that the 1-center of $P:=F\cup C\cup\\{s\\}$ must be from $F$.
Nevertheless, for the sake of compactness, this two step reduction in the
proofs of this section is sometimes written as a one step reduction.

This section is organized as follows. In Section 4.1, we show that there are
no subquadratic listing algorithms for Euclidean 1-center even in low
dimensions (Theorem 1.6). Next in Section 4.2, we show the conditional
subquadratic time lower bounds for 1-center in various metrics (Theorem 1.3).
Finally, in Section 4.3, we show the conditional subquartic time lower bound
for 1-center in edit metric (also Theorem 1.4) and explain how to adapt it for
1-median.

###  4.1 Subquadratic Lower Bounds for 1-center in Low dimensional Euclidean
space

In this subsection, we show that an algorithm with running time similar to the
one in the previous section for $\ell_{1}$-metric does not extend to the
Euclidean metric. Our proof essentially adopts ideas developed in [Wil18a,
Che20].

######  Theorem 4.1.

Assuming $\mathsf{HSC}$, there exists a constant $\eta>0$ such that for every
$\varepsilon>0$, no algorithm running in time $n^{2-\varepsilon}$ can given as
input a point-set $P\in\mathbb{R}^{d}$ and a positive real $\alpha$ output all
points in $P$ whose 1-center cost in the Euclidean metric is at most $\alpha$,
where $|P|=n$, $d=\eta^{\log^{*}n}$, and representing each vector requires at
most $\widetilde{O}(\log n)$ bits.

###### Proof of Theorem 4.1.

We prove the theorem statement by contradiction. Suppose for some
$\varepsilon>0$ there is an algorithm $\mathcal{T}$ running in time
$n^{2-\varepsilon}$ that can given as input a point-set
$P\subseteq\mathbb{R}^{d}$ and a positive real $\alpha$ output all points in
$P$ whose 1-center cost in the Euclidean metric is at most $\alpha$, where
$|P|=n$, $d=\eta^{\log^{*}n}$, and each vector is of at most $k\log n$ bit
entries (for some constant integer $k$).

Let $(\mathcal{A}:=(S_{1},\ldots,S_{n}),\mathcal{B}:=(T_{1},\ldots,T_{n}),U)$
be an instance arising from $\mathsf{HSC}$, where $|U|=c\log n$. We think of
each set in $\mathcal{A}$ and $\mathcal{B}$ as its characteristic vector in
$\\{0,1\\}^{c\log n}$. We show how we can decide this instance in
$n^{2-\frac{\varepsilon}{2}}$ time using $\mathcal{T}$, thus contradicting
$\mathsf{HSC}$.

We need the following theorem from Chen [Che20].

######  Theorem 4.2 (Chen [Che20]).

Let $b,\ell$ be two sufficiently large integers. There is a reduction
$\psi_{b,\ell}:\\{0,1\\}^{b\cdot\ell}\to\mathbb{Z}^{\ell}$ and a set
$V_{b,\ell}\subseteq\mathbb{Z}$, such that for every
$x,y\in\\{0,1\\}^{b\cdot\ell}$,

$x\cdot y=0\Leftrightarrow\psi_{b,\ell}(x)\cdot\psi_{b,\ell}(y)\in V_{b,\ell}$

and

$0\leq\psi_{b,\ell}(x)_{i}<{\ell}^{6^{\log^{*}(b)}\cdot b}$

for all possible $x$ and $i\in[\ell]$. Moreover, the computation of
$\psi_{b,\ell}(x)$ takes $\operatorname*{poly}(b\cdot\ell)$ time, and the set
$V_{b,\ell}$ can be constructed in $O\left(\ell^{O(6^{\log^{*}(b)}\cdot
b)}\cdot\operatorname{poly}(b\cdot\ell)\right)$ time.

We use the above theorem with $\ell=7^{\log^{*}n}$ and $b=|U|/\ell$. Note that
if $\ell=7^{\log^{*}n}$ then $\log\left({\ell}^{6^{\log^{*}(b)}\cdot
b}\right)=o(\log n)$. All of the below construction details appears in
[Wil18a, Che20] and we skip many of the calculations and claim proofs
hereafter. Our contributions are mainly in using these previously known
constructions in a new way to prove the theorem statement. In particular, for
every $t\in V_{b,\ell}$ we create an instance
$(P_{t}\subseteq\mathbb{R}^{(\ell+1)^{2}+3},\alpha:=\sqrt{2n^{5}-1})$ of
1-center as follows.

For every777Recall that we think of $S_{i}$ and $T_{j}$ through their
characteristic vector. $S_{i}\in\mathcal{A}$ (resp. $T_{j}\in\mathcal{B}$) we
first define a point $p_{i}^{t}\in\mathbb{Z}^{\ell+1}$ (resp.
$q_{j}^{t}\in\mathbb{Z}^{\ell+1}$) as follows:

$p_{i}^{t}:=(\psi_{b,\ell}(S_{i}),t)\ (\text{resp.
}q_{j}^{t}:=(\psi_{b,\ell}(T_{j}),-1)).$

It is then easy to verify that $S_{i}\cap T_{j}=\emptyset$ if and only if
there exists some $t\in V_{b,\ell}$ such that $\langle
p_{i}^{t},q_{j}^{t}\rangle=0$. Next for every
$p_{i}^{t}\in\mathbb{Z}^{\ell+1}$ (resp. $q_{j}^{t}\in\mathbb{Z}^{\ell+1}$) we
define $\widetilde{p}_{i}^{t}\in\mathbb{Z}^{(\ell+1)^{2}}$ (resp.
$\widetilde{q}_{j}^{t}\in\mathbb{Z}^{(\ell+1)^{2}}$) as follows:

$\forall a,b\in[\ell+1],\ \widetilde{p}_{i}^{t}(a,b):=p_{i}^{t}(a)\cdot
p_{i}^{t}(b)\ (\text{resp. }\widetilde{q}_{j}^{t}(a,b):=-q_{j}^{t}(a)\cdot
q_{j}^{t}(b)).$

It is then straightforward to verify that $\langle
p_{i}^{t},q_{j}^{t}\rangle=0$ if and only if
$\langle\widetilde{p}_{i}^{t},\widetilde{q}_{j}^{t}\rangle\geq 0$.

Finally, we have our pointset $P_{t}\in\mathbb{R}^{(\ell+1)^{2}+3}$ defined as
follows:

$P_{t}:=\underbrace{\left\\{\left(\widetilde{p}_{i}^{t},\sqrt{n^{5}-\|\widetilde{p}_{i}^{t}\|_{2}^{2}},0,0\right)\bigg{|}S_{i}\in\mathcal{A}\right\\}}_{P_{t}^{\mathcal{A}}}\bigcup\underbrace{\left\\{\left(-\widetilde{q}_{j}^{t},0,\sqrt{n^{5}-\|\widetilde{q}_{j}^{t}\|_{2}^{2}},\sqrt{n^{5}}\right)\bigg{|}T_{j}\in\mathcal{B}\right\\}}_{P_{t}^{\mathcal{B}}}\cup\left\\{\vec{0}\right\\},$

where $\vec{0}=(0,0,\ldots,0)$.

It can then be verified that
$\langle\widetilde{p}_{i}^{t},\widetilde{q}_{j}^{t}\rangle\geq 0$ if and only
if the distance between
$\left(\widetilde{p}_{i}^{t},\sqrt{n^{5}-\|\widetilde{p}_{i}^{t}\|_{2}^{2}},0\right)$
and
$\left(-\widetilde{q}_{j}^{t},0,\sqrt{n^{5}-\|\widetilde{q}_{j}^{t}\|_{2}^{2}}\right)$
is at least $\sqrt{2n^{5}}$; otherwise their distance is at most
$\sqrt{2n^{5}-1}$. Also note that any pair of points in
${P_{t}^{\mathcal{A}}}$ or any pair of points in ${P_{t}^{\mathcal{B}}}$ are
at distance at most $\sqrt{2n^{5}-1}$ from each other. Finallt, note that the
distance between any point in ${P_{t}^{\mathcal{B}}}$ and $\vec{0}$ is exactly
$\sqrt{2n^{5}}$ and the distance between any point in ${P_{t}^{\mathcal{A}}}$
and $\vec{0}$ is exactly $\sqrt{n^{5}}$.

We run $\mathcal{T}$ on $(P_{t},\alpha:=\sqrt{2n^{5}-1})$ for every $t\in
V_{b,\ell}$. Let $\mathcal{O}_{t}\subseteq P_{t}$ be the output of running
$\mathcal{T}$ on $(P_{t},\alpha)$. In other words for every $t\in V_{b,\ell}$
and every $p\in\mathcal{O}_{t}$ we have that for every $p^{\prime}\in P_{t}$,
$\|p-p^{\prime}\|_{2}\leq\sqrt{2n^{5}-1}$.

We claim that there exists $S$ in $\mathcal{A}$ such that it intersects with
every subset $T$ in $\mathcal{B}$ if and only if there exists $i\in[n]$ such
that for all $t\in V_{b,\ell}$, we have
$\left(\widetilde{p}_{i}^{t},\sqrt{n^{5}-\|\widetilde{p}_{i}^{t}\|_{2}^{2}},0\right)\in\mathcal{O}_{t}$.

Suppose there exists $S_{i^{*}}$ in $\mathcal{A}$ such that it intersects with
every subset $T$ in $\mathcal{B}$. Fix $t\in V_{b,\ell}$. We have that
$\left(\widetilde{p}_{i^{*}}^{t},\sqrt{n^{5}-\|\widetilde{p}_{i^{*}}^{t}\|_{2}^{2}},0\right)$
is at distance at most $\sqrt{2n^{5}-1}$ from every other point in
$P_{t}^{\mathcal{A}}$ just from construction. Suppose there is
$\left(-\widetilde{q}_{j}^{t},0,\sqrt{n^{5}-\|\widetilde{q}_{j}^{t}\|_{2}^{2}}\right)\in
P_{t}^{\mathcal{B}}$ such that their distance is greater than
$\sqrt{2n^{5}-1}$ then from the construction, their distance must be
$\sqrt{2n^{5}}$, which implies that $S_{i^{*}}\cap T_{j}=\emptyset$, a
contradiction.

On the other hand, if for every $S$ in $\mathcal{A}$ there exists $T$ in
$\mathcal{B}$ such that $S$ and $T$ are disjoint then we show that for any
point
$\left(\widetilde{p}_{i}^{t},\sqrt{n^{5}-\|\widetilde{p}_{i}^{t}\|_{2}^{2}},0\right)$
there exists $t\in V_{b,\ell}$ such that
$\left(\widetilde{p}_{i}^{t},\sqrt{n^{5}-\|\widetilde{p}_{i}^{t}\|_{2}^{2}},0\right)\notin\mathcal{O}_{t}$.
Fix $i\in[n]$. Let $T_{j}\in\mathcal{B}$ such that $S_{i}\cap
T_{j}=\emptyset$. Let $t^{*}:=\psi_{b,\ell}(S_{i})\cdot\psi_{b,\ell}(T_{j})$.
From Theorem 4.2 we have that $t^{*}\in V_{b,\ell}$. Thus
$\left(\widetilde{p}_{i}^{t^{*}},\sqrt{n^{5}-\|\widetilde{p}_{i}^{t^{*}}\|_{2}^{2}},0\right)$
and
$\left(-\widetilde{q}_{j}^{t^{*}},0,\sqrt{n^{5}-\|\widetilde{q}_{j}^{t^{*}}\|_{2}^{2}}\right)$
in $P_{t^{*}}$ are at distance at least $\sqrt{2n^{5}}$ and thus
$\left(\widetilde{p}_{i}^{t^{*}},\sqrt{n^{5}-\|\widetilde{p}_{i}^{t^{*}}\|_{2}^{2}},0\right)\notin\mathcal{O}_{t^{*}}$.

Finally, note that the total run time was
$O(n^{2-\varepsilon}\cdot|V_{b,\ell}|)=O(n^{2-\varepsilon}\log
n)<n^{2-\frac{\varepsilon}{2}}$. ∎

###  4.2 Subquadratic Lower Bounds for 1-center when $d=\omega(\log n)$ in
String and $\ell_{p}$-metrics

In this subsection, we show that subquadratic time algorithms for 1-center do
not exist in $\ell_{p}$-metrics, Ulam metic, and edit metric, when
$d=\omega(\log n)$.

######  Theorem 4.3 (Subquadratic Hardness of 1-center in $\ell_{p}$-metrics).

Let $p\in\mathbb{R}_{\geq 1}\cup\\{0\\}$. Assuming $\mathsf{HSC}$, for every
$\varepsilon>0$, there exists $c>1$ such that no algorithm running in time
$n^{2-\varepsilon}$ can, given as input a point-set $P\subseteq\\{0,1\\}^{d}$,
solve the discrete 1-center problem in $\ell_{p}$-metric, where $|P|=n$ and
$d=c\log n$.

###### Proof.

Let $(\mathcal{A}:=(S_{1},\ldots,S_{n}),\mathcal{B}:=(T_{1},\ldots,T_{n}),U)$
be an instance arising from $\mathsf{HSC}$. We construct a point-set
$P\subseteq\\{0,1\\}^{d}$ where $|P|=2n+1$ and $d=5\cdot|U|+2$. We build the
two maps
$\tau_{\mathcal{A}}:\mathcal{A}\to\\{0,1\\}^{d},\tau_{\mathcal{B}}:\mathcal{B}\to\\{0,1\\}^{d}$
and a special point $s\in\\{0,1\\}^{d}$ and the point-set $P$ is then simply
defined to be the union of $\\{s\\}$ and the images (range) of
$\tau_{\mathcal{A}}$ and $\tau_{\mathcal{B}}$, i.e.,

$P:=\\{\tau_{\mathcal{A}}(S)\mid
S\in\mathcal{A}\\}\cup\\{\tau_{\mathcal{B}}(T)\mid
T\in\mathcal{B}\\}\cup\\{s\\}.$

Let $U:=\\{u_{1},\ldots,u_{m}\\}$. We define our special point $s$ as follows:

$\forall i\in[5m+2],\ s_{i}:=\begin{cases}0&\text{ if }1\leq i\leq 3m\\\
1&\text{ if }3m+1\leq i\leq 5m+2\end{cases}$

For any $S\in\mathcal{A}$ we define $\tau_{\mathcal{A}}(S)$ as follows:

$\forall i\in[5m+2],\ \tau_{\mathcal{A}}(S)_{i}:=\begin{cases}1&\text{ if
}u_{i}\in S\text{ and }1\leq i\leq m\\\ 0&\text{ if }u_{i}\notin S\text{ and
}1\leq i\leq m\\\ 0&\text{ if }u_{i-m}\in S\text{ and }m+1\leq i\leq 2m\\\
1&\text{ if }u_{i-m}\notin S\text{ and }m+1\leq i\leq 2m\\\ 0&\text{ if
}2m+1\leq i\leq 4m+1\\\ 1&\text{ if }4m+2\leq i\leq 5m+2\end{cases}$

For any $T\in\mathcal{B}$ we define $\tau_{\mathcal{B}}(T)$ as follows:

$\forall i\in[5m+2],\ \tau_{\mathcal{B}}(T)_{i}:=\begin{cases}1&\text{ if
}u_{i}\in T\text{ and }1\leq i\leq m\\\ 0&\text{ if }u_{i}\notin T\text{ and
}1\leq i\leq m\\\ 0&\text{ if }m+1\leq i\leq 2m\\\ 0&\text{ if }u_{i-2m}\in
T\text{ and }2m+1\leq i\leq 3m\\\ 1&\text{ if }u_{i-2m}\notin T\text{ and
}2m+1\leq i\leq 3m\\\ 0&\text{ if }3m+1\leq i\leq 5m+2\end{cases}$

Notice that for any $S,S^{\prime}$ in $\mathcal{A}$ and $T$ in $\mathcal{B}$,
we have

$\|\tau_{\mathcal{A}}(S)-\tau_{\mathcal{B}}(T)\|_{p}=\left(|S|+|T|-2\cdot|S\cap
T|+m-|S|+m-|T|+m+1\right)^{1/p}=\left(3m+1-2\cdot|S\cap T|\right)^{1/p}.$
$\|\tau_{\mathcal{A}}(S)-\tau_{\mathcal{A}}(S^{\prime})\|_{p}\leq\left(2m\right)^{1/p}.$
$\|\tau_{\mathcal{A}}(S)-s\|_{p}=\left(2m+1\right)^{1/p}.$
$\|\tau_{\mathcal{B}}(T)-s\|_{p}=\left(3m+2\right)^{1/p}.$

Suppose there exists $S$ in $\mathcal{A}$ such that it intersects with every
subset $T$ in $\mathcal{B}$ then $\tau_{\mathcal{A}}(S)$ has distance strictly
less than $(3m+1)^{1/p}$ with $\tau_{\mathcal{B}}(T)$ for every $T$ in
$\mathcal{B}$. Additionally, $\tau_{\mathcal{A}}(S)$ has distance at most
$(2m)^{1/p}$ with $\tau_{\mathcal{A}}(S^{\prime})$ for any
$S^{\prime}\in\mathcal{A}$ and distance $(2m+1)^{1/p}$ with $s$. Therefore,
$\tau_{\mathcal{A}}(S)$ is at distance at most $(3m)^{1/p}$ from every point
in $P$.

On the other hand, if for every $S$ in $\mathcal{A}$ there exists $T$ in
$\mathcal{B}$ such that $S$ and $T$ are disjoint, then we show that for any
point $x$ in $P$ there is a point $y$ in $P$ such that
$\|x-y\|_{p}\geq(3m+1)^{1/p}$. Suppose $x:=\tau_{\mathcal{B}}(T)$ for some
$T\in{\mathcal{B}}$ then we have $x$ is at distance $(3m+2)^{1/p}$ from $s$.
Similarly if $x:=s$ then it is at distance $(3m+2)^{1/p}$ from every
$\tau_{\mathcal{B}}(T)$ for all $T\in{\mathcal{B}}$. Finally, if
$x:=\tau_{\mathcal{A}}(S)$ for some $S\in{\mathcal{A}}$ then from the
soundness assumption we have that there exists $T$ in $\mathcal{B}$ such that
$S$ and $T$ are disjoint. Thus, $x$ is at distance $(3m+1)^{1/p}$ from
$\tau_{\mathcal{B}}(T)$. ∎

######  Remark 4.4.

For the $\ell_{\infty}$-metric, we can solve Discrete 1-center problem in
$\widetilde{O}(nd)$ time as follows. For every coordinate, we determine the
1-center cost of the point-set projected onto that coordinate. The 1-center
cost of the point-set then is the maximum of the 1-center costs over all the
coordinates.

The quadratic lower bound for 1-center in Ulam metric follows from the below
lemma.

######  Lemma 4.5.

Let $\Pi_{d}$ denote the set of all permutations over $[d]$. For every
$d\in\mathbb{N}$, there is a function $\eta:\\{0,1\\}^{d}\to\Pi_{2d}$, such
that for all $a,b\in\\{0,1\\}^{d}$ the following holds:

$\mathsf{ed}(\eta(a),\eta(b))=2\cdot\|a-b\|_{0}.$

Moreover, for any $a\in\\{0,1\\}^{d}$, $\eta(a)$ can be computed in $O(d)$
time.

###### Proof.

Let $a\in\\{0,1\\}^{d}$. We define $\eta(a)$ as follows:

$\forall i\in[2d],\ \eta(a)[i]=\begin{cases}i&\text{ if }i=2k-1\text{ and
}a_{k}=0\text{ for some }k\in\mathbb{N}\\\ i&\text{ if }i=2k\text{ and
}a_{k}=0\text{ for some }k\in\mathbb{N}\\\ i+1&\text{ if }i=2k-1\text{ and
}a_{k}=1\text{ for some }k\in\mathbb{N}\\\ i-1&\text{ if }i=2k\text{ and
}a_{k}=1\text{ for some }k\in\mathbb{N}\end{cases}$

Fix some $k\in[d]$ and $a,b\in\\{0,1\\}^{d}$. If $a_{k}=b_{k}$ then notice
that $\eta(a)[2k]=\eta(b)[2k]$ and $\eta(a)[2k-1]=\eta(b)[2k-1]$. If
$a_{k}\neq b_{k}$ then $\eta(a)[2k]=\eta(b)[2k-1]$ and
$\eta(a)[2k-1]=\eta(b)[2k]$. Since the characters do not repeat, we have that
the optimal distance is obtained by swapping which amounts to two edit
operations. ∎

######  Corollary 4.6 (Subquadratic Hardness of 1-center in Ulam metric).

Assuming $\mathsf{HSC}$, for every $\varepsilon>0$ there exists $c>1$ such
that no algorithm running in time $n^{2-\varepsilon}$ can given as input a set
$P$ of $n$ many permutations of $[d]$, solve the discrete 1-center problem in
Ulam metric, where $|P|=n$ and $d=c\log n$.

The quadratic lower bound for 1-center in Edit metric follows from the below
lemma.

######  Lemma 4.7.

For every $d\in\mathbb{N}$, there is a function
$\eta:\\{0,1\\}^{d}\to\\{0,1\\}^{d^{\prime}}$, such that for all
$a,b\in\\{0,1\\}^{d}$ the following holds:

$\mathsf{ed}(\eta(a),\eta(b))=\|a-b\|_{0}.$

Moreover, for any $a\in\\{0,1\\}^{d}$, $\eta(a)$ can be computed in $O(d\log
d)$ time.

###### Proof.

Let $l_{1},l_{2},\ldots,l_{d}$ be $d$ strings of length $10\log d$ each made
by realizing $10\log d$ $0/1$ bits uniformly at random. It follows that with
high probability, the hamming distance as well as the edit distance of each
pair $l_{i},l_{j}$ ($i\neq j$) is $\Omega(\log d)$ [BEK+03]. For a string $a$,
we define $\eta(a)$ in the following way: we make a string of size $d(10\log
d+1)$ which consists of $d$ consecutive blocks. Each block $i$ starts with
$a_{i}$ and is followed by $l_{i}$. By putting all the blocks next to each
other we obtain a string of size $d(10\log d+1)$ which we denote by $\eta(a)$.
We prove in the following that $\mathsf{ed}(\eta(a),\eta(b))=\|a-b\|_{0}$
holds for each pair of strings $a$ and $b$.

$\mathsf{ed}(\eta(a),\eta(b))\leq\|a-b\|_{0}$ immediately follows from the
fact that by only toggling the first characters of some block of $\eta(a)$ we
can turn $\eta(a)$ into $\eta(b)$ and this transformation only costs
$\|a-b\|_{0}$. Note that we only toggle the first characters of the blocks
whose corresponding characters in $a$ and $b$ are not the same.

Now, assume for the sake of contradiction that
$\mathsf{ed}(\eta(a),\eta(b))<\|a-b\|_{0}$ holds. This implies that for at
least $d-\|a-b\|_{0}+1$ many blocks of $a$, the transformation cost is 0. In
other words, for each of these blocks, there is a substring of length $10\log
d+1$ in $\eta(b)$ which is completely the same as that block. Indeed, this can
only happen if for some $i$, the $i$’th block of $\eta(a)$ is transformed into
the $i$’th block of $\eta(b)$ and $a_{i}=b_{i}$. Thus, this implies that for
at least $d-\|a-b\|_{0}+1$ different values of $i$ we have $a_{i}=b_{i}$ which
is contradiction. ∎

######  Corollary 4.8 (Subquadratic Hardness of 1-center in Edit metric).

Assuming $\mathsf{HSC}$, for every $\varepsilon>0$ there exists $c>1$ such
that no algorithm running in time $n^{2-\varepsilon}$ can given as input a
point-set $P\subseteq\\{0,1\\}^{d}$ solve the discrete 1-center problem in
edit metric, where $|P|=n$ and $d=c\log n\log\log n$.

Next we prove much higher lower bounds for the Edit metric when $d$ is larger.

###  4.3 Subquartic Lower Bound for 1-center when $d=n$ in Edit metric

We now present our lower bound under Quantified SETH which offers a conceptual
novelty since as discussed in Section 2 it is the first time (to our
knowledge) that more than two quantifier alternations are utilized.

######  Theorem 4.9 (Subquartic Hardness of 1-center in Edit metric).

Assuming Quantified SETH, for every $\varepsilon>0$ no algorithm running in
time $n^{4-\varepsilon}$ can given as input a point-set
$P\subseteq\\{0,1\\}^{n}$ solve the discrete 1-center problem in edit metric,
where $|P|=n$.

###### Proof.

Let us first reduce to the 1-center problem with facilities where there are
two sets of binary strings, a set of clients $C$ and a set of facilities $F$
and the goal is to decide if there is a string in $F$ that has ED at most
$\tau$ to all strings in $C$. Given an instance
$\mathcal{A},\mathcal{B},\mathcal{C},\mathcal{D}$ of
$\exists\forall\exists\exists\mathsf{OVH}$ we construct $C$ and $F$ as
follows.

First we will use the following lemma that follows from the existing
reductions from OVH to ED [BI15, BK15] (the latter reference gets the alphabet
size down to $2$).

######  Lemma 4.10 ([BK15]).

There are two linear time algorithms such that: each algorithm takes a set
($A$ or $B$) of $n$ binary vectors of length $d$ and constructs (independently
of the other) a binary string ($s_{A}$ or $s_{B}$) of length $O(nd)$ with the
following property for a fixed value $\tau$ that only depends on $n,d$:
$ED(s_{A},s_{B})<\tau$ if there is a pair of orthogonal vectors $v_{A}\in
A,v_{B}\in B$ and $ED(s_{A},s_{B})\geq\tau$ otherwise.

For a set $X\subseteq[d]$ let $v(X)\in\\{0,1\\}^{d}$ be the natural encoding
of the set as a binary vector where $v(X)[i]=1$ iff $i\in X$. Note that two
vectors are orthogonal iff the two corresponding sets are disjoint.

Now, for each set $S_{A}\in\mathcal{A}$ define the set of $n$ vectors
$A=\\{v(X)\mid S_{C}\in\mathcal{C},X=S_{A}\cap S_{C}\\}$ representing the $n$
sets that result from intersecting $S_{A}$ with any set in $\mathcal{C}$.
Similarly, for each set $S_{B}\in\mathcal{B}$ define the set of $n$ vectors
$B=\\{v(X)\mid S_{D}\in\mathcal{D},X=S_{B}\cap S_{D}\\}$.

It follows that there is an orthogonal pair $v_{A}\in A,v_{B}\in B$ iff there
exist $S_{C}\in\mathcal{C}$ and $S_{D}\in\mathcal{D}$ such that $S_{A}\cap
S_{B}\cap S_{C}\cap S_{D}=\emptyset$. Therefore, if we use the algorithms in
the above lemma to encode each set $A$ with a string $s_{A}$ and add it to the
set of facilities $F$, and also encode each set $B$ with a string $s_{B}$ and
add it into the set of clients $C$ we get the reduction we are after: By the
definition of the $\exists\forall\exists\exists\mathsf{OVH}$ problem, there is
a string $s_{A}\in F$ such that for all strings $s_{B}\in C$ we have
$ED(s_{A},s_{B})<\tau$ if and only if the given
$\exists\forall\exists\exists\mathsf{OVH}$ instance is a yes-instance.

Finally, we reduce to the basic 1-center problem (without facilities). Suppose
that the strings in $F,C$ have length $m$. We simply construct an instance
$P\subseteq\\{0,1\\}^{4m}$ of 1-center as follows.

$P:=\\{1^{m}\circ f\circ 0^{2m}\mid f\in F\\}\cup\\{1^{m}\circ c\circ
1^{2m}\mid c\in C\\}\cup\\{0^{4m}\\}.$

The following simple facts about the ED of the transformed strings show that
the optimal center in $P$ must be from $\\{1^{m}\circ f\circ 0^{2m}\mid f\in
F\\}$ and its cost would be smaller than $2m+\tau$ iff the original
$\exists\forall\exists\exists\mathsf{OVH}$ instance is a yes-instance.

######  Claim 4.11.

Let $x,y$ be two binary strings of length $m$ with ED exactly $t$.

  * •

$ED(1^{m}\circ x\circ 0^{2m},1^{m}\circ y\circ 0^{2m})\leq m$.

  * •

$ED(1^{m}\circ x\circ 0^{2m},0^{4m})\leq 2m$.

  * •

$ED(1^{m}\circ x\circ 0^{2m},1^{m}\circ y\circ 1^{2m})=2m+t$.

  * •

$ED(1^{m}\circ x\circ 1^{2m},0^{4m})\geq 3m$.

The first and second items follow from the straightforward alignment of the
strings. The fourth item follows because $ED(0^{\ell},1^{\ell})=\ell$. The
third item requires a bit more care. First, to see that the ED is at most
$2m+t$ consider the alignment that maps $x$ to $y$ optimally at cost $t$ and
then maps the other parts in the straightforward way at cost $2m$. Now suppose
for contradiction that there was a better alignment. This alignment must match
one of the new letters (from the transformation) to $x$ or $y$; otherwise it
would yield an alignment between $x,y$ at cost smaller than $t$. But any
alignment that matches the $1$ letters on the left to $x$ or $y$ can be
corrected so that the $1^{m}$ parts on the left are matched to each other,
without affecting the cost. Similarly, any matching between the letters on the
right to $x$ or $y$ can be corrected without increasing the cost. Suppose that
a $0$ from the right is matched to $y$. This implies that one of the $1$’s to
the right of $y$ must be deleted (because there are no longer enough $0$’s in
the other string to get substituted with all of them), and a corrected
alignment that instead substitutes the $0$ with a $1$ (reducing the number of
such deletions by one) and leaves the mate in $y$ unmatched does not have a
higher cost. We refer the reader to [BK15] for more formal proofs of such
claims.

∎

######  Remark 4.12.

The above reduction to Edit also work for the 1-median problem but with two
key differences. The first and main difference is that, since we take the sum
instead of the max, the cost in the objective may now be affected by non-
orthogonal pairs and it is no longer sufficient to have gadgets that give
distance $<\tau$ or $\geq\tau$ depending on the orthogonality. Instead, we
need gadgets that guarantee that the distance is either $<\tau$ or exactly
$\tau$. Fortunately, such requirements can be accomplished, see e.g. Theorem
$4$ in [BI15]. The second difference is that we do not need the $\forall$
quantifier in the starting assumption; the sum is powerful enough to support
the (standard) $\exists\exists\exists\exists$ structure type. Therefore, the
lower bounds for 1-median can be based on the standard SETH rather than the
Quantified-SETH.

##  5 An $n^{2.5}$ time $1+\epsilon$ Approximation Algorithm for 1-Center in
Ulam Metric when $d=n$

In this section, we consider the 1-center problem under Ulam metric. More
precisely, we consider a problem where $n$ strings $s_{1},s_{2},\ldots,s_{n}$
are given as input and our goal is to find a string $s_{k}$ such that the
maximum distance of $s_{k}$ from the rest of the strings is minimized. Our
focus here is on the Ulam metric.

We assume throughout this section that the length of all strings is equal to
$d$. Our algorithm for this case is two-fold. Let $o$ be the value of the
solution (i.e., the maximum distance of the center of the strings to the rest
of the strings is exactly equal to $o$). If $o$ is lower bounded by
$\sqrt{d}$, previous work on Ulam distance gives us a $1+\epsilon$ approximate
solution for center in the following way: We iterate over all pairs of strings
and each time we estimate their Ulam distance via the algorithm of Naumovitz,
Saks, and Seshadhri [NSS17a] for approximating the Ulam distance of each pair.
When the Ulam distance of two strings is equal to $u$, their algorithm takes
time $\widetilde{O}_{\epsilon}(d/u+\sqrt{d})$ to $1+\epsilon$ approximate the
solution. Thus, we only run their algorithm up to a runtime of
$\widetilde{O}_{\epsilon}(\sqrt{d})$ to either obtain a $1+\epsilon$
approximate solution for the Ulam distance or verify that the Ulam distance is
smaller than $\sqrt{d}$. It follows that if $o\geq\sqrt{d}$ this information
is enough for us to approximate the 1-center problem within a factor
$1+\epsilon$ and the runtime of the algorithm is bounded by
$\widetilde{O}_{\epsilon}(n^{2}\sqrt{d})$. Thus, it only remains to design an
algorithm for the low-distance regime.

From here on, we assume that $o\leq\sqrt{d}$. In this case, we take an
arbitrary string (say $s_{1}$) and compute the Ulam distance of that string to
all the other strings. In addition to this, we also keep track of the changes
that convert $s_{1}$ into all the strings. It follows that since
$o\leq\sqrt{d}$, the distance of $s_{1}$ to all the strings is bounded by at
most $2\sqrt{d}$. Thus, via the transformations we compute in this step, we
would be able to make a transformation from any $s_{i}$ to any $s_{j}$ with at
most $4\sqrt{d}$ operations (we can combine the transformation from $s_{1}$ to
$s_{i}$ and the transformation from $s_{1}$ to $s_{j}$). Using this
information, we can determine the exact Ulam distance of every string $s_{i}$
to every string $s_{j}$ in the following way:

We start with the non-optimal transformation from $s_{i}$ to $s_{j}$ that uses
at most $4\sqrt{d}$ operations. We then split the characters from
$[1,\ldots,d]$ into buckets such that in each bucket all the characters are
next to each other and they appear in the same order in the two strings. It
follows that because there is a transformation from $s_{i}$ to $s_{j}$ with at
most $4\sqrt{d}$ operations, the total number of buckets would be bounded by
$O(\sqrt{d})$. Moreover, there exists an optimal transformation wherein either
all characters of each buckets are deleted/inserted or all characters of each
bucket remain intact. This implies that we can compress the two strings into
smaller strings by replacing each bucket with a single character. The
insertion and deletion of these special characters then has a cost
proportional to the size of the bucket. This way, the size of the two strings
would be bounded by $O(\sqrt{d})$ and thus we can compute the Ulam distance of
the two strings in time $\widetilde{O}(\sqrt{d})$. Therefore, we can compute
the center of the strings in time
$\widetilde{O}_{\epsilon}(nd+n^{2}\sqrt{d})$.

Data: $s_{1},s_{2},\ldots,s_{n}$

Result: 1-center

$o\leftarrow\infty$;

for  _$i\leftarrow 1$ to $n$_ do

$mx\leftarrow-1$;

for  _$j\leftarrow 1$ to $n$_ do

Run [NSS17a] on $s_{i}$ and $s_{j}$ up to $\widetilde{O}_{\epsilon}(\sqrt{d})$
steps;

if  _the algorithm terminates_ then

$mx\leftarrow\max\\{mx,\text{the output of the algorithm}\\}$;

end if

end for

$o\leftarrow\min\\{o,mx\\}$;

end for

if  _$o\neq-1$_ then

return o;

end if

else

$o\leftarrow\infty$;

for  _$i\leftarrow 1$ to $n$_ do

$tr_{i}\leftarrow$ optimal transformation between $s_{1}$ and $s_{i}$;

end for

for  _$i\leftarrow 1$ to $n$_ do

$mx\leftarrow-1$;

for  _$j\leftarrow 1$ to $n$_ do

$(s^{*}_{i},s^{*}_{j})\leftarrow$ compressed versions of $(s_{i},s_{j})$ based
on $tr_{i}$ and $tr_{j}$;

$mx\leftarrow\max\\{mx,\text{the Ulam distance of }s^{*}_{i}\text{ and
}s^{*}_{j}\\}$;

end for

$o\leftarrow\min\\{o,mx\\}$;

end for

return $o$;

end if

Algorithm 1 1-center of $n$ strings under Ulam metric.

See 1.5

###### Proof of Theorem 1.5.

The outline of the algorithm along with its runtime analysis is given earlier.
Here we prove that the approximation factor of the algorithm is bounded by
$1+\epsilon$. In case $o\geq\sqrt{d}$, we use the $1+\epsilon$ approximation
algorithm of Naumovitz, Saks, and Seshadhri [NSS17a] for each pair of strings
up to a runtime of $\widetilde{O}_{\epsilon}(\sqrt{d})$. If the algorithm
gives an estimation before we terminate it, we take the value into account
when determining the maximum distance for the strings involved. It follows
that since $o\geq\sqrt{d}$, then for each string $s_{x}$, there is one string
$s_{y}$ whose distance to $s_{x}$ is at least $\sqrt{d}$ and thus the maximum
distance we determine for each string is a $1+\epsilon$ approximation of the
optimal value.

Next, we show that in case $o\leq\sqrt{d}$, our algorithm determines the Ulam
distance of each pair exactly and thus solves the 1-center problem correctly.
In order to determine the Ulam distance between $s_{i}$ and $s_{j}$, we begin
with a transformation of size at most $4\sqrt{d}$ between the two strings. We
then mark all the characters that are either deleted or inserted in this
transformation and all the characters that are next to these characters. We
then compress the two strings in the following way: each marked character
becomes a single character with the same value. Each maximal interval of
unmarked characters that are next to each other also become a single character
whose value represents the entire interval. Therefore, the compressed strings
have $O(\sqrt{d})$ characters each. It follows that the Ulam distance of the
compressed strings is exactly equal to the Ulam distance of the original
strings. Moreover, even though for the compressed strings the operations have
arbitrary costs, we can still solve Ulam distance in time proportional to the
length of the strings which results in an algorithm with runtime
$\widetilde{O}(\sqrt{d})$ for computing Ulam distance between each pair. ∎

##  6 Hardness of Approximation of 1-center in String and $\ell_{p}$-metrics

In this section, we prove hardness of approximation results for the 1-center
problem but first we need some error correcting codes background.

##### Error-Correcting Codes.

An error correcting code $C$ over alphabet $\Sigma$ is a function
$C:\Sigma^{m}\to\Sigma^{\ell}$ where $m$ and $\ell$ are positive integers
which are referred to as the message length and block length of $C$
respectively. Intuitively, the function $C$ encodes an original message of
length $m$ to an encoded message of length $\ell$. The rate of a code
$\rho(C)$ is defined as the ratio between its message length and its block
length, i.e., $\rho(C)=\nicefrac{{m}}{{\ell}}$. The relative distance of a
code, denoted by $\delta(C)$, is defined as $\underset{x\neq
y\in\Sigma^{m}}{\min}\delta(C(x),C(y))$ where $\delta(C(x),C(y))$ is the
relative Hamming distance between $C(x)$ and $C(y)$, i.e., the fraction of
coordinates on which $C(x)$ and $C(y)$ disagree.

In this paper, we require our codes to have some special algebraic properties
which have been shown to be present in algebraic geometric codes [GS96].
First, we will introduce a couple of additional definitions.

######  Definition 6.1 (Systematicity).

Given $s\in\mathbb{N}$, a code $C:\Sigma^{m}\to\Sigma^{\ell}$ is
$s$-systematic if there exists a size-$s$ subset of $[\ell]$, which for
convenience we identify with $[s]$, such that for every $x\in\Sigma^{s}$ there
exists $w\in\Sigma^{m}$ in which $x=C(w)\mid_{[s]}$.

######  Definition 6.2 (Degree-$t$ Closure).

Let $\Sigma$ be a finite field. Given two codes
$C:\Sigma^{m}\to\Sigma^{\ell},C^{\prime}:\Sigma^{m^{\prime}}\to\Sigma^{\ell}$
and positive integer $t$, we say that $C^{\prime}$ is a degree-$t$ closure of
$C$ if, for every $w_{1},\ldots,w_{r}\in\Sigma^{m}$ and
$P\in\mathbb{F}[X_{1},\ldots,X_{r}]$ of total degree at most $t$, it holds
that $\omega:=P(C(w_{1}),\ldots,C(w_{r}))$ is in the range of $C^{\prime}$,
where $\omega\in\Sigma^{\ell}$ is defined coordinate-wise by the equation
$\omega_{i}:=P(C(w_{1})_{i},\ldots,C(w_{r})_{i})$.

Below we provide a self-contained statement of the result we need; it follows
from Theorem 7 of [SAK+01], which gives an efficient construction of the
algebraic geometric codes based on [GS96]’s explicit towers of function
fields.

######  Theorem 6.3 ([GS96, SAK+01]).

There is a constant $\lambda>0$ such that for any prime $q\geq 7$, there are
two code families $\mathcal{C}^{1}=\\{C_{n}^{1}\\}_{n\in\mathbb{N}},\
\mathcal{C}^{2}=\\{C_{n}^{2}\\}_{n\in\mathbb{N}}$ such that the following
holds for all $n\in\mathbb{N}$,

  * •

$C_{n}^{1}$ and $C_{n}^{2}$ are $n$-systematic code with alphabet
$\mathbb{F}_{q^{2}}$,

  * •

$C_{n}^{1}$ and $C_{n}^{2}$ have block length less than $\lambda n$.

  * •

$C_{n}^{2}$ has relative distance $\geq\nicefrac{{1}}{{2}}$,

  * •

$C_{n}^{2}$ is a degree-$2$ closure of $C_{n}^{1}$, and,

  * •

Any codeword in $C_{n}^{1}$ or $C_{n}^{2}$ can be computed in poly($n$) time.

We point the interested reader to [KLM19] for a proof sketch of the above
theorem.

######  Theorem 6.4 (Subquadratic Inapproximability of 1-center in
$\ell_{p}$-metrics).

Let $p\in\mathbb{R}_{\geq 1}\cup\\{0\\}$. Assuming $\mathsf{HSC}$, for every
$\varepsilon>0$ there exists $\delta>0$ such that no algorithm running in time
$n^{2-\varepsilon}$ can given as input a point-set $P\subseteq\\{0,1\\}^{d}$
and a positive real $\alpha$ output all points in $P$ whose 1-center cost in
the $\ell_{p}$-metric is at most $\alpha\cdot(1+\delta)$, where $|P|=n$ and
$d=O_{\varepsilon}(\log n)$.

###### Proof.

Fix $p\in\mathbb{R}_{\geq 1}\cup\\{0\\}$. We prove the theorem statement by
contradiction. Suppose for some $\varepsilon>0$ there is an algorithm
$\mathcal{T}$ running in time $n^{2-\varepsilon}$ that can for every
$\delta>0$, given as input a point-set $P\subseteq\mathbb{R}^{d}$ and a
positive real $\alpha$ output all points in $P$ whose 1-center cost in the
$\ell_{p}$-metric is at most $\alpha\cdot(1+\delta)$, where $|P|=n$ and
$d=\omega(\log n)$.

Let $(\mathcal{A}:=(S_{1},\ldots,S_{n}),\mathcal{B}:=(T_{1},\ldots,T_{n}),U)$
be an instance arising from $\mathsf{HSC}$, where $|U|=c\log n$. We think of
each set in $\mathcal{A}$ and $\mathcal{B}$ as its characteristic vector in
$\\{0,1\\}^{c\log n}$. We show how we can decide this instance in
$n^{2-\frac{\varepsilon}{2}}$ time using $\mathcal{T}$, thus contradicting
$\mathsf{HSC}$.

The construction below is exactly the same as the one suggested by Rubinstein
[Rub18]. We however, use this construction to fit our purposes of proving
lower bound for the 1-center problem.

#### Algebrization

Fix $T=2c/\varepsilon$. Let $q$ be the smallest prime greater than $T$ (i.e.,
$q<2\cdot T$). Let $m:=c\log n$. Let $C_{m/T}^{1}$ and $C_{m/T}^{2}$ be the
codes guaranteed in Theorem 6.3 over $\mathbb{F}_{q^{2}}$ with block length
$\ell\leq\lambda m/T$.

Let $\widetilde{C}\subseteq C_{m/T}^{2}$ such that $\omega\in\widetilde{C}$ if
and only if $\omega\mid_{[m/T]}=\vec{0}$ (i.e., $\omega$ has a zero entry in
each of the first $m/T$ coordinates). For every $\omega\in\widetilde{C}$ we
define two functions
$\tau_{\mathcal{A}}^{\omega},\tau_{\mathcal{B}}^{\omega}:\\{0,1\\}^{m}\to\\{0,1\\}^{r}$,
where $r:=q^{4(T+2)}\times\ell$. We can thus index every $i\in[r]$ using
elements in $\mathbb{F}_{q^{2}}^{T}\times\mathbb{F}_{q^{2}}^{T}\times[\ell]$.

Fix $x\in\\{0,1\\}^{m}$. Let $x=(x^{1},\ldots,x^{T})\in\\{0,1\\}^{m}$ where
for all $i\in[T]$ we have $x^{i}\in\\{0,1\\}^{m/T}$. We define
$\tau_{\mathcal{A}}^{\omega}(x)$ coordinate wise. Fix $\zeta\in[r]$ and we
think of $\zeta$ as follows:

$\displaystyle\zeta=\left((\mu_{1}^{\mathcal{A}},\ldots,\mu_{T+2}^{\mathcal{A}}),(\mu_{1}^{\mathcal{B}},\ldots,\mu_{T+2}^{\mathcal{B}}),j\right)\in\mathbb{F}_{q^{2}}^{T+2}\times\mathbb{F}_{q^{2}}^{T+2}\times[\ell].$
(1)

We define $\tau_{\mathcal{A}}^{\omega}(x)_{\zeta}$ to be 1 if and only if:

$\underset{i\in[T+2]}{\sum}\mu_{i}^{\mathcal{A}}\cdot\mu_{i}^{\mathcal{B}}=\omega(j)\text{\
\ and \ \ }\forall i\in[T],\ \mu_{i}^{\mathcal{A}}=C_{m/T}^{1}(x^{i})_{j},\
\text{and }\mu_{T+1}^{\mathcal{A}}=0,\
\mu_{T+2}^{\mathcal{A}}=C_{m/T}^{1}(\mathbbm{1}^{m/T})_{j}.$

Similarly, we define $\tau_{\mathcal{B}}^{\omega}(x)$ coordinate wise. Fix
$\zeta\in[r]$ and we think of $\zeta$ as in (1). We define
$\tau_{\mathcal{B}}^{\omega}(x)_{\zeta}$ to be 1 if and only if:

$\underset{i\in[T+2]}{\sum}\mu_{i}^{\mathcal{A}}\cdot\mu_{i}^{\mathcal{B}}=\omega(j)\text{\
\ and \ \ }\forall i\in[T],\ \mu_{i}^{\mathcal{B}}=C_{m/T}^{1}(x^{i})_{j}\
\text{and }\mu_{T+1}^{\mathcal{B}}=C_{m/T}^{1}(\mathbbm{1}^{m/T})_{j},\
\mu_{T+2}^{\mathcal{B}}=0.$

#### Construction

For every $S_{i}\in\mathcal{A}$, we define
$s_{i}^{\omega}:=\tau_{\mathcal{A}}^{\omega}(S_{i})$. Further, we define
$\widetilde{s}_{i}^{\omega}=(s_{i}^{\omega},\mathbbm{1}^{r}-s_{i}^{\omega},\mathbbm{1}^{2r})\in\\{0,1\\}^{4r}$.
For every $T_{j}\in\mathcal{B}$, we define
$t_{j}^{\omega}:=\tau_{\mathcal{B}}^{\omega}(T_{j})$. Further, we define
$\widetilde{t}_{j}^{\omega}=(\mathbbm{1}^{r}-t_{j}^{\omega},t_{j}^{\omega},{0}^{2r})\in\\{0,1\\}^{4r}$.

We define the point-set $P_{\omega}$ to be
$P_{\omega}^{\mathcal{A}}:=\\{\widetilde{s}_{i}^{\omega}\mid
S_{i}\in\mathcal{A}\\}\cup
P_{\omega}^{\mathcal{B}}:=\\{\widetilde{t}_{j}^{\omega}\mid
T_{j}\in\mathcal{B}\\}\cup\\{\mathbbm{1}^{4r}\\}$. Let
$\alpha:=(2q^{4(T+2)}-4q^{2(T+1)})\cdot\ell+2r+\ell$. Let
$\delta:=1/(4q^{4T}-4q^{2T-2}+1)$.

#### Analysis

We run $\mathcal{T}$ on $(P_{\omega},\alpha)$ for every
$\omega\in\widetilde{C}$. Let $\mathcal{O}_{\omega}\subseteq P_{\omega}$ be
the output of running $\mathcal{T}$ on $(P_{\omega},\alpha)$. In other words
for every $\omega\in\widetilde{C}$ and every $s\in\mathcal{O}_{t}$ we have
that for every $s^{\prime}\in P_{\omega}$,
$\|s-s^{\prime}\|_{p}\leq(1+\delta)^{1/p}\cdot\alpha^{1/p}$.

We claim that there exists $S$ in $\mathcal{A}$ such that it intersects with
every subset $T$ in $\mathcal{B}$ if and only if there exists $i\in[n]$ such
that for all $\omega\in\widetilde{C}$, we have
$\widetilde{s}_{i}^{\omega}\in\mathcal{O}_{\omega}$.

Suppose there exists $S_{i^{*}}$ in $\mathcal{A}$ such that it intersects with
every subset $T$ in $\mathcal{B}$. Fix $\omega\in\widetilde{C}$. We have that
$\widetilde{s}_{i^{*}}^{\omega}$ is at distance at most $(2r)^{1/p}$ from
every other point in $P_{\omega}^{\mathcal{A}}$ just from construction.
Suppose there is $\widetilde{t}_{j}^{\omega}\in P_{\omega}^{\mathcal{B}}$ such
that their distance is greater than $\alpha^{1/p}$ then from the construction,
their distance must be at least $(1+\delta)^{1/p}\cdot\alpha^{1/p}$, which
implies that $S_{i^{*}}\cap T_{j}=\emptyset$, a contradiction.

On the other hand, if for every $S$ in $\mathcal{A}$ there exists $T$ in
$\mathcal{B}$ such that $S$ and $T$ are disjoint then we show that for any
point $\widetilde{s}_{i}^{\omega}$ there exists $\omega\in\widetilde{C}$ such
that $\widetilde{s}_{i}^{\omega}\notin\mathcal{O}_{\omega}$. Fix $i\in[n]$.
Let $T_{j}\in\mathcal{B}$ such that $S_{i}\cap T_{j}=\emptyset$. Let
$\omega^{*}:=\sum_{e\in[T]}C_{m/T}^{1}(S_{i}^{e})\cdot
C_{m/T}^{1}(T_{j}^{e})$. From Theorem 6.3 we have that
$\omega^{*}\in\widetilde{C}$. Thus $\widetilde{s}_{i}^{\omega^{*}}$ and
$\widetilde{t}_{j}^{\omega^{*}}$ in $P_{\omega^{*}}$ are at distance at least
$(1+\delta)^{1/p}\cdot\alpha^{1/p}$ and thus
$\widetilde{s}_{i}^{\omega^{*}}\notin\mathcal{O}_{\omega^{*}}$. Also, note
that for all $\omega\in\widetilde{C}$, we have that every point in
$P_{\omega}^{\mathcal{B}}$ is at distance at least $(3r)^{1/p}$ from
$\mathbbm{1}^{4r}$.

Finally, note that the total run time was
$O(n^{2-\varepsilon}\cdot|\widetilde{C}|)=O(n^{2-\varepsilon+\frac{c}{T}})<n^{2-\frac{\varepsilon}{2}}$.
∎

The results readily extend to the edit metric from the below statement and to
the Ulam metric from Lemma 3.4.

######  Lemma 6.5 (Rubinstein [Rub18]).

For large enough $d\in\mathbb{N}$, there is a function
$\eta:\\{0,1\\}^{d}\to\\{0,1\\}^{d^{\prime}}$, where $d^{\prime}=O(d\log d)$,
such that for all $a,b\in\\{0,1\\}^{d}$ the following holds for some constant
$\lambda>0$:

$\left|\mathsf{ed}(\eta(a),\eta(b))-\lambda\cdot\log
d\cdot\|a-b\|_{0}\right|=o(d^{\prime}).$

Moreover, for any $a\in\\{0,1\\}^{d}$, $\eta(a)$ can be computed in $2^{o(d)}$
time.

## References

  * [ABHS20] Amir Abboud, Karl Bringmann, Danny Hermelin, and Dvir Shabtay.  Scheduling lower bounds via AND subset sum.  In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), volume 168 of LIPIcs, pages 4:1–4:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [ARW17] Amir Abboud, Aviad Rubinstein, and R. Ryan Williams.  Distributed PCP theorems for hardness of approximation in P.  In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 25–36, 2017\.
  * [AWW16] Amir Abboud, Virginia Vassilevska Williams, and Joshua R. Wang.  Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs.  In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 377–391. SIAM, 2016.
  * [BC19] Karl Bringmann and Bhaskar Ray Chaudhury.  Polyline simplification has cubic complexity.  In Gill Barequet and Yusu Wang, editors, 35th International Symposium on Computational Geometry, SoCG 2019, June 18-21, 2019, Portland, Oregon, USA, volume 129 of LIPIcs, pages 18:1–18:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [BEK+03] Tugkan Batu, Funda Ergün, Joe Kilian, Avner Magen, Sofya Raskhodnikova, Ronitt Rubinfeld, and Rahul Sami.  A sublinear algorithm for weakly approximating edit distance.  In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 316–324, 2003.
  * [BI15] Arturs Backurs and Piotr Indyk.  Edit distance cannot be computed in strongly subquadratic time (unless SETH is false).  In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 51–58. ACM, 2015.
  * [BK15] Karl Bringmann and Marvin Künnemann.  Quadratic conditional lower bounds for string problems and dynamic time warping.  In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 79–97. IEEE Computer Society, 2015.
  * [BLPR97] Amir Ben-Dor, Giuseppe Lancia, Jennifer Perone, and R. Ravi.  Banishing bias from consensus sequences.  In Alberto Apostolico and Jotun Hein, editors, Combinatorial Pattern Matching, 8th Annual Symposium, CPM 97, Aarhus, Denmark, June 30 - July 2, 1997, Proceedings, volume 1264 of Lecture Notes in Computer Science, pages 247–261. Springer, 1997.
  * [CDK21] Diptarka Chakraborty, Debarati Das, and Robert Krauthgamer.  Approximating the median under the ulam metric.  In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 \- 13, 2021, pages 761–775. SIAM, 2021.
  * [CGI+16] Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, and Stefan Schneider.  Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility.  In Madhu Sudan, editor, Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, Cambridge, MA, USA, January 14-16, 2016, pages 261–270. ACM, 2016.
  * [Che20] Lijie Chen.  On the hardness of approximate and exact (bichromatic) maximum inner product.  Theory Comput., 16:1–50, 2020.
  * [CHW10] Kenneth L. Clarkson, Elad Hazan, and David P. Woodruff.  Sublinear optimization for machine learning.  In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 449–457. IEEE Computer Society, 2010.
  * [CKL21] Vincent Cohen-Addad, Karthik C. S., and Euiwoong Lee.  On approximability of clustering problems without candidate centers.  In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 \- 13, 2021, pages 2635–2648. SIAM, 2021.
  * [dlHC00] Colin de la Higuera and Francisco Casacuberta.  Topology of strings: Median string is np-complete.  Theoretical Computer Science, 230(1):39–48, 2000.
  * [FL97] Moti Frances and Ami Litman.  On covering problems of codes.  Theory Comput. Syst., 30(2):113–119, 1997.
  * [GBT84] Harold N Gabow, Jon Louis Bentley, and Robert E Tarjan.  Scaling and related techniques for geometry problems.  In Proceedings of the sixteenth annual ACM symposium on Theory of computing, pages 135–143, 1984.
  * [GGJ76] M. R. Garey, Ronald L. Graham, and David S. Johnson.  Some np-complete geometric problems.  In Ashok K. Chandra, Detlef Wotschke, Emily P. Friedman, and Michael A. Harrison, editors, Proceedings of the 8th Annual ACM Symposium on Theory of Computing, May 3-5, 1976, Hershey, Pennsylvania, USA, pages 10–22. ACM, 1976.
  * [GJL99] Leszek Gasieniec, Jesper Jansson, and Andrzej Lingas.  Efficient approximation algorithms for the hamming center problem.  In Robert Endre Tarjan and Tandy J. Warnow, editors, Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 17-19 January 1999, Baltimore, Maryland, USA, pages 905–906. ACM/SIAM, 1999.
  * [GS96] Arnaldo Garcia and Henning Stichtenoth.  On the asymptotic behaviour of some towers of function fields over finite fields.  Journal of Number Theory, 61(2):248 – 273, 1996.
  * [KLM19] Karthik C. S., Bundit Laekhanukit, and Pasin Manurangsi.  On the parameterized complexity of approximating dominating set.  J. ACM, 66(5):33:1–33:38, 2019.
  * [LLM+03] J. Kevin Lanctôt, Ming Li, Bin Ma, Shaojiu Wang, and Louxin Zhang.  Distinguishing string selection problems.  Inf. Comput., 185(1):41–55, 2003.
  * [LMW02a] Ming Li, Bin Ma, and Lusheng Wang.  Finding similar regions in many sequences.  J. Comput. Syst. Sci., 65(1):73–96, 2002.
  * [LMW02b] Ming Li, Bin Ma, and Lusheng Wang.  On the closest string and substring problems.  J. ACM, 49(2):157–171, 2002.
  * [MS20] Michael Mitzenmacher and Saeed Seddighin.  Dynamic algorithms for LIS and distance to monotonicity.  In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 671–684. ACM, 2020.
  * [NR03] François Nicolas and Eric Rivals.  Complexities of the centre and median string problems.  In Proceedings of the 14th Annual Conference on Combinatorial Pattern Matching, CPM’03, page 315–327, Berlin, Heidelberg, 2003. Springer-Verlag.
  * [NR05] François Nicolas and Eric Rivals.  Hardness results for the center and median string problems under the weighted and unweighted edit distances.  Journal of discrete algorithms, 3(2-4):390–415, 2005.
  * [NSS17a] Timothy Naumovitz, Michael Saks, and C Seshadhri.  Accurate and nearly optimal sublinear approximations to ulam distance.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2012–2031. SIAM, 2017.
  * [NSS17b] Timothy Naumovitz, Michael E. Saks, and C. Seshadhri.  Accurate and nearly optimal sublinear approximations to ulam distance.  In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 2012–2031. SIAM, 2017.
  * [Rub18] Aviad Rubinstein.  Hardness of approximate nearest neighbor search.  In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 1260–1268. ACM, 2018.
  * [SAK+01] Kenneth W. Shum, Ilia Aleshnikov, P. Vijay Kumar, Henning Stichtenoth, and Vinay Deolalikar.  A low-complexity algorithm for the construction of algebraic-geometric codes better than the Gilbert-Varshamov bound.  IEEE Trans. Information Theory, 47(6):2225–2241, 2001.
  * [SBG+97] Nikola Stojanovic, Piotr Berman, Deborah Gumucio, Ross C. Hardison, and Webb Miller.  A linear-time algorithm for the 1-mismatch problem.  In Frank K. H. A. Dehne, Andrew Rau-Chaplin, Jörg-Rüdiger Sack, and Roberto Tamassia, editors, Algorithms and Data Structures, 5th International Workshop, WADS ’97, Halifax, Nova Scotia, Canada, August 6-8, 1997, Proceedings, volume 1272 of Lecture Notes in Computer Science, pages 126–135. Springer, 1997.
  * [Sch94] S Schuierer.  An optimal algorithm to compute the l1-diameter and center of a simple rectilinear polygon.  Technical report, Technical Report 49, Institut f ur Informatik, Universit at Freiburg, 1994.
  * [SP03] Jeong Seop Sim and Kunsoo Park.  The consensus string problem for a metric is np-complete.  J. Discrete Algorithms, 1(1):111–117, 2003.
  * [Wil18a] Ryan Williams.  On the difference between closest, furthest, and orthogonal pairs: Nearly-linear vs barely-subquadratic complexity.  In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1207–1215. SIAM, 2018.
  * [Wil18b] Virginia Vassilevska Williams.  On some fine-grained questions in algorithms and complexity.  In Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018, pages 3447–3487. World Scientific, 2018.
  * [Yao82] Andrew Chi-Chih Yao.  On constructing minimum spanning trees in k-dimensional spaces and related problems.  SIAM Journal on Computing, 11(4):721–736, 1982.