#  Johnson Coverage Hypothesis:
Inapproximability of $k$-means and $k$-median in $\ell_{p}$-metrics

Vincent Cohen-Addad  Google Research, Switzerland<EMAIL_ADDRESS>Karthik C. S.111Rutgers University, USA<EMAIL_ADDRESS> Euiwoong
Lee222 University of Michigan, USA<EMAIL_ADDRESS>
###### Abstract

$k$-$\mathsf{median}$ and $k$-$\mathsf{means}$ are the two most popular
objectives for clustering algorithms. Despite intensive effort, a good
understanding of the approximability of these objectives, particularly in
$\ell_{p}$-metrics, remains a major open problem. In this paper, we
significantly improve upon the hardness of approximation factors known in
literature for these objectives in $\ell_{p}$-metrics.

We introduce a new hypothesis called the _Johnson Coverage Hypothesis_
($\mathsf{JCH}$), which roughly asserts that the well-studied Max $k$-Coverage
problem on set systems is hard to approximate to a factor greater than
$\left(1-\nicefrac{{1}}{{e}}\right)$, even when the membership graph of the
set system is a subgraph of the Johnson graph. We then show that together with
generalizations of the embedding techniques introduced by Cohen-Addad and
Karthik (FOCS ’19), $\mathsf{JCH}$ implies hardness of approximation results
for $k$-$\mathsf{median}$ and $k$-$\mathsf{means}$ in $\ell_{p}$-metrics for
factors which are close to the ones obtained for general metrics. In
particular, assuming $\mathsf{JCH}$ we show that it is hard to approximate the
$k$-$\mathsf{means}$ objective:

  * •

Discrete case: To a factor of 3.94 in the $\ell_{1}$-metric and to a factor of
1.73 in the $\ell_{2}$-metric; this improves upon the previous factor of 1.56
and 1.17 respectively, obtained under the Unique Games Conjecture
($\mathsf{UGC}$).

  * •

Continuous case: To a factor of 2.10 in the $\ell_{1}$-metric and to a factor
of 1.36 in the $\ell_{2}$-metric; this improves upon the previous factor of
1.07 in the $\ell_{2}$-metric obtained under $\mathsf{UGC}$ (and to the best
of our knowledge, the continuous case of $k$-$\mathsf{means}$ in
$\ell_{1}$-metric was not previously analyzed in literature).

We also obtain similar improvements under $\mathsf{JCH}$ for the
$k$-$\mathsf{median}$ objective.

Additionally, we prove a weak version of $\mathsf{JCH}$ using the work of
Dinur et al. (SICOMP ’05) on Hypergraph Vertex Cover, and recover all the
results stated above of Cohen-Addad and Karthik (FOCS ’19) to (nearly) the
same inapproximability factors but now under the standard
$\mathsf{NP}\neq\mathsf{P}$ assumption (instead of $\mathsf{UGC}$).

Finally, we establish a strong connection between $\mathsf{JCH}$ and the long
standing open problem of determining the Hypergraph Turán number. We then use
this connection to prove improved SDP gaps (over the existing factors in
literature) for $k$-$\mathsf{means}$ and $k$-$\mathsf{median}$ objectives.

##  1 Introduction

Over the last 15 years, the Unique Game Conjecture has enabled tremendous
progress on the understanding of the (in)approximability of fundamental graph
problems, such as Vertex Cover [KR08], Max Cut [KKMO07], Betweeness [CGM09],
and Sparsest Cut [CKK+06, KV15, AKK+08], sometimes even leading to tight
results. Yet, the approximability of most $\mathsf{NP}$-hard _geometric_
problems remains wide open: even for fundamental geometric problems such as
the Traveling Salesman Problem, Steiner Tree, $k$-$\mathsf{median}$, and
Facility Location, the hardness of approximation in various $\ell_{p}$-metrics
has remained below 1.01. On the other hand, approximation algorithms for the
aforementioned problems in $\Omega(\log n)$ dimensions do not achieve much
better guarantees than what they do for general metrics. This situation stands
in stark contrast to the bounded dimension versions of the same problems,
whose approximabilities are mostly well understood.

The main approach for proving hardness of approximation for geometric problems
in $\ell_{p}$-metrics consists of two components: (1) establishing hardness of
approximation in general metric spaces; (2) finding an embedding of the hard
instances into $\ell_{p}$-metrics that preserves the gap. The challenge here
is to make (1) and (2) _meet_ at a sweet spot: we would like the hard gap
instances in general metric spaces to be ‘embeddable’, i.e., to be mapped into
the $\ell_{p}$-metric space while preserving the distances between points,
but, proving a significant inapproximability bound for ‘embeddable’ instances
requires a deep understanding of the hard instances (in the general metric) of
the problem at hand. This paper aims at characterizing the sweet spot between
(1) and (2), hence providing a general framework for obtaining strong
inapproximability for a large family of clustering and covering problems.

##### Hardness of Clustering Problems in $\ell_{p}$-metrics.

Given a set of points in a metric space, a clustering is a partition of the
points such that points in the same part are close to each other. Thus
studying the complexity of finding good clustering is a very natural research
avenue: On one hand these problems have a wide range of applications, ranging
from unsupervised learning, to information retrieval, and bioinformatics; on
the other hand, as we will illustrate in this paper, such problems are very
natural generalizations of set-cover-type problems to the metric setting, and
as such are very fundamental computational problems. The most popular
objectives for clustering in metric spaces are arguably the
$k$-$\mathsf{median}$ and $k$-$\mathsf{means}$ problems: Given a set of points
$P$ in a metric space, the $k$-$\mathsf{median}$ problem asks to identify a
set of $k$ representatives, called _centers_ , such that the sum of the
distances from each point to its closest center is minimized (for the
$k$-$\mathsf{means}$ problem, the goal is to minimize the sum of distances
squared) – see Section 2 for formal definitions. In general metrics, the
$k$-$\mathsf{median}$ and $k$-$\mathsf{means}$ problems are known to be hard
to approximate within a factor 1.73 and 3.94 respectively [GK99], whereas the
best known approximation algorithms achieve an approximation guarantee of 2.67
and 9 respectively [BPR+15, ANSW20].

A natural question arising from the above works is whether one can exploit the
structure of more specific metrics, such as doubling or Euclidean metrics to
obtain better approximation or bypass the lower bound. If the points lie in an
Euclidean space of arbitary dimension, a 6.357-approximation and a
2.633-approximation are known for $k$-$\mathsf{means}$ and
$k$-$\mathsf{median}$ respectively [ANSW20], while a near-linear time
approximation scheme is known for doubling metrics [CSF19]333With doubly
exponential dependency in the dimension. In terms of hardness of
approximation: the problems were known to be $\mathsf{APX}$-Hard since the
early 2000s [Tre00, GI03] in Euclidean spaces of dimension $\Omega(\log n)$
and have recently been shown to be hard to approximate within a factor of 1.17
and 1.06 for $k$-$\mathsf{means}$ and $k$-$\mathsf{median}$ respectively
[CK19]. Perhaps surprisingly, for some other structured metrics such as
Hamming or Edit distance, no better approximation algorithms are known while
the hardness known for both Hamming and Edit distances were 1.56 for
$k$-$\mathsf{means}$ problem and 1.14 for $k$-median problem. Summarizing, the
gap between upper and lower bounds for the Euclidean, Hamming, and Edit
metrics, remains huge.

##### Technical Barriers.

A well-known framework to obtain hardness of approximation results in the
general metric for clustering objectives is through a straightforward
reduction from the Max $k$-Coverage444Given a set system and $k\in\mathbb{N}$,
the problem asks to choose $k$ sets to maximize the size of their union. or
the Set Cover problem. We create a ’point’ for each element of the universe
and a ’candidate center’, namely a location where it is possible to place a
center, for each set. Then, we define the distance between a point
(corresponding to an element of the universe) and a candidate center
(corresponding to a set) to be 1 if the set contains the element and 3
otherwise. This reduction due to Guha and Khuller [GK99] yields lower bounds
of $1+2/e$ and $1+8/e$ for the $k$-$\mathsf{median}$ and $k$-$\mathsf{means}$
problems, respectively, in general discrete metric spaces.

However, for the $k$-$\mathsf{median}$ and $k$-$\mathsf{means}$ objectives,
the above strong hardness results for Max $k$-Coverage produce instances that
are impossible to embed in $\mathbb{R}^{n}$ without suffering a huge
distortion in the distances, and thus would yield only a trivial gap for
$k$-$\mathsf{means}$ or $k$-$\mathsf{median}$ problems in $\ell_{p}$-metrics.
This issue has been faced for most other geometric problems as well, such as
TSP or Steiner tree. It is tempting to obtain more structure on the “hard
instances” of set-cover-type problems with the large toolbox that has been
developed around the Unique Games Conjecture over the last 15 years for
fundamental graph problems such as Vertex Cover or Sparsest Cut. However, it
seems that most of these hardness of approximation tools would not provide the
adequate structure on the set cover instances constructed, namely a structure
that would make the whole instance easily “embeddable” into an
$\ell_{p}$-metric.

This illustrates the main difficulty in understanding $k$-$\mathsf{median}$/
$k$-$\mathsf{means}$ in $\ell_{p}$-metrics; Guha-Khuller type reductions from
general set systems with strong (perhaps optimal) gaps are not directly
“embeddable”, but the current results use hardness for very restricted systems
in a black-box way and thus cannot be extended to give strong hardness of
approximation results. Thus, we ask:

What structure on hard instances of Max $k$-Coverage problem would yield
meaningful hardness of $k$-$\mathsf{median}$ and $k$-$\mathsf{means}$ in
$\ell_{p}$-metrics?

###  1.1 Our Results

This paper addresses the above question in a unified manner, providing a
general framework for obtaining strong inapproximability in $\ell_{p}$-metrics
(see Table 1 for a summary of our results). We segregate our results below in
terms of conceptual and technical contributions and provide more details in
the subsequent subsubsections.

Our main conceptual contribution is proposing the Johnson Coverage Hypothesis
($\mathsf{JCH}$) and identifying it as lying at the heart of the hard
instances of $k$-$\mathsf{means}$ and $k$-$\mathsf{median}$ problems in
$\ell_{p}$-metrics. Intuitively, $\mathsf{JCH}$ conjectures that the
$(1-1/e)$-hardness of approximation for Max $k$-Coverage [Fei98] holds even
for set systems whose bipartite incidence graph (between sets and elements) is
a subgraph of the Johnson graph (see Section 1.1.1 for the formal definition).
Johnson graphs are well-studied objects in combinatorics that also admit nice
geometric embedding properties. More generally, we argue that identifying an
intermediate mathematical property between geometry and combinatorics, and
revisiting fundamental combinatorial optimization problems (Max $k$-Coverage
in this paper) restricted to instances having that property is a fruitful
avenue to understand approximability of high dimensional geometric
optimization problems.

Metric |  Discrete $k$-$\mathsf{means}$ |  Discrete $k$-$\mathsf{median}$ |  Continuous $k$-$\mathsf{means}$ |  Continuous $k$-$\mathsf{median}$ | Assumption |
---|---|---|---|---|---|---
$\ell_{0}$ | 1.56 [CK19] | 1.14 [CK19] | 1.21 [CK19] | 1.07 [CK19] | $\mathsf{UGC}$ | Previous
1.38 | 1.12 | 1.16 | 1.06 | $\mathsf{NP}\neq\mathsf{P}$ | This paper
3.94 | 1.73 | 2.10 | 1.36 |  $\mathsf{JCH}$/$\mathsf{JCH}^{*}$ | This paper
$\ell_{1}$ | 1.56 [CK19] | 1.14 [CK19] | – | 1.07 [CK19] | $\mathsf{UGC}$ | Previous
1.38 | 1.12 | 1.16 | 1.06 | $\mathsf{NP}\neq\mathsf{P}$ | This paper
3.94 | 1.73 | 2.10 | 1.36 |  $\mathsf{JCH}$/$\mathsf{JCH}^{*}$ | This paper
$\ell_{2}$ | 1.17 [CK19] | 1.06 [CK19] | 1.07 [CK19] | – | $\mathsf{UGC}$ | Previous
1.17 | 1.07 | 1.06 | 1.015 | $\mathsf{NP}\neq\mathsf{P}$ | This paper
1.73 | 1.27 | 1.36 | 1.08 |  $\mathsf{JCH}$/$\mathsf{JCH}^{*}$ | This paper
$\ell_{\infty}$ | 3.94 [CK19] | 1.73 [CK19] | Open555See Open Problem 5.5. | Open0 | $\mathsf{NP}\neq\mathsf{P}$ | Previous
General | 3.94 [GK99] | 1.73 [GK99] | 4 [CKL21] | 2 [CKL21] | $\mathsf{NP}\neq\mathsf{P}$ | Previous

Table 1:  State-of-the-art inapproximability for $k$-$\mathsf{means}$ and
$k$-$\mathsf{median}$ clustering objectives in various metric spaces for both
the discrete and continuous versions of the problem. All the results for
$\ell_{p}$-metrics stated inside the table are when the input points are given
in $O(\log n)$ dimensions. The NP-hardness reductions for the continuous
objectives are randomized.

Our main technical contributions are two-fold. First, we generalize the
embedding technique introduced in [CK19] that gives a reduction from covering
problems to clustering problems. The embedding technique in [CK19] has two
components: the first component is embedding the incidence graph of the
complete graph into $\ell_{p}$-metrics and the second component is a dimension
reduction technique developed by designing efficient protocols for the Vertex
Cover problem in the communication model. We generalize both these components:
we show how to embed the incidence graph of the complete _hypergraph_ into
$\ell_{p}$-metrics and we provide a dimension reduction technique by designing
efficient protocols for the _Set Cover_ problem in the communication model.
These generalization were necessary to prove strong inapproximability results
for clustering objectives as we needed to handle the less structured instances
arising from $\mathsf{JCH}$ and its variants (as opposed to [CK19] whose
reduction started from the more structured Vertex Coverage problem).

Combining $\mathsf{JCH}$ with the new embedding results above, we deduce
strong and perhaps even surprising inapproximability results: for example, we
show that $k$-$\mathsf{means}$ and $k$-$\mathsf{median}$ problems are no
easier in the $\ell_{1}$-metric/Hamming metric/Edit distance metric than in
general metric spaces666It is interesting to note that approximate nearest-
neighbor search, a problem closely related to clustering, is easier to solve
in the $\ell_{1}$-metric than general metrics., or obtain a much higher
inapproximability for $\ell_{2}$-metric (see Table 1 and Section 1.1.3 for the
whole list of results we obtain). Indeed, our framework accommodates hardness
of any variant of $\mathsf{JCH}$ defined in Section 1.1.2 in order to show new
hardness of clustering problems; for instance, the classic Set Cover hardness
of Feige (or any APX-hardness of Max $k$-Coverage) can be plugged into our
framework to produce $\mathsf{APX}$-Hardness for $k$-$\mathsf{means}$ and
$k$-$\mathsf{median}$ in all $\ell_{p}$-metrics in both the discrete and the
continuous case (see Remarks 3.14 and 3.19 for precise details)

Our second technical contribution is a new $\mathsf{NP}$-Hardness of
approximation result for a (weaker) variant of $\mathsf{JCH}$ corresponding to
Hypergraph Vertex Coverage in $3$-uniform hypergraphs. Consequently, with the
above generalized embedding technique, we obtained $\mathsf{NP}$-Hardness
results for clustering problems to factors that nearly match and sometimes
even improve upon the previous best hardness results (which were based on the
Unique Games Conjecture); see Table 1 for the precise factors. Our proof
relies on (i) tighter analysis of the Multilayered PCP constructed by Dinur et
al. [DGKR05], followed by (ii) a _densification_ process to ensure that the
resulting instance is dense enough to be used for clustering hardness. As the
previous best $\mathsf{NP}$-hardness results for clustering [CK19] rely on the
hardness of Vertex Coverage [AKS11, Man19, AS19] obtained by recent advances
on the 2-to-2 Games Conjecture [KMS17, DKK+18a, DKK+18b, KMS18, BKS19, BK19],
we believe that further study on $\mathsf{JCH}$ and its variants will lead to
more interesting ideas in hardness of approximation that will be useful for
understanding geometric optimization problems.

####  1.1.1 Johnson Coverage Hypothesis

We introduce the Johnson Coverage Hypothesis ($\mathsf{JCH}$) which states
that for every $\varepsilon>0$, there is some $z\in\mathbb{N}$, such that
given a parameter $k\in\mathbb{N}$ and a collection $E$ of $z$-sized subsets
($z$-sets henceforth) of $[n]$ as input, it is $\mathsf{NP}$-hard to
distinguish between the following two cases:

Completeness:

There are $k$ subsets of $[n]$ each of cardinality $z-1$, say
$S_{1},\ldots,S_{k}$, such that for every $T\in E$ there is some $i\in[k]$
such that $S_{i}\subset T$.

Soundness:

For every $k$ subsets of $[n]$ each of cardinality $z-1$, say
$S_{1},\ldots,S_{k}$, we have that there is $E^{\prime}\subseteq E$ such that

  * •

For every $T\in E^{\prime}$ and every $i\in[k]$ we have $S_{i}\not\subset T$.

  * •

$|E^{\prime}|\geq\left(\frac{1}{e}-\varepsilon\right)\cdot|E|$.

We will often say that a set $S$ covers another $T$ if $S\subseteq T$.

We refer to the gap problem described above in $\mathsf{JCH}$ as the Johnson
Coverage problem. Notice that when $z=2$, the Johnson Coverage problem is just
the Vertex Coverage problem, for which [AS19] have shown that a value close to
0.93 is the correct inapproximability ratio assuming the Unique Games
Conjecture. Therefore, for larger values of $z$, $\mathsf{JCH}$ suggests that
the Johnson Coverage problem (which is a generalization of the Vertex Coverage
problem) gets harder to approximate and approaches the same inapproximability
as Max $k$-Coverage.

Introducing $\mathsf{JCH}$ is the main conceptual contribution of this paper.
Most previous hardness results for geometric optimization problems [Tre00,
GI03, ACKS15, LSW17] use hardness of graph problems in bounded degree graphs
and embed them to $\ell_{p}$-metrics, where the bounded degree condition was
crucial for the inapproximability ratio. Cohen-Addad and Karthik [CK19], at
least in the context of clustering, were the first to show how to embed
instances of Vertex Coverage problem (with no restriction on the degree) to
obtain hard instances of $k$-$\mathsf{means}$ and $k$-$\mathsf{median}$.

In this work, we further study embeddability of coverage problems, and show
that the embedding of [CK19] can be further generalized to covering problems
on hypergraphs, i.e., to the Johnson Coverage problem, which may be as hard as
the general covering problem. Johnson Coverage problem is a purely
combinatorial covering problem, but the implicit geometric structure of the
problem allows us to seamlessly embed it to $\ell_{p}$-metrics.

##### Plausibility of $\mathsf{JCH}$ and Connection to Hypergraph Turán
Number.

One may reformulate the Johnson Coverage problem as a special case of Max
$k$-Coverage, by asking for instances of Max $k$-Coverage whose sets and
elements correspond to subsets of size $(z-1)$ and $z$ of some universe $[n]$
respectively. So it is natural to study the performance of the standard LP or
SDP relaxation, which is closely related to relaxations for the clustering
problems.

A natural gap instance for Johnson Coverage problem is the complete
$z$-uniform hypergraph, i.e., $E:=\binom{[n]}{z}$. Since each $e\in E$
contains exactly $z$ subsets of size $(z-1)$, the standard LP relaxation and
SDP relaxation admit a feasible solution whose value is at most
$\nicefrac{{\binom{[n]}{z-1}}}{{z}}$ and
$\nicefrac{{\binom{[n]}{z-1}}}{{z-1}}$ respectively [GL17]. Interestingly, the
soundness analysis of this proposed gap instance is closely related to the
Hypergraph Turán problem, a long standing open problem in extremal
combinatorics [Tur41].

Given $r<~{}z\in\mathbb{N}$, let $\mathsf{Tu}(n,z,r)$ be the minimum
$f\in\mathbb{N}$ such that there exists an $r$-uniform hypergraph $H=([n],F)$
with $n$ vertices and $f$ edges where every set $T\in\binom{[n]}{z}$ contains
at least one hyperedge from $F$. Let
$t(z,r)=\lim_{n\to\infty}\mathsf{Tu}(n,z,r)\binom{n}{r}^{-1}$. The classical
Turan’s theorem states that $t(z,2)=\nicefrac{{1}}{{(z-1)}}$, with the
extremal example being the union of $(z-1)$ equal-sized cliques. However, the
quantity of our interest $t(z,z-1)$ is not well understood when $z>3$; the
best lower bound is $\nicefrac{{1}}{{(z-1)}}$ [DC83] and the best upper bound
is $\nicefrac{{(1/2+o(1))\ln z}}{{z}}$ [Sid97], with the conjecture
$t(z,z-1)\geq\omega(1/z)$ still open [DC91]. We refer the reader to more
recent surveys by Sidorenko [Sid95] and Keevash [Kee11].

What will happen if $H$ has at most a $\nicefrac{{1}}{{(z-1)}}$ fraction of
hyperedges, which is much less than the conjectured value of $t(z,z-1)$? Then
some $T\in\binom{[n]}{z}$ will not be covered by hyperedges of $H$. If we
consider a random hypergraph where each hyperedge is picked with probability
$\nicefrac{{1}}{{z-1}}$, $S\in\binom{[n]}{z}$ is covered with probability
$1-(1-\nicefrac{{1}}{{z-1}})^{z}$, which converges to $1-1/e$ as $z$
increases. It is thus natural to hypothesize that this is indeed optimal as
$z$ increases.

######  Hypothesis 1.1.

Any $(z-1)$-uniform hypergraph with $n$ vertices and
$\nicefrac{{\binom{n}{z-1}}}{{z-1}}$ hyperedges covers at most a $d(n,z)$
fraction of sets of size $z$, where
$\lim_{z\to\infty}\lim_{n\to\infty}d(n,z)=1-1/e$.

If Hypothesis 1.1 is true, then the afore-proposed gap instance for Johnson
Coverage problem (the complete $z$-uniform hypergraph) has an integrality gap
of $(1-1/e+\varepsilon)$ for any $\varepsilon>0$ for the LP and SDP
relaxation. Thus, a refutation of $\mathsf{JCH}$ either implies interesting
constructions in extremal combinatorics or establishes that there is a
polynomial time algorithm outperforming the LP and SDP relaxation, on which
the current best approximation algorithms for both $k$-$\mathsf{median}$ and
$k$-$\mathsf{means}$ in any metric are based [BPR+15, ANSW20].

At first glance, the hypothesis looks rather strong (i.e., less likely to be
true) because of the existence of extremal structures that are strictly better
than random hypergraphs. However, these advantages often diminish as the size
of the object of interest increases. One example is the $z$-clique density in
graphs corresponding to $t(z,2)$. After the work of Razborov (for $z=3$
[Raz08]) and Nikiforov (for $z=4$ [Nik11]), Reiher [Rei16] proved that the
graph that covers the most number of $K_{z}$ with the given edge density is
the union of disjoint cliques of the same size. In our context, since every
$K_{z}$ has $\binom{z}{2}$ edges, the desired edge density is
$\nicefrac{{1}}{{w-1}}$ with $w=\binom{z}{2}$, so the extremal graph is the
union of $w$ disjoint cliques and the probability that a random copy of
$K_{z}$ is not covered by this graph is
$\prod_{i=1}^{z}(1-\frac{i-1}{\binom{z}{2}-1}),$ which converges to $1/e$ as
$z$ increases. So for large $z$, the extremal examples do not have an
advantage over a random graph! Indeed, this connection already gives improved
SDP gaps for various clustering objectives in natural hard instances in
$\ell_{p}$-metrics (see Theorem 1.6, or for more details, see Section 3.5).

##### Technical Barriers.

One may wonder if it is possible to start from Feige’s hard instances of Max
$k$-Coverage [Fei98] (which have the desired gap of $1-\nicefrac{{1}}{{e}}$)
and simply provide a gap-preserving reduction to Johnson Coverage problem. In
Theorem A.1 we showed that if such a reduction exists, then it should
significantly blow up the witness size (the number of sets needed to cover the
universe in the completeness case). At the heart of this observation is that
we are transforming arbitrary set systems (arising from hard instances of Max
$k$-Coverage) to set systems with bounded VC dimension (as in the Johnson
Coverage problem). In fact, a reduction in this spirit was recently obtained
in [CKL21], and that reduction did indeed blow up the witness size. Therefore
the result in [CKL21] where we show Max $k$-Coverage is hard to approximate
beyond $1-\nicefrac{{1}}{{e}}$ factor on set systems of large girth (thus
bounded VC dimension) may be seen as moral progress on understanding
$\mathsf{JCH}$.

Additionally, in Theorem A.11, we revisit Feige’s framework for showing
hardness of approximation of Max $k$-Coverage, and highlight that certain
simple modifications to his reduction would not prove $\mathsf{JCH}$. In
particular, we show that no “partition system” can be combined with standard
label cover instances to yield $\mathsf{JCH}$. This provides some evidence
that in order to prove $\mathsf{JCH}$, we would need to potentially prove
hardness of approximation result for some highly structured label cover
instances.

##### Subsequent Work.

Motivated by an earlier version of this paper, Guruswami and Sandeep [GS20]
initiated the study of the minimization variant of $\mathsf{JCH}$, where the
goal is to select as few $(z-1)$-sets as possible to ensure that every $z$-set
in $E$ is covered by a chosen $(z-1)$-set. While the naive algorithm gives a
$z$-approximation, they obtained an $(z/2+o(z))$-approximation algorithm. They
also asked as an open problem whether $\mathsf{JCH}$ and hardness of the
minimization version can be formally related.

####  1.1.2 Generalized Johnson Coverage Problem

Motivated by the connections in previous subsubsection to $t(z,r)$ for general
$z>r\geq 1$, we consider more generalized Johnson Coverage problems where the
input is still a collection of $z$-sized sets $E$ but instead of choosing
$(z-1)$-sized sets, we choose $r$-sized sets for some $r\in\\{1,\ldots,z-1\\}$
to cover as many sets in $E$ as possible. (See Definition 3.1 for the formal
definition.) For example, when $r=1$, the problem becomes the $z$-Hypergraph
Vertex Coverage problem. We prove the following for the $3$-Hypergraph Vertex
Coverage problem:

######  Theorem 1.2 (Informal statement; See Theorem 4.1).

For every $\varepsilon>0$, the $3$-Hypergraph Vertex Coverage problem is
$\mathsf{NP}$-Hard to approximate to a factor of $7/8+\varepsilon$.

While the covering version of the above problem, namely the (Minimum)
$3$-Hypergraph Vertex Cover has been studied actively in literature,
culminating in [DGKR05], the coverage version does not seem to have been
explicitly studied.

We remark that the above inapproximability result is higher than the
inapproximability of Vertex Coverage problem proved under $\mathsf{UGC}$ (of
roughly 0.93) and more so under $\mathsf{NP}\neq\mathsf{P}$ (of roughly 0.98),
and this higher gap will be useful in the next subsubsection for applications.

In Section 3, we provide a embedding framework which converts any hardness
result for Generalized Johnson Coverage problem (where $z>r\geq 1$) with
hardness ratio $\alpha<1$ to directly yield inapproximability results for
various clustering objectives. Together with Theorem 1.2, this framework
produces $\mathsf{NP}$-Hardness results nearly matching or improving the best
known hardness results assuming $\mathsf{UGC}$. The case $z=4$, $r=2$ also
yields improved SDP gaps for various clustering objectives in Section 3.5.

####  1.1.3 Inapproximability Results for $k$-$\mathsf{means}$ and
$k$-$\mathsf{median}$ in $\ell_{p}$-metrics

First, we present our results for the “discrete” $k$-$\mathsf{median}$ and
$k$-$\mathsf{means}$ problems. In these versions, the centers must be chosen
from a specific set of points of the metric.

######  Theorem 1.3 (Discrete version; Informal statement of Theorems 3.12 and
3.13).

Assuming $\mathsf{JCH}$, given $n$ points and $\text{poly}(n)$ candidate
centers, it is $\mathsf{NP}$-hard to approximate:

  * •

the $k$-$\mathsf{means}$ objective to within a
$1~{}+~{}\nicefrac{{8}}{{e}}\approx 3.94$ factor in $\ell_{1}$-metric and
$1~{}+~{}\nicefrac{{2}}{{e}}\approx 1.73$ factor in $\ell_{2}$-metric.

  * •

the $k$-$\mathsf{median}$ objective to within a
$1~{}+~{}\nicefrac{{2}}{{e}}\approx 1.73$ factor in $\ell_{1}$-metric and
$1.27$ factor in $\ell_{2}$-metric.

In fact, we obtain inapproximability results for all $\ell_{p}$-metrics (where
$p\in\mathbb{R}_{\geq 1}$), and the details are provided in Section 3. Also,
the results obtained in the above theorem significantly improves on the bounds
of [CK19] (see Table 1). Finally, we note that the bounds obtained for the
$\ell_{1}$-metric might be optimal as approximating $k$-$\mathsf{means}$ and
$k$-$\mathsf{median}$ to a factor of $3.95$ and $1.74$ is _fixed parameter
tractable_ even for general metrics [CGK+19].

We now sketch the proof of Theorem 1.3. We use the notations concerning
$\mathsf{JCH}$ established in Section 1.1.1. We create a point for each ($z$
size) subset in $E$ and a candidate center for each subset of $[n]$ of size
$z-1$. Both the points and candidate centers are just the characteristic
vectors of their corresponding subsets of $[n]$, i.e., the points are all
Boolean vectors of Hamming weight $z$ and the candidate centers are all
Boolean vectors of Hamming weight $z-1$. In the completeness case, it is easy
to see that there is a set $\mathcal{C}$ of $k$ candidate centers such that
every point has a center in $\mathcal{C}$ at (Hamming) distance 1. Also, in
the soundness case, it is easy to see that for every set $\mathcal{C}$ of $k$
candidate centers, we have that at least $\nicefrac{{1}}{{e}}-\varepsilon$
fraction of the points in $E$ are at (Hamming) distance at least 3 from every
center in $\mathcal{C}$ . Note that the dimension of this embedding is $n$,
and that we reduce it to $O(\log n)$ by developing a generalization of the
dimenionality reduction machinery introduced in [CK19]. Furthermore, the proof
from the Hamming metric to other $\ell_{p}$-metrics goes through the
composition of various graph embedding gadgets introduced in [CK19] and
generalized in this paper to hypergraph embedding.

We now shift our attention to the continuous case, where the centers can be
picked at arbitrary locations in the metric space. We show the
following777Note that Theorem 1.4 depends on a slight strengthening of
$\mathsf{JCH}$, which we call $\mathsf{JCH}^{*}$, where we further assume that
for the hard instances of $\mathsf{JCH}$, we have $|E|=\omega(k)$ (see Section
3.4 for further discussion). .

######  Theorem 1.4 (Continuous version; Informal statement of Theorems 3.16,
3.22, 3.24, and 3.25).

Assuming $\mathsf{JCH}^{*}$, given $n$ points, it is $\mathsf{NP}$-hard to
approximate:

  * •

the $k$-$\mathsf{means}$ objective to within $2.10$ factor in
$\ell_{1}$-metric and $1~{}+~{}\nicefrac{{1}}{{e}}\approx 1.36$ factor in
$\ell_{2}$-metric.

  * •

the $k$-$\mathsf{median}$ objective to within a
$1~{}+~{}\nicefrac{{1}}{{e}}\approx 1.36$ factor in $\ell_{1}$-metric and
$1.08$ factor in $\ell_{2}$-metric.

The above theorem for $k$-$\mathsf{median}$ in $\ell_{1}$-metric is obtained
through an intermediate hardness of approximation proof for
$k$-$\mathsf{median}$ in the Hamming metric (see Theorem 3.20). Additionally,
the fact that medians and means have nice algebraic definitions in $\ell_{1}$
and $\ell_{2}$ respectively allow us to transfer the hardness from Hamming
metrics without much loss. Furthermore, thanks to a technical result of
Rubinstein [Rub18] on near isometric embedding from Hamming metric in $d$
dimensions to Edit metric in $O(d\log d)$ dimensions, we can translate all our
(discrete case) results in the Hamming metric to the Edit metric (see Appendix
A in [CK19] for details).

We also prove the first hardness of approximation results for
$k$-$\mathsf{median}$ in $\ell_{2}$-metric (Theorem 3.24) and
$k$-$\mathsf{means}$ in $\ell_{1}$-metric (Theorem 3.25). Even though
continuous $k$-$\mathsf{median}$ in $\ell_{2}$ has been actively studied for
the bounded $d$ or $k$ [ARR98, BHPI02, KSS10, FL11], and to the best of our
knowledge, no hardness of approximation for the general case was known in the
literature. We remark that independent to our work, in [BGJ21], the authors
prove $\mathsf{APX}$-hardness of the Euclidean $k$-$\mathsf{median}$ problem
under $\mathsf{UGC}$.

Next, we move our attention to proving $\mathsf{NP}$-Hardness results. With
general versions of Theorem 1.3 and Theorem 1.4 for generalized Johnson
Coverage problem, Theorem 1.2 proves the following $\mathsf{NP}$-Hardness
results presented in Table 1. For continuous versions, more technical work and
randomized reductions are needed to ensure enough density (see Section 4.5).

######  Theorem 1.5.

It is $\mathsf{NP}$-hard to approximate the following clustering objectives;
discrete $k$-$\mathsf{means}$ in $\ell_{1}$ within $1.38$, discrete
$k$-$\mathsf{median}$ in $\ell_{1}$ within $1.12$, discrete
$k$-$\mathsf{means}$ in $\ell_{2}$ within $1.17$, discrete
$k$-$\mathsf{median}$ in $\ell_{2}$ within $1.07$, continuous
$k$-$\mathsf{means}$ in $\ell_{1}$ within $1.16$, continuous
$k$-$\mathsf{median}$ in $\ell_{1}$ within $1.06$, continuous
$k$-$\mathsf{means}$ in $\ell_{2}$ within $1.06$, and continuous
$k$-$\mathsf{median}$ in $\ell_{2}$ within $1.015$. The results for continuous
$k$-$\mathsf{median}$ and $k$-$\mathsf{means}$ hold under randomized
reductions.

Finally, we present another evidence for usefulness of (generalized) Johnson
Coverage problem via the clique density theorem of Reiher [Rei16], which gives
improved SDP gaps of $149/125=1.192$ for discrete $k$-$\mathsf{median}$ in
$\ell_{1}$-metric and $k$-$\mathsf{means}$ in $\ell_{2}$-metric when the
instances are well-separated. (I.e., points are not closed to one another.)
Moreover, this result holds even when the integral solution is allowed to use
$\Omega(k)$ more centers. Previously, the best gaps were $1.14$ and $1.17$ for
$k$-$\mathsf{median}$ in $\ell_{1}$-metric and $k$-$\mathsf{means}$ in
$\ell_{2}$-metric respectively, both following from the SDP gaps of the Unique
Games hardness [CK19].

######  Theorem 1.6 (Informal version of Theorem 3.26).

Fix any $\varepsilon>0$. For discrete $k$-$\mathsf{median}$ in $\ell_{1}$ and
discrete $k$-$\mathsf{means}$ in $\ell_{2}$, there is a family of well-
separated instances where the SDP relaxation has a gap of at least
$149/125-\varepsilon\approx 1.192-\varepsilon$, even when the integral
solution opens $\Omega(k)$ more centers.

###  1.2 Organization of the Paper

The paper is organized as follows. In Section 2, we introduce some notations
that are used throughout the paper, and some tools from coding theory. In
Section 3, we introduce $\mathsf{JCH}$, and show how it implies the
inapproximability of $k$-$\mathsf{means}$ and $k$-$\mathsf{median}$ in various
$\ell_{p}$-metrics (i.e., Theorems 1.3 and 1.4). In Section 4 we prove a weak
version of $\mathsf{JCH}$. In Section 5 we present some open problems of
interest.

##  2 Preliminaries

##### Notations.

For any two points $a,b\in\mathbb{R}^{d}$, the distance between them in the
$\ell_{p}$-metric is denoted by
$\|a-b\|_{p}~{}=~{}\left(\sum_{i=1}^{d}|a_{i}-b_{i}|^{p}\right)^{1/p}$. Their
distance in the $\ell_{\infty}$-metric is denoted by
$\|a-b\|_{\infty}=\underset{{i\in[d]}}{\max}\ \\{|a_{i}-b_{i}|\\}$, and in the
$\ell_{0}$-metric is denoted by $\|a-b\|_{0}=|\\{i\in[d]:a_{i}\neq b_{i}\\}|$,
i.e., the number of coordinates on which $a$ and $b$ differ. For every
$n\in\mathbb{N}$, we denote by $[n]$ the set of first $n$ natural numbers,
i.e., $\\{1,\ldots,n\\}$. We denote by $\binom{[n]}{r}$, the set of all
subsets of $[n]$ of size $r$. Let $e_{i}$ denote the vector which is 1 on
coordinate $i$ and 0 everywhere else. We denote by
$\left(\vec{\frac{1}{2}}\right)$, the vector that is $\nicefrac{{1}}{{2}}$ on
all coordinates.

##### Clustering Objectives.

Given two sets of points $P$ and $C$ in a metric space, we define the
$k$-$\mathsf{means}$ cost of $P$ for $C$ to be $\underset{p\in
P}{\sum}\left(\underset{c\in C}{\min}\
\left(\text{dist}(p,c)\right)^{2}\right)$ and the $k$-$\mathsf{median}$ cost
to be $\underset{p\in P}{\sum}\left(\underset{c\in C}{\min}\
\text{dist}(p,c)\right)$. Given a set of points $P$ in a metric space and
partition $\pi$ of $P$ into
$P_{1}\dot{\cup}P_{2}\dot{\cup}\cdots\dot{\cup}P_{k}$, we define the
$k$-$\mathsf{minsum}$ cost of $P$ for $\pi$ to be
$\underset{i\in[k]}{\sum}\left(\underset{p,q\in P_{i}}{\sum}\
\text{dist}(p,q)\right)$. Given a set of points $P$, the
$k$-$\mathsf{means}$/$k$-$\mathsf{median}$ (resp. $k$-$\mathsf{minsum}$)
objective is the minimum over all $C$ (resp. $\pi$) of cardinality $k$ of the
$k$-$\mathsf{means}$/$k$-$\mathsf{median}$ (resp. $k$-$\mathsf{minsum}$) cost
of $P$ for $C$ (resp. $\pi$). Given a point $p\in P$, the contribution to the
$k$-$\mathsf{means}$ (resp. $k$-$\mathsf{median}$) cost of $p$ is
$\underset{c\in C}{\min}\left(\text{dist}(p,c)\right)^{2}$ (resp.
$\underset{c\in C}{\min}\ \text{dist}(p,c)$).

##### Error Correcting Codes.

We recall here a few coding theoretic notations. An error correcting code of
block length $\ell$ over alphabet set $\Sigma$ is simply a collection of
codewords $\mathcal{C}\subseteq\Sigma^{\ell}$. The relative distance between
any two points is the fraction of coordinates on which they are different. The
relative distance of the code $\mathcal{C}$ is defined to be the smallest
relative distance between any pair of distinct codewords in $\mathcal{C}$. The
message length of $\mathcal{C}$ is defined to be
$\log_{|\Sigma|}|\mathcal{C}|$. The rate of $\mathcal{C}$ is defined as the
ratio of its message length and block length.

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

For every prime square $q$ greater than 49, there is a code family denoted by
$\mathsf{AG}$ over alphabet of size $q$ of positive constant (depending on
$q$) rate and relative distance at least $1-\frac{3}{\sqrt{q}}$. Moreover, the
encoding time of any code in the family is polynomial in the message length.

An informal argument justifying the existence of the above code family is
provided in [CK19]. Furthermore, as noted in [CK19], random codes obtaining
weaker parameters than the parameters stated above (see Gilbert-Varshamov
bound [Gil52, Var57]) suffice for the results in this paper and it may even be
possible to use concatenated codes (arising from Reed-Solomon codes) which
approach the Gilbert-Varshamov bound in the proofs in this paper instead of
the aforementioned algebraic geometric codes.

##  3 Conditional Inapproximability of $k$-$\mathsf{means}$ and
$k$-$\mathsf{median}$ in $\ell_{p}$-metrics

In this section, we first formally introduce the Johnson Coverage Hypothesis
($\mathsf{JCH}$), then generalize the gadget constructions via graph embedding
which were introduced in [CK19], and finally prove how $\mathsf{JCH}$ implies
the hardness of approximation results for $k$-$\mathsf{means}$ and
$k$-$\mathsf{median}$, i.e., Theorems 1.3 and 1.4. We also prove improved
integrality gaps inspired by $\mathsf{JCH}$ (i.e., Theorem 1.6).

###  3.1 Johnson Coverage Hypothesis

In this subsection, we first introduce the Johnson Coverage problem, followed
by the Johnson Coverage hypothesis.

Let $n,z,y\in\mathbb{N}$ such that $n\geq z>y$. Let $E\subseteq\binom{[n]}{z}$
and $S\in\binom{[n]}{y}$. We define the coverage of $S$ w.r.t. $E$, denoted by
$\mathsf{cov}(S,E)$ as follows:

$\mathsf{cov}(S,E)=\\{T\in E\mid S\subset T\\}.$

######  Definition 3.1 (Johnson Coverage Problem).

In the $(\alpha,z,y)$-Johnson Coverage problem with $z>y\geq 1$, we are given
a universe $U:=[n]$, a collection of subsets of $U$, denoted by
$E\subseteq\binom{[n]}{z}$, and a parameter $k$ as input. We would like to
distinguish between the following two cases:

  * •

_Completeness_ : There exists
$\mathcal{C}:=\\{S_{1},\ldots,S_{k}\\}\subseteq\binom{[n]}{y}$ such that

$\mathsf{cov}(\mathcal{C}):=\underset{i\in[k]}{\cup}\mathsf{cov}(S_{i},E)=E.$

  * •

_Soundness_ : For every
$\mathcal{C}:=\\{S_{1},\ldots,S_{k}\\}\subseteq\binom{[n]}{y}$ we have
${\left|\mathsf{cov}(\mathcal{C})\right|}\leq\alpha\cdot\left|E\right|$.

We call $(\alpha,z,z-1)$-Johnson Coverage as $(\alpha,z)$-Johnson Coverage.

Notice that $(\alpha,2)$-Johnson Coverage Problem is simply the well-studied
vertex coverage problem (with gap $\alpha$). Also, notice that if instead of
picking the collection $\mathcal{C}$ from $\binom{[n]}{y}$, we replace it with
picking the collection $\mathcal{C}$ from $\binom{[n]}{1}$ with a similar
notion of coverage, then we simply obtain the Hypergraph Vertex Coverage
problem (which is equivalent to the Max $k$-Coverage problem for unbounded
$z$).

We now put forward the following hypothesis.

######  Hypothesis 3.2 (Johnson Coverage Hypothesis ($\mathsf{JCH}$)).

For every constant $\varepsilon>0$, there exists a constant
$z:=z(\varepsilon)\in\mathbb{N}$ such that deciding the
$\left(1-\frac{1}{e}+\varepsilon,z\right)$-Johnson Coverage Problem is
$\mathsf{NP}$-Hard.

Since Vertex Coverage problem is a special case of the Johnson Coverage
problem, we have that the $\mathsf{NP}$-Hardness of $(\alpha,z)$-Johnson
Coverage problem is already known for $\alpha=0.94$ [AS19] (under unique games
conjecture).

On the other hand, if we replace picking the collection $\mathcal{C}$ from
$\binom{[n]}{z-1}$ by picking from $\binom{[n]}{1}$, then for the Hypergraph
Vertex Coverage problem, we do know that for every $\varepsilon>0$ there is
some constant $z$ such that the Hypergraph Vertex Coverage problem is
$\mathsf{NP}$-Hard to decide for a factor of
$\left(1-\frac{1}{e}+\varepsilon\right)$ [Fei98].

##### Related work to $\mathsf{JCH}$.

Johnson Coverage problem can be considered as a special case of Max
$k$-Coverage in set systems with a natural additional structure. Such a
restriction of fundamental covering / packing / constraint satisfaction
problems to structured instances often arise in geometric settings such as
Independent Set of Rectangles [CE16]. The VC dimension has been an important
combinatorial notion capturing many implicit structures posed by geometric
problems that allow better algorithms [BG95, BKL12] than general set systems
in some regimes. Recently, Alev et al. [AJT19] studied approximating
constraint satisfaction problems on a high-dimensional expander, another
object that bridges graph theory and geometry, and showed that this structure
makes CSPs easier to approximate.

###  3.2 Gadget Constructions via Graph Embeddings

In this subsection, we recall a notion of graph embedding that was introduced
in [CK19]. And then we prove some bounds on the embedding for important
$\ell_{p}$-metrics. These embedding are then used in the next subsection to
prove inapproximability results.

Let $q,t,r\in\mathbb{N}$ such that $q\geq t\geq r$. Let $J(q,t,r)$ denote the
incidence graph of the Johnson graph [HS93]. Elaborating, we define $J(q,t,r)$
to be the bipartite graph on partite sets $\binom{[q]}{t}$ and
$\binom{[q]}{r}$ where we have an edge
$(S,S^{\prime})\in\binom{[q]}{t}\times\binom{[q]}{r}$ in $J(q,t,r)$ if and
only if $S^{\prime}\subseteq S$. We use the shorthand $J(q,t)$ to denote
$J(q,t,t-1)$.

We would like to analyze the embedding of $J(q,t)$ into $\ell_{p}$-metric
spaces for all $p\in\mathbb{R}_{\geq 1}$.

######  Definition 3.3 (Gap Realization of a Bipartite graph [CK19]).

Let $p\in\mathbb{R}_{\geq 1}$. For any bipartite graph $G=(A\dot{\cup}B,E)$
and $\lambda\geq 1$, a mapping $\tau:V\to\mathbb{R}^{d}$ is said to _$\lambda$
-gap-realize $G$ (in the $\ell_{p}$-metric)_ if for some $\beta>0$, the
following holds:

  1. (i)

For all $(u,v)\in E$, $\|\tau(u)-\tau(v)\|_{p}=\beta$.

  2. (ii)

For all $(u,v)\in(A\times B)\setminus E$, we have
$\|\tau(u)-\tau(v)\|_{p}\geq\lambda\cdot\beta$.

Moreover, we require that $\tau$ $\lambda$-gap-realize $G$ in the
$\ell_{p}$-metric efficiently, i.e., there is a polynomial time algorithm (in
the size of $G$) which can compute $\tau$.

We remark here that the above definition is a variant of the notion gap
contact dimension introduced in [KM20] and is closely related to notion of
contact dimension which has been well-studied in literature since the early
eighties [Pac80, Mae85, FM88, Mae91, DKL19]. We refer the reader to [CK19] for
further discussion.

######  Definition 3.4 (Gap number).

Let $p\in\mathbb{R}_{\geq 1}$. For any bipartite graph $G=(A\dot{\cup}B,E)$,
its gap number in the $\ell_{p}$-metric $g_{p}(G)$ is the largest $\lambda$
for which there exists a mapping $\tau$ that $\lambda$-gap-realizes $G$ in a
$d$-dimensional $\ell_{p}$-metric space888For all the main results of this
paper to hold, we do not require the specified upper bound on the dimension of
the mapping realizing the gap number; any finite dimensional realization
suffices. where $d\leq\text{poly}(|A|+|B|)$.

In [CK19], the authors studied $g_{p}(J(q,t,1))$. In this paper, we are
interested in analyzing $g_{p}(J(q,t,t-1))$ for all $q,t\in\mathbb{N}$ ($q\geq
t$) and $p\in\mathbb{R}_{\geq 1}$. We remark that we do not study
$g_{\infty}(J(q,t,t-1))$ in this paper, as this was already settled to be
equal to 3 in [CK19]. We recall the following upper bound on gap number which
follows immediately from triangle inequality:

######  Proposition 3.5 (Essentially [CK19]).

Let $q\geq 3$, $t\geq 2$ (where $q\geq t$), and $p\in\mathbb{R}_{\geq 1}$. We
have $g_{p}(J(q,t))\leq 3$.

We consider the $\ell_{1}$-metric and show that we can meet the upper bound in
Proposition 3.5.

######  Lemma 3.6.

For all $q\geq 3$ and $t\geq 2$ (where $q\geq t$), we have $g_{1}(J(q,t))=3$.
More generally, $g_{1}(J(q,t,s))=(t-s+2)/(t-s)$.

###### Proof.

For the $\ell_{1}$-metric consider the mapping
$\tau:\binom{[q]}{t}\cup\binom{[q]}{s}\to\\{0,1\\}^{q}$ defined as follows.
For every $S\in\binom{[q]}{t}\cup\binom{[q]}{s}$, we define

$\tau(S)=\sum_{i\in S}e_{i}.$

Fix some $(S,S^{\prime})\in\binom{[q]}{t}\times\binom{[q]}{s}$ such that
$S^{\prime}\subseteq S$. Then we have that

$\tau(S)-\tau(S^{\prime})=\sum_{i\in S\setminus
S^{\prime}}e_{i}\Rightarrow\|\tau(S)-\tau(S^{\prime})\|_{1}=t-s.$

On the other hand if we fix some
$(S,S^{\prime})\in\binom{[q]}{t}\times\binom{[q]}{s}$ such that
$S^{\prime}\not\subset S$ then we have that

$\|\tau(S)-\tau(S^{\prime})\|_{1}=\left\|\left(\sum_{i\in S\setminus
S^{\prime}}e_{i}\right)-\left(\sum_{i\in S^{\prime}\setminus
S}e_{i}\right)\right\|_{1}\geq t-s+2.$

Thus we have that $\tau$, $(t-s+2)/(t-s)$-gap-realizes $J(q,t,s)$ in the
$\ell_{1}$-metric. ∎

Now we focus our attention to bounding the gap number in the Euclidean metric.
First, we see that the below lower bound simply follows from $\tau$
constructed in the above proof.

######  Corollary 3.7.

For all $q\geq 3$ and $t\geq 2$ (where $q\geq t$), we have
$g_{2}(J(q,t))\geq\sqrt{3}$ and $g_{2}(J(q,t))\geq\sqrt{(t-s+2)/(t-s)}$.

However, we improve the lower bound with a different embedding.

######  Lemma 3.8.

For all $q\geq 3$ and $t\geq 2$ (where $q\geq t$), we have
$g_{2}(J(q,t,1))\geq\sqrt{1+\frac{1}{\sqrt{t}-1}}$. More generally,
$g_{2}(J(q,t,s))\geq\sqrt{1+\frac{1}{\sqrt{ts}-s}}$.

###### Proof.

For the $\ell_{2}$-metric consider the mapping
$\tau:\binom{[q]}{t}\cup\binom{[q]}{s}\to\mathbb{R}^{q}$ defined as follows.
For every $T\in\binom{[q]}{t}$, we define

$\tau(T)=\sum_{i\in T}e_{i}.$

For every $S\in\binom{[q]}{s}$, we define

$\tau(S)=\sqrt{\frac{t}{s}}\cdot\sum_{i\in S}e_{i}.$

Fix some $(T,S)\in\binom{[q]}{t}\times\binom{[q]}{s}$ such that $S\subseteq
T$. Then we have that

$\displaystyle\tau(T)-\tau(S)$
$\displaystyle=\left(\left(\sqrt{\frac{t}{s}}-1\right)\cdot\sum_{i\in
S}e_{i}\right)+\left(\sum_{i\in T\setminus S}e_{i}\right)$
$\displaystyle\Rightarrow\|\tau(T)-\tau(S)\|_{2}$
$\displaystyle=\sqrt{s\cdot\left(\sqrt{\frac{t}{s}}-1\right)^{2}+t-s}$
$\displaystyle=\sqrt{2}\cdot\sqrt{t-\sqrt{ts}}$

On the other hand if we fix some $(T,S)\in\binom{[q]}{t}\times\binom{[q]}{s}$
such that $S\not\subset T$ then we have that

$\displaystyle\|\tau(T)-\tau(S)\|_{2}$
$\displaystyle=\left\|\left(\left(\sqrt{\frac{t}{s}}-1\right)\cdot\sum_{i\in
S\cap T}e_{i}\right)+\left(\sqrt{\frac{t}{s}}\cdot\sum_{i\in S\setminus
T}e_{i}\right)+\left(\sum_{i\in T\setminus S}e_{i}\right)\right\|_{2}$
$\displaystyle\geq\sqrt{(s-1)\cdot\left(\sqrt{\frac{t}{s}}-1\right)^{2}+t-s+1+\frac{t}{s}}$
$\displaystyle=\sqrt{2}\cdot\sqrt{t-\sqrt{ts}+\sqrt{\frac{t}{s}}}$
$\displaystyle=\sqrt{2}\cdot\sqrt{(t-\sqrt{ts})\cdot\left(1+\frac{1}{\sqrt{ts}-s}\right)}$

Thus we have that $\tau$, $\sqrt{\left(1+\frac{1}{\sqrt{ts}-s}\right)}$-gap-
realizes $J(q,t,s)$ in the $\ell_{2}$-metric. When $s=1$, $\tau$
$\sqrt{\left(1+\frac{1}{\sqrt{t}-1}\right)}$-gap-realizes $J(q,t,1)$ in the
$\ell_{2}$-metric. ∎

In order to see that the lower bound on $g_{2}(J(q,t,s))$ given in Lemma 3.8
is indeed higher than the one given in Corollary 3.7, note the following:

$\displaystyle\left(1+\frac{1}{\sqrt{ts}-s}\right)-\left(\frac{t-s+2}{t-s}\right)$
$\displaystyle=\frac{1}{\sqrt{ts}-s}-\frac{2}{t-s}=\frac{t-s-2\sqrt{ts}+2s}{(\sqrt{ts}-s)(t-s)}=\frac{(\sqrt{t}-\sqrt{s})^{2}}{(\sqrt{ts}-s)(t-s)}>0,$

as $t>s$.

We wrap up our computation of gap numbers by showing that as $p$ grows the gap
number of $J(q,t)$ in the $\ell_{p}$-metric approaches 3.

######  Lemma 3.9.

For all $q\geq 3$ and $t\geq 2$ (where $q\geq t$), we have that for every
$\varepsilon>0$ there exists $p\in\mathbb{N}$ such that
$g_{p}(J(q,t))>3-\varepsilon$.

###### Proof.

Fix $q\geq 3$, $t\geq 2$, and $\varepsilon>0$. Let $p\in\mathbb{N}$ such that
$q^{1/p}<1+\nicefrac{{\varepsilon}}{{3}}$. Consider the mapping
$\tau:\binom{[q]}{t}\cup\binom{[q]}{t-1}\to\mathbb{R}^{q}$ defined as follows.
For every $S\in\binom{[q]}{t-1}$, we define

$\tau(S)=\left(\vec{\frac{1}{2}}\right)+\sum_{i\in S}e_{i},$

and for every $T\in\binom{[q]}{t}$, we define

$\tau(T)=\sum_{i\in T}e_{i}.$

Fix some $(S,T)\in\binom{[q]}{t-1}\times\binom{[q]}{t}$ such that $S\subset
T$. Then we have that

$\eta:=\tau(T)-\tau(S)=\left(\sum_{i\in T\setminus
S}e_{i}\right)-\left(\vec{\frac{1}{2}}\right).$

Since $\eta\in\\{\nicefrac{{-1}}{{2}},\nicefrac{{1}}{{2}}\\}^{q}$, we have
that $\|\eta\|_{p}=\|\tau(T)-\tau(S)\|_{p}=\nicefrac{{q^{1/p}}}{{2}}$.

On the other hand if we fix some
$(S,T)\in\binom{[q]}{t-1}\times\binom{[q]}{t}$ such that $S\not\subset T$,
i.e., $\exists u\in[q]$ such that $u\in S\setminus T$ then we have that

$\|\tau(T)-\tau(S)\|_{p}\geq|(\tau(T))_{u}-(\tau(S))_{u}|=\frac{3}{2}.$

Thus we have that $\tau$, $\left(\frac{3}{q^{1/p}}\right)$-gap-realizes
$J(q,t)$ in the $\ell_{p}$-metric. Finally note that
$\frac{3}{q^{1/p}}>\frac{9}{3+\varepsilon}=3-\frac{3\varepsilon}{3+\varepsilon}>3-\varepsilon$.
∎

We remark that the embeddings given in Lemmas 3.6 and 3.9 are essentially
small modifications of the ones given in [CK19].

For the sake of compactness of statements in the future, we introduce the
following.

######  Definition 3.10.

For all $p\in\mathbb{R}_{\geq 1}$, we define
$\gamma_{p}=\underset{\begin{subarray}{c}q\geq t\end{subarray}}{\inf}\
g_{p}(J(q,t))$, and $\gamma_{p,\Delta}=\underset{\begin{subarray}{c}q\geq
t\geq\Delta+1\end{subarray}}{\inf}\ g_{p}(J(q,t,t-\Delta))$

Finally, we conclude this subsection by recalling the following ‘hereditary’
property of the embedding which is important for applications to hardness of
approximation.

######  Proposition 3.11 ([CK19]).

Let $q\geq 3$ and $t\geq 2$ (where $q\geq t$), and $p\in\mathbb{R}_{\geq 1}$.
Let $E\subseteq\binom{[q]}{t}$ and $G$ be the subgraph of $J(q,t)$ induced by
the vertex set $E\cup\binom{[q]}{t-1}$. Let $\tau$ be a $\lambda$-gap
realization of $J(q,t)$ in the $\ell_{p}$-metric. Then $\tau$ restricted to
the vertices of $G$ is a $\lambda$-gap realization of $G$ in the
$\ell_{p}$-metric.

###  3.3 Conditional Inapproximability of Discrete $k$-$\mathsf{means}$ and
$k$-$\mathsf{median}$

In this subsection, we show how $\mathsf{JCH}$ or any hardness of
$(\alpha,z,y)$-Johnson Coverage implies the hardness of approximation of the
discrete case of $k$-$\mathsf{means}$ and $k$-$\mathsf{median}$ in all
$\ell_{p}$-metrics, i.e., we prove Theorem 1.3.

First, we define for every $p\in\mathbb{R}_{\geq 1}$,the quantities
$\zeta_{1}(p,\Delta,\alpha)$ and $\zeta_{2}(p,\Delta,\alpha)$ as follows:

$\zeta_{1}(p,\Delta,\alpha):=1+(1-\alpha)(\gamma_{p,\Delta}-1)\text{\ \ and \
\ }\zeta_{2}(p,\Delta,\alpha):=1+(1-\alpha)(\gamma_{p,\Delta}^{2}-1).$

Also let $\zeta_{1}(p):=\zeta_{1}(p,1,1-1/e)$ and
$\zeta_{2}(p):=\zeta_{2}(p,1,1-1/e)$. Notice that $\zeta_{1}(1)\approx 1.73$,
$\zeta_{2}(1)=3.94$, $\zeta_{1}(2)\approx 1.27$, $\zeta_{2}(2)\approx 1.73$,
and as $p\rightarrow\infty$, we have $\zeta_{1}(p)\rightarrow\zeta_{1}(1)$ and
$\zeta_{2}(p)\rightarrow\zeta_{2}(1)$.

Now, we state our inapproximability results for $k$-$\mathsf{means}$ and
$k$-$\mathsf{median}$.

######  Theorem 3.12 ($k$-$\mathsf{means}$ with candidate centers in $O(\log
n)$ dimensional $\ell_{p}$-metric space).

Let $p\in\mathbb{R}_{\geq 1}$. Assuming $(\alpha,z,y)$-Johnson Coverage is NP-
hard, for every constant $\varepsilon>0$, given a point-set
$\mathcal{P}\subset\mathbb{R}^{d}$ of size $n$ (and $d=O(\log n)$), a
collection $\mathcal{C}$ of $m$ candidate centers in $\mathbb{R}^{d}$ (where
$m=\text{poly}(n)$), and a parameter $k$ as input, it is $\mathsf{NP}$-Hard to
distinguish between the following two cases:

  * •

_Completeness_ : There exists
$\mathcal{C}^{\prime}:=\\{c_{1},\ldots,c_{k}\\}\subseteq\mathcal{C}$ and
$\sigma:\mathcal{P}\to\mathcal{C}^{\prime}$ such that

$\sum_{a\in\mathcal{P}}\|a-\sigma(a)\|_{p}^{2}\leq\rho n(\log n)^{2/p},$

  * •

_Soundness_ : For every
$\mathcal{C}^{\prime}:=\\{c_{1},\ldots,c_{k}\\}\subseteq\mathcal{C}$ and every
$\sigma:\mathcal{P}\to\mathcal{C}^{\prime}$ we have:

$\sum_{a\in\mathcal{P}}\|a-\sigma(a)\|_{p}^{2}\geq(\zeta_{2}(p,z-y,\alpha)-\varepsilon)\cdot\rho
n(\log n)^{2/p},$

for some constant $\rho>0$.

In particular, assuming $\mathsf{JCH}$, $k$-$\mathsf{means}$ is
$\mathsf{NP}$-Hard to approximate within a factor $\zeta_{2}(p)$, which is at
least $3.94$ in $\ell_{1}$ and at least $1.73$ in $\ell_{2}$.

######  Theorem 3.13 ($k$-$\mathsf{median}$ with candidate centers in $O(\log
n)$ dimensional $\ell_{p}$-metric space).

Let $p\in\mathbb{R}_{\geq 1}$. Assuming $(\alpha,z,y)$-Johnson Coverage is
$\mathsf{NP}$-Hard, for every constant $\varepsilon>0$, given a point-set
$\mathcal{P}\subset\mathbb{R}^{d}$ of size $n$ (and $d=O(\log n)$), a
collection $\mathcal{C}$ of $m$ candidate centers in $\mathbb{R}^{d}$ (where
$m=\text{poly}(n)$), and a parameter $k$ as input, it is $\mathsf{NP}$-Hard to
distinguish between the following two cases:

  * •

_Completeness_ : There exists
$\mathcal{C}^{\prime}:=\\{c_{1},\ldots,c_{k}\\}\subseteq\mathcal{C}$ and
$\sigma:\mathcal{P}\to\mathcal{C}^{\prime}$ such that

$\sum_{a\in\mathcal{P}}\|a-\sigma(a)\|_{p}\leq\rho n(\log n)^{1/p},$

  * •

_Soundness_ : For every
$\mathcal{C}^{\prime}:=\\{c_{1},\ldots,c_{k}\\}\subseteq\mathcal{C}$ and every
$\sigma:\mathcal{P}\to\mathcal{C}^{\prime}$ we have:

$\sum_{a\in\mathcal{P}}\|a-\sigma(a)\|_{p}\geq(\zeta_{1}(p,z-y,\alpha)-\varepsilon)\cdot\rho
n(\log n)^{1/p},$

for some constant $\rho>0$.

In particular, assuming $\mathsf{JCH}$, $k$-$\mathsf{median}$ is
$\mathsf{NP}$-Hard to approximate within a factor $\zeta_{2}(p)$, which is at
least $1.73$ in $\ell_{1}$ and at least $1.27$ in $\ell_{2}$.

######  Remark 3.14.

Notice that for every $q,z,$ and $p$, from the embedding given by Lemma 3.6,
we can deduce that $g_{p}(J(q,z,1))$ is a constant (depending on $q,z,$ and
$p$) bounded away from 1. Thus we have for $i\in\\{1,2\\}$ that
$\zeta_{i}(p,z-1,\alpha)\geq 1+\delta$ for some positive constant $\delta$
depending only on $p,\alpha,$ and $z$. On the other hand, Feige [Fei98] showed
that for any constant $\varepsilon>0$ there is a constant $z:=z(\varepsilon)$
such that $(1-\nicefrac{{1}}{{e}}+\varepsilon,z,1)$-Johnson Coverage problem
is $\mathsf{NP}$-Hard. Plugging these parameters in Theorems 3.12 and 3.13, we
have that $k$-$\mathsf{means}$ and $k$-$\mathsf{median}$ are
$\mathsf{APX}$-Hard in all $\ell_{p}$-metrics. In fact, we do not even need to
invoke the tight result of [Fei98], as it’s relatively easy to show that
$(1-\delta,z,1)$-Johnson Coverage problem is $\mathsf{NP}$-Hard directly from
the PCP theorem [AS98, ALM+98, Din07] for some constants $\delta>0$ and
$z\in\mathbb{N}$.

The proof of the above two theorems follows by generalizing the embedding
framework established in [CK19]. In [CK19], the authors considered a two-
player communication game between Alice and Bob, where Alice holds as input an
edge in a publicly known graph and Bob holds as input a vertex in the same
graph, and the goal is for Bob to send a message to Alice (using public
randomness), so that Alice can decide if her edge is incident on Bob’s vertex.
The authors then showed how an efficient randomized protocol for this
communication problem can be combined with a certain embedding of the complete
graph (into $\ell_{p}$-metrics) to obtain inapproximaility results for
$k$-$\mathsf{means}$ and $k$-$\mathsf{median}$ in $\ell_{p}$-metrics.

Below we consider the game where Alice holds a $z$-sized subset of $[n]$ and
Bob holds a $y$-sized subset of $[n]$, and the goal is for Bob to send a
message to Alice (using public randomness), so that Alice can decide if her
subset completely contains Bob’s subset. We then design an efficient
randomized protocol for this communication problem using Algebraic Geometric
codes (as in [CK19]) and show how the transcript of the protocol can be
combined with a certain embedding of the Johnson graph (into
$\ell_{p}$-metrics) to obtain the two theorems. We skip providing further
details about the framework for the sake of brevity, and point the reader to
[CK19].

###### Proof of Theorems 3.12 and 3.13.

Fix $\varepsilon>0$ as in the theorem statement. Also, fix
$p\in\mathbb{R}_{\geq 1}$. Let $\varepsilon^{\prime}:=\varepsilon/11$ (setting
$\varepsilon^{\prime}$ to be $\varepsilon/4$ suffices for Theorem 3.13).
Starting from a hard instance of $\left(\alpha,z,y\right)$-Johnson Coverage
problem $(U,E,k)$, we create an instance of the $k$-$\mathsf{means}$, or of
the $k$-$\mathsf{median}$ problem using Algebraic-Geometric codes and the
embedding given in Proposition 3.11 as follows. Let $q$ be a (constant) prime
square greater than $\left(\frac{18z^{2}}{\varepsilon^{\prime}}\right)^{2}$.
Let $\mathsf{AG}$ be the code guaranteed by Theorem 2.1 over alphabet of size
$q$ of message length $\eta:=\log_{q}n$ (recall $|U|=n$), block length
$\ell:=O_{q}(\eta)$, and relative distance at least
$1-\nicefrac{{3}}{{\sqrt{q}}}$. Let $\tau$ be a $g_{p}(J(q,z,y))$-gap
realization embedding of $J(q,z,y)$ which maps vertices of $J(q,z,y)$ to a
$d^{*}$-dimensional space (note that $q$, $z$, and $y$ are all constants, and
thus so is $d^{*}$). Let $\beta>0$ be the constant from Definition 3.3.

##### Construction.

The $k$-$\mathsf{median}$ or $k$-$\mathsf{means}$ instance consists of the set
of candidate centers $\mathcal{C}\subseteq\mathbb{R}^{\ell\cdot d^{*}}$ and
the set of points to be clustered $\mathcal{P}\subseteq\mathbb{R}^{\ell\cdot
d^{*}}$ which will be defined below. First, we define functions
$A_{E}:E\times[\ell]\to\binom{[q]}{z}\cup\\{\perp\\}$ and
$A_{F}:\binom{[n]}{y}\times[\ell]\to\binom{[q]}{y}\cup\\{\perp\\}$ below.
Then, we will construct functions
$\widetilde{A}_{E}:E\to\mathbb{R}^{d^{*}\cdot\ell}$ and
$\widetilde{A}_{F}:\binom{[n]}{y}\to\mathbb{R}^{d^{*}\cdot\ell}$. Given
$\widetilde{A}_{E}$ and $\widetilde{A}_{F}$ the point-set $\mathcal{P}$ is
just defined to be

$\left\\{\widetilde{A}_{E}(T)\big{|}T\in E\right\\},$

and the set of candidate centers $\mathcal{C}$ is just defined to be

$\left\\{\widetilde{A}_{F}(S)\Big{|}S\in\binom{[n]}{y}\right\\}.$

For every $\gamma\in[\ell]$ and every $S\in\binom{[n]}{y}$, we define
$R_{S,\gamma}^{y}\subseteq[q]$, where $\mu\in[q]$ is contained in
$R_{S,\gamma}^{y}$ if and only if there exists some $u\in S$ such that999Here
we think of $\gamma$ as a field element of $\mathbb{F}_{q}$ by using some
canonical bijection between $[q]$ and $\mathbb{F}_{q}$.
$\mathsf{AG}(u)_{\gamma}=\mu$. Then, we define
$A_{F}(S,\gamma)=R_{S,\gamma}^{y}$ if $|R_{S,\gamma}^{y}|=y$ and
$A_{F}(S,\gamma)=\perp$ otherwise. Similarly, for every $\gamma\in[\ell]$ and
every $T\in E\subseteq\binom{[n]}{z}$ we define
$R_{T,\gamma}^{z}\subseteq[q]$, where $\mu\in[q]$ is contained in
$R_{T,\gamma}$ if and only if there exists some $u\in T$ such that
$\mathsf{AG}(u)_{\gamma}=\mu$. Then, we define
$A_{E}(T,\gamma)=R_{T,\gamma}^{z}$ if $|R_{T,\gamma}^{z}|=z$ and
$A_{E}(T,\gamma)=\perp$ otherwise.

For every $x,y\in[q]$ such that $x<x^{\prime}$ we define
$\Lambda_{x,x^{\prime}}:\binom{[q]}{x}\to\binom{[q]}{x^{\prime}}$ as follows:
For every $X\in\binom{[q]}{x}$ define $\Delta_{X}$ to be the set of
$(x^{\prime}-x)$ many smallest integers in $[q]$ not contained in $X$. Then
$\Lambda_{x,x^{\prime}}(X)=X\cup\Delta_{X}$. Now we can construct functions
$\widetilde{A}_{E}:E\to\mathbb{R}^{d^{*}\cdot\ell}$ and
$\widetilde{A}_{F}:\binom{[n]}{x^{\prime}}\to\mathbb{R}^{d^{*}\cdot\ell}$ as
follows:

$\forall\gamma\in[\ell],\
\widetilde{A}_{E}(T)\lvert_{\gamma}=\begin{cases}\tau(A_{E}(T,\gamma))\text{
if }A_{E}(T,\gamma)\neq\perp\\\
\tau(\Lambda_{|R_{T,\gamma}^{z}|,z}(R_{T,\gamma}^{z}))\text{
otherwise}\end{cases}$ $\text{ and }\ \ \
\widetilde{A}_{F}(S)\lvert_{\gamma}=\begin{cases}\tau(A_{F}(S,\gamma))\text{
if }A_{F}(S,\gamma)\neq\perp\\\
\tau(\Lambda_{|R_{S,\gamma}^{x^{\prime}}|,x^{\prime}}(R_{S,\gamma}^{x^{\prime}}))\text{
otherwise}\end{cases}.$

##### Structural Observations.

Fix $S\in\binom{[n]}{y}$. We define the set $L_{S}^{y}$ as follows:

$L_{S}^{y}:=\\{\gamma\in[\ell]:|R_{S,\gamma}^{y}|=y\\}.$

Consider the set $W_{S}=\\{\mathsf{AG}(u)\mid u\in S\\}$. Since any two
codewords of $\mathsf{AG}$ agree on at most $3/\sqrt{q}$ fraction of
coordinates, we have by union bound that there are at least
$1-\binom{y}{2}(3/\sqrt{q})$ fraction of coordinates of $[\ell]$ on which all
codewords in $W_{S}$ are distinct. Therefore, we have that
$|L_{S}^{y}|\geq(1-\binom{y}{2}(3/\sqrt{q}))\cdot\ell$. Also, note that for
all $\gamma\in L_{S}^{y}$ we have $A_{F}(S,\gamma)\neq\perp$.

Similarly, we fix $T\in E$. We define the set $L_{T}^{z}$ as follows:

$L_{T}^{z}:=\\{\gamma\in[\ell]:|R_{T,\gamma}^{z}|=z\\}.$

By following the averaging argument above, we also have that
$|L_{T}^{z}|\geq(1-\binom{z}{2}(3/\sqrt{q}))\cdot\ell$. Again, note that for
all $\gamma\in L_{T}^{z}$ we have $A_{E}(T,\gamma)\neq\perp$.

Finally, for every $(S,T)\in\binom{[n]}{y}\times E$, we define
$L_{S,T}:=L_{S}^{y}\cap L_{T}^{z}$, and note the following

$|L_{S,T}|\geq\left(1-\frac{3zy}{\sqrt{q}}\right)\cdot\ell.$

Let us now compute a few distances. Consider $(S,T)\in\binom{[n]}{y}\times E$
such that $S\subset T$ then we have

$\displaystyle\|\widetilde{A}_{E}(T)-\widetilde{A}_{F}(S)\|_{p}=\beta\cdot\ell^{1/p}.$
(1)

This is because, if $S\subset T$ then for all $\gamma\in[\ell]$ we have
$R_{S,\gamma}^{y}\subseteq R_{T,\gamma}^{z}$. Fix $\gamma\in[\ell]$. If
$\gamma\in L_{S,T}$ then we have that
$\|\widetilde{A}_{E}(T)|_{\gamma}-\widetilde{A}_{F}(S)|_{\gamma}\|_{p}^{p}=\beta^{p}$
as $(R_{S,\gamma}^{y},R_{T,\gamma}^{z})$ is an edge in $J(q,z)$. On the other
hand if $\gamma\notin L_{T}^{z}$ then either $\gamma\notin L_{S}^{y}$ and we
have that
$\Lambda_{|R_{S,\gamma}^{y}|,y}(R_{S,\gamma}^{y})\subseteq\Lambda_{|R_{T,\gamma}^{z}|,z}(R_{T,\gamma}^{z})$
because $R_{S,\gamma}^{y}\subseteq R_{T,\gamma}^{z}$, or we have $\gamma\in
L_{S}^{y}$, in which case, we have $R_{T,\gamma}^{z}=R_{S,\gamma}^{y}$ and
thus
$R_{S,\gamma}^{y}\subseteq\Lambda_{|R_{T,\gamma}^{z}|,z}(R_{T,\gamma}^{z})$.
In the former case, we have that
$(\Lambda_{|R_{S,\gamma}^{y}|,y}(R_{S,\gamma}^{y}),\Lambda_{|R_{T,\gamma}^{z}|,z}(R_{T,\gamma}^{z}))$
is an edge in $J(q,z)$ and in the latter case we have that
$(R_{S,\gamma}^{y},\Lambda_{|R_{T,\gamma}^{z}|,z}(R_{T,\gamma}^{z}))$ is an
edge in $J(q,z)$. The final result in both cases is that
$\|\widetilde{A}_{E}(T)|_{\gamma}-\widetilde{A}_{F}(S)|_{\gamma}\|_{p}^{p}=\beta^{p}$.
Therefore, we have

$\sum_{\gamma\in[\ell]}\|\widetilde{A}_{E}(T)|_{\gamma}-\widetilde{A}_{F}(S)|_{\gamma}\|_{p}^{p}=\|\widetilde{A}_{E}(T)-\widetilde{A}_{F}(S)\|_{p}^{p}=\beta^{p}\cdot\ell.$

Consider $(S,T)\in\binom{[n]}{y}\times E$ such that $S\not\subset T$. Let
$u\in U$ such that $u\in S$ but $u\notin T$. We define
$\mathsf{Good}:=\\{\gamma\in[\ell]:\mathsf{AG}(u)_{\gamma}\notin
R_{T,\gamma}^{z}\\}$. Since the relative distance of $\mathsf{AG}$ is
$1-\nicefrac{{3}}{{\sqrt{q}}}$, we have by simple union bound that

$|\mathsf{Good}|\geq\left(1-\frac{3z}{\sqrt{q}}\right)\cdot\ell.$

Then, we have

$\displaystyle\|\widetilde{A}_{E}(T)-\widetilde{A}_{F}(S)\|_{p}\geq(g_{p}(J(q,y,z))-\delta)\cdot\beta\cdot\ell^{1/p},$
(2)

where $\delta:=\frac{18zy}{\sqrt{q}}$ (note that
$\delta\leq\varepsilon^{\prime}$). To see this first observe that:

$\|\widetilde{A}_{E}(T)-\widetilde{A}_{F}(S)\|_{p}^{p}\geq\sum_{\gamma\in
L_{S,T}\cap\mathsf{Good}}\|\widetilde{A}_{E}(T)|_{\gamma}-\widetilde{A}_{F}(S)|_{\gamma}\|_{p}^{p}.$

Fix $\gamma\in L_{S,T}\cap\mathsf{Good}$. Notice that
$R_{S,\gamma}^{y}\not\subset R_{T,\gamma}^{z}$ and thus
$(R_{S,\gamma}^{y},R_{T,\gamma}^{z})$ is not an edge in $J(q,z)$. Therefore,
we have

$\|\widetilde{A}_{E}(T)|_{\gamma}-\widetilde{A}_{F}(S)|_{\gamma}\|_{p}^{p}\geq
g_{p}(J(q,z,y))^{p}\cdot\beta^{p}.$

Since
$|L_{S,T}\cap\mathsf{Good}|\geq\left(1-\nicefrac{{3z}}{{\sqrt{q}}}-\nicefrac{{3zy}}{{\sqrt{q}}}\right)\cdot\ell\geq\left(1-\nicefrac{{6zy}}{{\sqrt{q}}}\right)\cdot\ell$,
(2) follows immediately by noting that (i) $g_{p}(J(q,z,y))\leq 3$, and (ii)
for any $\eta\in[0,1]$, $(1-\eta)^{1/p}\geq(1-\eta)$.

We now analyze the $k$-$\mathsf{means}$ and $k$-$\mathsf{median}$ cost of the
instance. Consider the completeness case first.

##### Completeness.

Suppose there exist $S_{1},\ldots,S_{k}\in\binom{[n]}{y}$ such that
$\underset{i\in[k]}{\bigcup}\mathsf{cov}(S_{i},E)=E$. Then, we define
$\mathcal{C}^{\prime}=\\{\widetilde{A}_{F}(S_{i})\mid i\in[k]\\}$ and we
define $\sigma:\mathcal{P}\to\mathcal{C}^{\prime}$ as follows: for every
$a\in\mathcal{P}$, where $a:=\widetilde{A}_{E}(T)$ for some $T\in E$, let
$\sigma(a)$ be equal to $\widetilde{A}_{F}(S_{i})$ such that $S_{i}\subset T$
(if there is more than one $i\in[k]$ for which $S_{i}$ is contained in $T$
then we choose one arbitrarily). Therefore for any $a\in\mathcal{P}$ we have
from (1)

$\displaystyle\|a-\sigma(a)\|_{p}=\beta\cdot\ell^{1/p}.$

The $k$-$\mathsf{means}$ cost of the overall instance is thus
$\beta^{2}\cdot\ell^{2/p}\cdot|\mathcal{P}|$, while the $k$-$\mathsf{median}$
cost is $\beta\cdot\ell^{1/p}\cdot|\mathcal{P}|$. Finally, we turn to the
soundness analysis.

##### Soundness.

Consider any set of centers
$\mathcal{C}^{\prime}=\\{c_{1},\ldots,c_{k}\\}\subset\mathcal{C}$ that is
optimal for the $k$-$\mathsf{median}$ or $k$-$\mathsf{means}$ objective (and
that $\sigma:\mathcal{P}\to\mathcal{C}^{\prime}$ simply maps to the closest
center in $\mathcal{C}^{\prime}$). Let
$\mathcal{S}:=\\{S_{1},\ldots,S_{k}\\}\subseteq\binom{[n]}{y}$ be the
collection of $y$ sized subsets of $U$ corresponding to the centers of
$\mathcal{C}^{\prime}$, namely

$\mathcal{S}=\left\\{S_{i}\in\binom{[n]}{y}\Big{|}\widetilde{A}_{F}(S_{i})\in\mathcal{C}^{\prime}\right\\}.$

By the assumptions of the soundness case, we have
$\mathsf{cov}(\mathcal{S})\leq\alpha\cdot|E|$. For each
$T\in\mathsf{cov}(\mathcal{S})$, from (1), we have that the contribution of
$\widetilde{A}_{E}(T)$ to the $k$-$\mathsf{means}$ cost is exactly
$\beta^{2}\cdot\ell^{2/p}$, and to the $k$-$\mathsf{median}$ cost is exactly
$\beta\cdot\ell^{1/p}$. However, from (2), for any other $T\in
E\setminus\mathsf{cov}(\mathcal{S})$, the contribution of
$\widetilde{A}_{E}(T)$ to the $k$-$\mathsf{median}$ and $k$-$\mathsf{means}$
cost is (at least) respectively
$(g_{p}(J(q,y,z))-\delta)\cdot\beta\cdot\ell^{1/p}$ and
$(g_{p}(J(q,y,z))-\delta)^{2}\cdot\beta^{2}\cdot\ell^{2/p}$. Therefore, the
optimal solution w.r.t. $k$-$\mathsf{median}$ objective has cost at least:

$\displaystyle\alpha\cdot|E|\cdot\beta\cdot\ell^{1/p}+\left(1-\alpha\right)\cdot|E|\cdot(\gamma_{p,z-y}-\delta)\cdot\beta\cdot\ell^{1/p}$
$\displaystyle\geq|\mathcal{P}|\cdot\beta\cdot\ell^{1/p}\cdot\left(\zeta_{1}(p,z-y,\alpha)-\delta\right)$
$\displaystyle\geq|\mathcal{P}|\cdot\beta\cdot\ell^{1/p}\cdot\left(\zeta_{1}(p,z-y,\alpha)-\varepsilon\right).$

Similarly, the optimal solution w.r.t. $k$-$\mathsf{means}$ objective has cost
at least:

$\displaystyle\alpha\cdot|E|\cdot\beta^{2}\cdot\ell^{2/p}+\left(1-\alpha\right)\cdot|E|\cdot(\gamma_{p,z-y}-\delta)^{2}\cdot\beta^{2}\cdot\ell^{2/p}$
$\displaystyle\geq|\mathcal{P}|\cdot\beta^{2}\cdot\ell^{2/p}\cdot\left(\zeta_{2}(p,z-y,\alpha)-2\delta\right)$
$\displaystyle\geq|\mathcal{P}|\cdot\beta^{2}\cdot\ell^{2/p}\cdot\left(\zeta_{2}(p,z-y,\alpha)-\varepsilon\right).$

∎

We remark that the above proof can be made significantly notation-light, if we
wanted to prove Theorem 1.3 in high dimensions (i.e., $\text{poly}(n)$
dimensions). In particular, we could skip the use of Algebraic Geometric
codes. However, the result is more interesting when the dimension is $O(\log
n)$, as proving the same $\mathsf{NP}$-Hardness for $(\log n)^{1-o(1)}$
dimensions would violate the Exponential Time Hypothesis [IP01, IPZ01], due to
the sub-exponential time approximation algorithm of [Coh18] for such
dimensions.

###  3.4 Conditional Inapproximability of Continuous $k$-$\mathsf{means}$ and
$k$-$\mathsf{median}$

In this subsection, we show how $\mathsf{JCH}$ or any hardness of
$(\alpha,z,y)$-Johnson Coverage implies the hardness of approximation of
various clustering objectives in the continuous case and i.e., we prove
Theorem 1.4. In order to prove the results in this section, we need to assume
a slight strengthening of $\mathsf{JCH}$.

######  Hypothesis 3.15 (Dense Johnson Coverage Hypothesis
($\mathsf{JCH}^{*}$)).

$\mathsf{JCH}$ holds for instances $(U,E,k)$ of Johnson Coverage problem where
$|E|=\omega(k)$.

More generally, let $(\alpha,z,y)$-Johnson Coverage∗ be the special case
$(\alpha,z,y)$-Johnson Coverage where the instances satisfy
$|E|=\omega(k\cdot|U|^{z-y-1})$. Then $\mathsf{JCH}^{*}$ states that for any
$\varepsilon>0$, there exists $z=z(\varepsilon)$ such that
$(1-1/e+\varepsilon,z,z-1)$-Johnson Coverage∗ is $\mathsf{NP}$-Hard. This
additional property has always been obtained in literature by looking at the
hard instances that were constructed. In [CK19], where the authors proved the
previous best inapproximability results for continuous case
$k$-$\mathsf{means}$ and $k$-$\mathsf{median}$, it was observed that hard
instances of $(0.94,2,1)$-Johnson Coverage constructed in [AKS11, AS19] can be
made to satisfy the above property.

First, we consider Euclidean $k$-$\mathsf{means}$.

######  Theorem 3.16 ($k$-$\mathsf{means}$ without candidate centers in
$O(\log n)$ dimensional Euclidean space).

Assume $(\alpha,z,y)$-Johnson Coverage∗ is $\mathsf{NP}$-Hard. For every
constant $\varepsilon>0$, given a point-set $\mathcal{P}\subset\\{0,1\\}^{d}$
of size $n$ (and $d=O(\log n)$) and a parameter $k$ as input, it is
$\mathsf{NP}$-Hard to distinguish between the following two cases:

  * •

_Completeness_ : There exists
$\mathcal{C}^{\prime}:=\\{c_{1},\ldots,c_{k}\\}\subseteq\mathbb{R}^{d}$ and
$\sigma:\mathcal{P}\to\mathcal{C}^{\prime}$ such that

$\sum_{a\in\mathcal{P}}\|a-\sigma(a)\|_{2}^{2}\leq\rho n\log n,$

  * •

_Soundness_ : For every
$\mathcal{C}^{\prime}:=\\{c_{1},\ldots,c_{k}\\}\subseteq\mathcal{C}$ and every
$\sigma:\mathcal{P}\to\mathcal{C}^{\prime}$ we have:

$\sum_{a\in\mathcal{P}}\|a-\sigma(a)\|_{2}^{2}\geq\left(1+\frac{(1-\alpha)}{(z-y)}-\varepsilon\right)\cdot\rho
n\log n,$

for some constant $\rho>0$.

###### Proof.

The construction of the point-set $\mathcal{P}$ in the theorem statement is
the same as in the proof of Theorem 3.12 (with a further simplification as we
fix the embedding given in Lemma 3.8). However, the soundness analysis to
prove the theorem is more intricate.

Fix $\varepsilon>0$ as in the theorem statement. Also, fix
$p\in\mathbb{R}_{\geq 1}$. Let $\varepsilon^{\prime}:=\varepsilon/11$.
Starting from a hard instance of $\left(\alpha,z,y\right)$-Johnson Coverage∗
problem $(U,E,k)$ with $|U|=n$ and $|E|=\omega(n^{z-y})$, we create an
instance of the $k$-$\mathsf{means}$ using Algebraic-Geometric codes and the
embedding given in Lemma 3.8 as follows. Let $q$ be a (constant) prime square
greater than $\left(\frac{18z^{2}}{\varepsilon^{\prime}}\right)^{2}$. Let
$\mathsf{AG}$ be the code guaranteed by Theorem 2.1 over alphabet of size $q$
of message length $\eta:=\log_{q}n$ (recall $|U|=n$), block length
$\ell:=O_{q}(\eta)$, and relative distance at least
$1-\nicefrac{{3}}{{\sqrt{q}}}$.

##### Construction.

The $k$-$\mathsf{means}$ instance consists of the set of points to be
clustered $\mathcal{P}\subseteq\\{0,1\\}^{\ell\cdot q}$ which will be defined
below. Recall the function
$A_{E}:E\times[\ell]\to\binom{[q]}{z}\cup\\{\perp\\}$ defined in the proof of
Theorem 3.12 (also recall the definitions $R_{T,\gamma}^{z}$, $\Lambda_{x,y}$,
$L_{T}^{z},\widetilde{A}_{F}$). We construct
$\widetilde{A}_{E}:E\to\\{0,1\\}^{q\cdot\ell}$ below. Given
$\widetilde{A}_{E}$ the point-set $\mathcal{P}$ is just defined to be

$\left\\{\widetilde{A}_{E}(T)\big{|}T\in E\right\\}.$

Let $\tau$ map a subset of $[q]$ to its characteristic vector in
$\\{0,1\\}^{q}$. Now we can construct $\widetilde{A}_{E}$ as follows:

$\forall\gamma\in[\ell],\
\widetilde{A}_{E}(T)\lvert_{\gamma}=\begin{cases}\tau(A_{E}(T,\gamma))\text{
if }A_{E}(T,\gamma)\neq\perp\\\
\tau(\Lambda_{|R_{T,\gamma}^{z}|,z}(R_{T,\gamma}^{z}))\text{
otherwise}\end{cases}.$

##### Structural Observations.

We compute distances in a couple of cases. Consider distinct $T,T^{\prime}\in
E$ such that $|T\cap T^{\prime}|=y$. Then we have

$\displaystyle(2(z-y)-\delta)\cdot{\ell}\leq\|\widetilde{A}_{E}(T)-\widetilde{A}_{E}(T^{\prime})\|_{2}^{2}\leq{2(z-y)\ell},$
(3)

where $\delta:=18z^{2}/\sqrt{q}$ (note that $\delta\leq\varepsilon^{\prime}$).

Now consider distinct $T,T^{\prime}\in E$ such that $|T\cap T^{\prime}|<y$.
Then we have

$\displaystyle(2(z-y)+2-\delta)\cdot{\ell}\leq\|\widetilde{A}_{E}(T)-\widetilde{A}_{E}(T^{\prime})\|_{2}^{2}.$
(4)

We now analyze the $k$-$\mathsf{means}$ cost of the instance. To do so, we
will make use of the following classic fact about the $k$-means cost of a
partition $C_{1}\dot{\cup}\cdots\dot{\cup}C_{k}=\mathcal{P}$ of a set of
points in $\mathbb{R}^{d}$.

######  Fact 3.17.

Given a clustering $C_{1}\dot{\cup}\cdots\dot{\cup}C_{k}=\mathcal{P}$, the
$k$-$\mathsf{means}$ cost is exactly

$\sum_{i=1}^{k}\frac{1}{2|C_{i}|}\sum_{p\in C_{i}}\sum_{q\in
C_{i}}\|p-q\|^{2}_{2}.$

Consider the completeness case first.

##### Completeness.

Suppose there exist $S_{1},\ldots,S_{k}\in\binom{[n]}{y}$ such that
$\underset{i\in[k]}{\bigcup}\mathsf{cov}(S_{i},E)=E$. Then, we define a
clustering $C_{1}\dot{\cup}\cdots\dot{\cup}C_{k}=\mathcal{P}$ as follows: for
every $a\in\mathcal{P}$, where $a:=\widetilde{A}_{E}(T)$ for some $T\in E$,
let $a\in C_{i}$ such that $T\in\mathsf{cov}(S_{i},E)$ (if there is more than
one $i\in[k]$ for which $S_{i}$ is contained in $T$ then we choose one
arbitrarily). We now provide an upper bound on the $k$-means cost of
clustering $\mathcal{C}:=\\{C_{1},\ldots,C_{k}\\}$. (3) implies that for each
$C_{i}$, for any pair $T,T^{\prime}$ such that
$\widetilde{A}_{E}(T),\widetilde{A}_{E}(T^{\prime})\in C_{i}$, we have that
$||\widetilde{A}_{E}(T)-\widetilde{A}_{E}(T^{\prime})||^{2}_{2}\leq 2\ell$.
Hence, if we let $W_{i}$ be the $k$-$\mathsf{means}$ cost for the $C_{i}$,

$W_{i}=\frac{1}{2|C_{i}|}\sum_{q\in C_{i}}\sum_{p\in
C_{i}}||p-q||^{2}_{2}\leq\frac{1}{2|C_{i}|}\sum_{q\in C_{i}}\sum_{p\in
C_{i},p\neq q}2(z-y)\ell\leq(z-y)|C_{i}|\ell.$

Thus, the cost of clustering $\mathcal{C}$ is at most
$(z-y)\ell|\mathcal{P}|$. Finally, we turn to the soundness analysis.

##### Soundness.

Consider the optimal $k$-means clustering
$\mathcal{C}:=\\{C_{1},\ldots,C_{k}\\}$ of the instance (i.e.,
$C_{1}\dot{\cup}\cdots\dot{\cup}C_{k}=\mathcal{P}$). We aim at showing that
the $k$-means cost of $\mathcal{C}$ is at least
$((z-y)+2(1-\alpha)-o(1))\ell|\mathcal{P}|$. Given a cluster $C_{i}$, let
$E_{i}:=\\{T\in E:\widetilde{A}_{E}(T)\in C_{i}\\}$ be the collection of
$z$-sets of $E$ corresponding to $C_{i}$. For each $S\in{[n]\choose y}$, we
define the _degree of $S$ in $C_{i}$_ to be

$d_{i,S}:=\left|\\{T\mid S\subset T\text{ and }\widetilde{A}_{E}(T)\in
C_{i}\\}\right|.$

Let $t_{0}=(2z-2y-\delta)\ell$, $t_{1}=(2z-2y)\ell$, and
$t_{2}=(2z-2y+2-\delta)\ell$. For each cluster $C_{i}$, let

$\displaystyle F_{i}$ $\displaystyle=\bigg{|}\\{(p,q)\in
C_{i}^{2}:\|p-q\|_{2}^{2}\geq t_{2}\\}\bigg{|}$ $\displaystyle M_{i}$
$\displaystyle=\bigg{|}\\{(p,q)\in
C_{i}^{2}:\|p-q\|_{2}^{2}\in[t_{0},t_{1}]\\}\bigg{|}$ $\displaystyle N_{i}$
$\displaystyle=\bigg{|}\\{(p,q)\in
C_{i}^{2}:\|p-q\|_{2}^{2}<t_{0}\\}\bigg{|}.$

By (3) and (4), $F_{i}$, $M_{i}$, and $N_{i}$ are the number of (ordered)
pairs within $C_{i}$ whose corresponding $z$-sets in the Johnson Coverage
instance intersect in $<y$, $=y$, and $>y$ elements respectively. Let
$\Delta_{i}=\underset{S\in\binom{[n]}{y}}{\max}\ d_{i,S}.$ We write the total
cost of the clustering as follows.

$\displaystyle\sum_{i=1}^{k}W_{i}$ $\displaystyle\geq\quad$
$\displaystyle\sum_{i=1}^{k}\frac{1}{2|C_{i}|}\bigg{(}F_{i}t_{2}+M_{i}t_{0}\bigg{)}$
$\displaystyle=\quad$
$\displaystyle\sum_{i=1}^{k}\frac{1}{2|C_{i}|}\bigg{(}(|C_{i}|^{2}-M_{i})t_{2}+(M_{i})t_{0}-N_{i}t_{2}\bigg{)}$
(5)

We first upper bound $\sum_{i}(N_{i}t_{2})/(2|C_{i}|)$. For each $z$-set $T$,
there are at most $(z-y)\cdot\binom{z}{z-y-1}\cdot n^{z-y-1}$ sets that
intersect with $T$ in at least $y+1$ elements. Therefore,
$N_{i}\leq|C_{i}|\cdot\max(|C_{i}|,O(n^{z-y-1}))$ and

$\sum_{i=1}^{k}\frac{N_{i}}{2|C_{i}|}\leq\sum_{i=1}^{k}\max(|C_{i}|,O(n^{z-y-1}))\leq
O(k\cdot n^{z-y-1})).$

By the definition of Johnson Coverage∗, $|E|=\omega(k\cdot n^{z-y-1})$, so
$\sum_{i}N_{i}t_{2}/(2|C_{i}|)$ is at most $o(\ell|\mathcal{P}|)$.

For $M_{i}$, we prove the following claim that bounds $M_{i}/|C_{i}|$ in terms
of $\Delta_{i}$ and $|C_{i}|$.

######  Claim 3.18.

For every $i\in[k]$, either $|C_{i}|=o(|\mathcal{P}|/k)$ or
$M_{i}/|C_{i}|\leq(1+o(1))\Delta_{i}+o(|C_{i}|)$.

This proves the theorem because we can lower bound (5) as

$\displaystyle\sum_{i=1}^{k}\frac{1}{2|C_{i}|}\bigg{(}(|C_{i}|^{2}-M_{i})t_{2}+(M_{i})t_{0}-N_{i}t_{2}\bigg{)}$
$\displaystyle\geq\quad$
$\displaystyle\sum_{i=1}^{k}\frac{1}{2|C_{i}|}\bigg{(}(|C_{i}|^{2}-M_{i})t_{2}+(M_{i})t_{0}\bigg{)}-o(\ell|\mathcal{P}|)$
$\displaystyle=\quad$
$\displaystyle\frac{1}{2}\sum_{i=1}^{k}\bigg{(}t_{2}|C_{i}|-(t_{2}-t_{0})(M_{i}/|C_{i}|)\bigg{)}-o(\ell|\mathcal{P}|)$
$\displaystyle=\quad$
$\displaystyle\frac{1}{2}\bigg{(}t_{2}|\mathcal{P}|-(t_{2}-t_{0})\sum_{i=1}^{k}(M_{i}/|C_{i}|)\bigg{)}-o(\ell|\mathcal{P}|)$
$\displaystyle\geq\quad$
$\displaystyle\frac{1}{2}\bigg{(}t_{2}|\mathcal{P}|-(t_{2}-t_{0})\sum_{i=1}^{k}\Delta_{i}\bigg{)}-o(\ell|\mathcal{P}|),$

where the last inequality used the fact that either either
$M_{i}/|C_{i}|\leq(1+o(1))\Delta+o(|C_{i}|)$ or $|C_{i}|=o(|E|/k)$ where we
can use trivial bound $M_{i}/|C_{i}|\leq|C_{i}|=o(|\mathcal{P}|/k)$ so that
all the terms multiplied by $o(1)$ can be absorbed by the last term
$o(\ell|\mathcal{P}|)$. By using the soundness condition
$\sum_{i=1}^{k}\Delta_{i}\leq\alpha|\mathcal{P}|$ and plugging in the values
of $t_{0}$ and $t_{2}$, the total cost is at least by

$|\mathcal{P}|\frac{t_{0}}{2}+|\mathcal{P}|\frac{(t_{2}-t_{0})}{2}\bigg{(}1-\alpha\bigg{)}-o(\ell|\mathcal{P}|)=\ell|\mathcal{P}|\bigg{(}(z-y)+(1-\alpha)-\delta/2-o(1)\bigg{)}.$

Therefore, it remains to proof Claim 3.18.

###### Proof of Claim 3.18.

Note that $M_{i}\leq\sum_{S\in\binom{[n]}{y}}d_{i,S}^{2}$. First, consider the
set $\mathcal{S}=\\{S\in{n\choose y}\mid d_{i,S}<\gamma|C_{i}|\\}$ for some
small $\gamma>0$ that will be determined later, and let $E^{0}_{i}=\\{T\in
E_{i}\mid\exists S\in\mathcal{S},S\subseteq T\\}$. We have that

$\frac{1}{|C_{i}|}\sum_{S\in\mathcal{S}}d^{2}_{i,S}\leq\frac{\gamma|C_{i}|}{|C_{i}|}\sum_{S\in\mathcal{S}}d_{i,S}\leq\binom{z}{y}\gamma|E^{0}_{i}|,$
(6)

because each $z$-set $T$ can contribute to the degree $d_{i,S}$ of at most
$\binom{z}{y}$ different sets.

We then bound $\sum_{S\notin\mathcal{S}}d^{2}_{i,S}$. Let
$\mathcal{S}^{\prime}={n\choose y}\setminus\mathcal{S}$ and $E^{1}_{i}=\\{T\in
E_{i}\mid\exists S_{1},S_{2}\in\mathcal{S}^{\prime},S_{1}\neq
S_{2},S_{1}\subseteq T,S_{2}\subseteq T\\}$. We claim that

$\sum_{S\in\mathcal{S}^{\prime}}d_{i,S}\leq\binom{z}{y}|E_{i}^{1}|+|E_{i}|.$
(7)

Indeed, consider an element $T\in E_{i}$, we have that either there is at most
one element $S$ of $\mathcal{S}^{\prime}$ such that $S\subset T$, in which
case $T$ will be counted at most once in
$\sum_{S\in\mathcal{S}^{\prime}}d_{i,S}$, or $T$ contains more than one
element of $\mathcal{S}^{\prime}$. The elements of $E^{1}_{i}$ are counted at
most $\binom{z}{y}$ times in the sum and from there follows (7).

We claim that if $|E^{1}_{i}|>\gamma|E_{i}|$ or $|E_{i}|$ is small. From (7)
we deduce that there exists $S\in\mathcal{S}^{\prime}$ such that
$d_{i,S}\leq(\binom{z}{y}|E^{1}_{i}|+|E_{i}|)/|\mathcal{S}^{\prime}|$.
Moreover, since $S\in\mathcal{S}^{\prime}$ we also have that
$d_{i,S}\geq\gamma|E_{i}|\geq\gamma|E^{1}_{i}|$ and so, combining the two
bounds yields
$\gamma|E^{1}_{i}|\leq(\binom{z}{y}|E^{1}_{i}|+|E_{i}|)/|\mathcal{S}^{\prime}|$.
Rearranging gives

$|\mathcal{S}^{\prime}|\leq{\binom{z}{y}}/\gamma+\frac{|E_{i}|}{\gamma|E^{1}_{i}|}.$

If $|E^{1}_{i}|>\gamma|E_{i}|$ we get
$|\mathcal{S}^{\prime}|\leq\binom{z}{y}/\gamma+1/\gamma^{2}$. Hence,
$|E^{1}_{i}|$ is at most $(\binom{y}{z}/\gamma+1/\gamma^{2})^{2}\cdot
n^{z-y-1}$ since for each pair $S,S^{\prime}\in\mathcal{S}^{\prime}$, $S\neq
S^{\prime}$ there is at most $n^{z-y-1}$ $T\in E_{i}$ such that $S\subset
T,S^{\prime}\subset T$. Thus,
$|E_{i}|\leq(\binom{y}{z}/\gamma+1/\gamma^{2})^{2}/\gamma\cdot n^{z-y-1}$,
proving the claim.

For $i$ with $|E_{i}^{1}|\leq\gamma|E_{i}|$, using (7) together with the above
bound on $|E^{1}_{i}|$, we obtain

$\sum_{S\notin\mathcal{S}}d^{2}_{i,S}\leq\Delta_{i}\sum_{S\notin\mathcal{S}}d_{i,S}\leq\Delta_{i}(|E_{i}|+\binom{z}{y}|E^{1}_{i}|)\leq\Delta_{i}(1+\gamma\binom{z}{y})|E_{i}|.$
(8)

Combining (6) and (8) we deduce that
$\frac{1}{|E_{i}|}\sum_{S}d^{2}_{i,S}\leq(1+\gamma\binom{z}{y})\Delta_{i}+\gamma\binom{z}{y}|E_{i}|$.

Finally, since $|E|=\omega(kn^{z-y-1})$, we can choose $\gamma=o(1)$ such that

$\gamma\binom{z}{y}=o(1)\mbox{ and
}\bigg{(}\bigg{(}\binom{y}{z}/\gamma+1/\gamma^{2}\bigg{)}^{2}/\gamma\bigg{)}\cdot
kn^{z-y-1}=o(|E|).$

Therefore, if $|E_{i}^{1}|\leq\gamma|E_{i}|$, then
$M_{i}/|E_{i}|\leq(1+o(1))\Delta_{i}+o(|E_{i}|)$, and if
$|E_{i}^{1}|>\gamma|E_{i}|$, $|E_{i}|=o(|E|/k)$. This finishes the proof of
the claim and the theorem. ∎

∎

######  Remark 3.19.

Similar to Remark 3.14, we note here that given $(1-\delta,z,1)$-Johnson
Coverage problem is $\mathsf{NP}$-Hard for some constants $\delta>0$ and
$z\in\mathbb{N}$, plugging those parameters in Theorem 3.16, we immediately
have that continuous $k$-$\mathsf{means}$ is $\mathsf{APX}$-Hard in
$\ell_{2}$-metric.

Before, we address continuous case of $k$-$\mathsf{median}$ in
$\ell_{1}$-metric, we prove hardness of approximating the continuous case of
both $k$-$\mathsf{means}$ and $k$-$\mathsf{median}$ in the Hamming metric. The
inapproximability of $k$-$\mathsf{median}$ in $\ell_{1}$-metric then follows
by a simple observation.

######  Theorem 3.20 ($k$-$\mathsf{median}$ without candidate centers in
$O(\log n)$ dimensional $\ell_{0}$-metric space).

Assume $(\alpha,z,y)$-Johnson Coverage∗ is $\mathsf{NP}$-Hard. For every
constant $\varepsilon>0$, given a point-set $\mathcal{P}\subset\\{0,1\\}^{d}$
of size $n$ (and $d=O(\log n)$) and a parameter $k$ as input, it is
$\mathsf{NP}$-Hard to distinguish between the following two cases:

  * •

_Completeness_ : There exists
$\mathcal{C}^{\prime}:=\\{c_{1},\ldots,c_{k}\\}\subseteq\mathbb{\\{}0,1\\}^{d}$
and $\sigma:\mathcal{P}\to\mathcal{C}^{\prime}$ such that

$\sum_{a\in\mathcal{P}}\|a-\sigma(a)\|_{0}\leq\rho n\log n,$

  * •

_Soundness_ : For every
$\mathcal{C}^{\prime}:=\\{c_{1},\ldots,c_{k}\\}\subseteq\\{0,1\\}^{d}$ and
every $\sigma:\mathcal{P}\to\mathcal{C}^{\prime}$ we have:

$\sum_{a\in\mathcal{P}}\|a-\sigma(a)\|_{0}\geq\left(1+\frac{(1-\alpha)}{(z-y)}-\varepsilon\right)\cdot\rho
n\log n,$

for some constant $\rho>0$.

######  Theorem 3.21 ($k$-$\mathsf{means}$ without candidate centers in
$O(\log n)$ dimensional $\ell_{0}$-metric space).

Assume $(\alpha,z,y)$-Johnson Coverage∗ is $\mathsf{NP}$-Hard. For every
constant $\varepsilon>0$, given a point-set $\mathcal{P}\subset\\{0,1\\}^{d}$
of size $n$ (and $d=O(\log n)$) and a parameter $k$ as input, it is
$\mathsf{NP}$-Hard to distinguish between the following two cases:

  * •

_Completeness_ : There exists
$\mathcal{C}^{\prime}:=\\{c_{1},\ldots,c_{k}\\}\subseteq\mathbb{\\{}0,1\\}^{d}$
and $\sigma:\mathcal{P}\to\mathcal{C}^{\prime}$ such that

$\sum_{a\in\mathcal{P}}\|a-\sigma(a)\|_{0}^{2}\leq\rho n(\log n)^{2},$

  * •

_Soundness_ : For every
$\mathcal{C}^{\prime}:=\\{c_{1},\ldots,c_{k}\\}\subseteq\\{0,1\\}^{d}$ and
every $\sigma:\mathcal{P}\to\mathcal{C}^{\prime}$ we have:

$\sum_{a\in\mathcal{P}}\|a-\sigma(a)\|_{0}^{2}\geq\left(1+\frac{(1-\alpha)(2(z-y)+1)}{(z-y)^{2}}-\varepsilon\right)\cdot\rho
n(\log n)^{2},$

for some constant $\rho>0$.

###### Proof of Theorems 3.20 and 3.21.

The construction of the point-set $\mathcal{P}$ in the theorem statement is
the same as in the proof of Theorem 3.16. The completeness case is the same as
in Theorem 3.12. Therefore, we have that the $k$-$\mathsf{means}$ cost of the
overall instance is at most $\ell^{2}\cdot|\mathcal{P}|$, while the
$k$-$\mathsf{median}$ cost is at most $\ell\cdot|\mathcal{P}|$. The soundness
analysis to prove the theorem follows by a case analysis, which is elaborated
in [CK19] and we skip it here for the sake of brevity. ∎

We consider below $k$-$\mathsf{median}$ in $\ell_{1}$-metric.

######  Theorem 3.22 ($k$-$\mathsf{median}$ without candidate centers in
$O(\log n)$ dimensional $\ell_{1}$-metric space).

Assume $(\alpha,z,y)$-Johnson Coverage∗ is $\mathsf{NP}$-Hard. For every
constant $\varepsilon>0$, given a point-set $\mathcal{P}\subset\\{0,1\\}^{d}$
of size $n$ (and $d=O(\log n)$) and a parameter $k$ as input, it is
$\mathsf{NP}$-Hard to distinguish between the following two cases:

  * •

_Completeness_ : There exists
$\mathcal{C}^{\prime}:=\\{c_{1},\ldots,c_{k}\\}\subseteq\mathbb{\mathbb{R}}^{d}$
and $\sigma:\mathcal{P}\to\mathcal{C}^{\prime}$ such that

$\sum_{a\in\mathcal{P}}\|a-\sigma(a)\|_{1}\leq\rho n\log n,$

  * •

_Soundness_ : For every
$\mathcal{C}^{\prime}:=\\{c_{1},\ldots,c_{k}\\}\subseteq\mathbb{R}^{d}$ and
every $\sigma:\mathcal{P}\to\mathcal{C}^{\prime}$ we have:

$\sum_{a\in\mathcal{P}}\|a-\sigma(a)\|_{1}\geq\left(1+\frac{(1-\alpha)}{(z-y)}-\varepsilon\right)\cdot\rho
n\log n,$

for some constant $\rho>0$.

###### Proof Sketch.

The proof follows from a simple observation that for instances where all the
coordinates of the points to be clustered are in $\\{0,1\\}$, we have that for
any subset (i.e. cluster) of the points of the instance, an optimal center of
the set is such that its $i$th coordinate is the median of a set of values in
$\\{0,1\\}$, i.e., we may assume without loss of generality that the $i$th
coordinate of the center is also in $\\{0,1\\}$. Therefore, simply mimicking
the proof of Theorem 3.20 yields the desired theorem statement. See [CK19] for
a formal argument. ∎

Finally, we finish the section by proving the remaining hardness results for
continuous $k$-$\mathsf{median}$ and $k$-$\mathsf{means}$:
$k$-$\mathsf{median}$ in $\ell_{2}$-metric and $k$-$\mathsf{means}$ in
$\ell_{1}$-metric. Especially, $k$-$\mathsf{median}$ in $\ell_{2}$-metric for
$k=1$ is known as the geometric median and is actively studied for bounded $d$
or $k$ [ARR98, BHPI02, KSS10, FL11], but to the best of our knowledge, no
(hardness of) approximation algorithms have been studied for general $d$ and
$k$. First, we prove the following lemma that if points are pairwise far
apart, there is no good center that is close to all of them.

######  Lemma 3.23.

For any $\varepsilon\in(0,1)$, if $p_{1},\dots,p_{n}\in\mathbb{R}^{d}$ with
$n>4/\varepsilon+1$ satisfy $\|p_{i}-p_{j}\|_{2}\geq\sqrt{2}$, then, for any
$c\in\mathbb{R}^{d}$, $\max_{i\in[n]}\|c-p_{i}\|_{2}\geq 1-\varepsilon$.

###### Proof.

Assume towards contradiction that there exists $c$ such that
$\max_{i\in[n]}\|c-p_{i}\|_{2}<1-\varepsilon$. Without loss of generality let
$c=\vec{0}$ and consider the matrix $A\in\mathbb{R}^{n\times n}$ such that
$A_{i,j}=\langle
p_{i},p_{j}\rangle=(\|p_{i}\|_{2}^{2}+\|p_{j}\|_{2}^{2}-\|p_{i}-p_{j}\|_{2}^{2})/2<(2(1-\varepsilon)^{2}-2)/2\leq\varepsilon$.
Then $A$ is positive semidefinite, so if $\vec{1}$ denotes the all-ones
vector,

$(\vec{1}^{T})A\vec{1}\leq\sum_{i}A_{i,i}+\sum_{i<j}A_{i,j}\leq
n-\binom{n}{2}\varepsilon\geq 0,$

which leads to contradiction if $n>4/\varepsilon+1$. ∎

######  Theorem 3.24 ($k$-$\mathsf{median}$ without candidate centers in
$O(\log n)$-dimensional $\ell_{2}$-metric space).

Assume $(\alpha,z,y)$-Johnson Coverage∗ is $\mathsf{NP}$-Hard. For every
constant $\varepsilon>0$, given a point-set $\mathcal{P}\subset\mathbb{R}^{d}$
of size $n$ (and $d=O(\log n)$) and a parameter $k$ as input, it is
$\mathsf{NP}$-Hard to distinguish between the following two cases:

  * •

_Completeness_ : There exists
$\mathcal{C}^{\prime}:=\\{c_{1},\ldots,c_{k}\\}\subseteq\mathbb{\mathbb{R}}^{d}$
and $\sigma:\mathcal{P}\to\mathcal{C}^{\prime}$ such that

$\sum_{a\in\mathcal{P}}\|a-\sigma(a)\|_{2}\leq n$

  * •

_Soundness_ : For every
$\mathcal{C}^{\prime}:=\\{c_{1},\ldots,c_{k}\\}\subseteq\mathbb{R}^{d}$ and
every $\sigma:\mathcal{P}\to\mathcal{C}^{\prime}$ we have:

$\sum_{a\in\mathcal{P}}\|a-\sigma(a)\|_{2}\geq\left(\alpha+\sqrt{\frac{z-y+0.5}{z-y}}(1-\alpha)-\varepsilon\right)n$

###### Proof.

Given an instance $(U,E,k)$ of $(\alpha,z,y)$-Johnson Coverage∗, for any
$S\subseteq U$, let $\tau(S)$ be the indicator vector of $S$. (The dimension
can be reduced to $O(\log n)$ by the standard dimension reduction technique.)

In the completeness case, every point is connected to a center at distance
$\sqrt{z-y}$. For the soundness case, fix one cluster $C$ and its center
$c\in\mathbb{R}^{U}$. Fix $\varepsilon>0$, and remove all points from $C$
whose $\ell_{2}$ distance to $c$ is greater than
$(\sqrt{z-y+0.5}-\varepsilon)$. Assume $C=\omega(n^{z-y-1})$. We will show
that there exists $S^{\prime}\in\binom{U}{y}$ that covers all but
$O(n^{z-y-1})$ sets in $C$.

We claim that no two $y$-sets can both cover $\omega(n^{z-y-1})$ number of
$z$-sets in $C$. Assume towards contradiction that there exist
$S^{\prime},T^{\prime}\in\binom{U}{y}$ be such that each of them covers at
least $t=\omega(n^{z-y-1})$ sets in $C$. Let $s=|S^{\prime}\cap T^{\prime}|$
and $I=S^{\prime}\cap T^{\prime}$. Consider the center $c$ and its squared
distances to $\tau(S^{\prime})$ and $\tau(T^{\prime})$ in coordinates
$Q=(S^{\prime}\cup T^{\prime})\setminus I$. Since $\tau(S^{\prime})$ and
$\tau(T^{\prime})$ are different in these coordinates,
$(c_{i}-\tau(S^{\prime})_{i})^{2}+(c_{i}-\tau(T^{\prime})_{i})^{2}\geq 0.5$
for each $i\in Q$. Without loss of generality, assume that
$(c_{i}-\tau(S^{\prime})_{i})^{2}\geq(y-s)/2\geq 0.5$.

Now let us consider the points restricted to the coordinates
$O=U\setminus(S\cup T)$. First, we claim that we can choose
$S_{1},\dots,S_{\ell}$ with $\ell=\omega(1)$ such that $S_{i}\in C$,
$S^{\prime}\subseteq S_{i}$, $S_{i}\setminus S\subseteq O$, and $S_{i}$’s are
pairwise disjoint. First the number of $S\in C$ that contains $S^{\prime}$ and
intersects $T^{\prime}$ with in at least one element outside $S^{\prime}$ is
at most $|T^{\prime}|\cdot n^{z-y-1}$, which is only an $o(1)$ fraction of the
$z$-sets in $C$ covered by $S^{\prime}$. Remove them from $C$. Now, consider a
greedy iteration for $i=1,\dots,\ell$ where we pick an arbitrary set $S_{i}\in
C$ that contains $S^{\prime}$, and remove all sets from $C$ that insect
$S_{i}$ outside $S^{\prime}$. Each time, the number of removed sets is only
$(z-y)n^{z-y-1}$, and since $C=\omega(n^{z-y-1})$, this process can continue
$\ell=o(1)$ iterations.

Then $\tau(S_{i})$ and $\tau(S_{j})$ on coordinates in $O$ are at distance at
least $\sqrt{2(z-y)}$ from each other. Since the contribution of
$\|c-S_{i}\|_{2}^{2}$ from $Q$ is already at least $0.5$, Lemma 3.23 shows
there is no center can cover every point in $C$ at distance at most
$\sqrt{z-y+0.5}-o(1)$, leading to the desired contradiction.

Now we prove that there exist a bounded number of $y$-sets that collectively
cover every $z$-sets. Consider the following process starting with
$C^{\prime}=C$ and $i=1$.

  1. 1.

Let $S_{i}$ be an arbitrary set from $C^{\prime}$.

  2. 2.

Delete all $S\in C^{\prime}$ such that $|S\cap S_{i}|\geq y$.

  3. 3.

If $C^{\prime}$ is nonempty, increase $i$ by $1$ and repeat from 1.

Let $t$ be the final value of $i$, and consider $S_{1},\dots,S_{t}$. They are
at distance at least $\sqrt{2(z-y+1)}$ from each other, so again by Lemma 3.23
and using that $\sqrt{2(z-y+1)}/\sqrt{2}=\sqrt{z-y+1}>\sqrt{z-y+0.5}$, $t$ is
most some absolute constant. Then $y$-sets in $\\{S^{\prime}\subseteq
U:|S^{\prime}|=y\mbox{ and }S^{\prime}\subseteq S_{i}\mbox{ for some
}i\in[t]\\}$ cover all sets in $C$. A similar argument for
$C^{*}=\\{S:\|\tau(S)-c\|_{2}<\sqrt{z-y}-\varepsilon\\}$ and $y+1$ implies
that $|C^{*}|\leq O(n^{z-y-1})$.

So far, we showed that (1) there are a constant number of $y$-sets that
collectively cover every $S\in C$ (2) except one set, every $y$-set can cover
at most $O(n^{z-y-1})$ sets in $C$, and (3) $|C^{*}|\leq O(n^{z-y-1})$.
Therefore, whenever $|C|=\omega(n^{z-y-1})$, there exists
$S^{\prime}\in\binom{U}{y}$ that covers all but a subconstant fraction of sets
in $C$. Since $|E|=\omega(kn^{y-z-1})$, we can use an argument similar to
Theorem 3.16 to show that in the soundness case, the fraction of points that
are covered by a center at distance at most $\sqrt{z-y+0.5}-\varepsilon$ is at
most $\alpha+o(1)$, and at most an $o(1)$ fraction of points are covered at
distance at most $\sqrt{z-y}-\varepsilon$. This proves the theorem. ∎

######  Theorem 3.25 ($k$-$\mathsf{means}$ without candidate centers in
$\text{poly}(n)$-dimensional $\ell_{1}$-metric space).

Assume $(\alpha,z,y)$-Johnson Coverage∗ is $\mathsf{NP}$-Hard. For every
constant $\varepsilon>0$, given a point-set $\mathcal{P}\subset\\{0,1\\}^{d}$
of size $n$ (and $d=O(\log n)$) and a parameter $k$ as input, it is
$\mathsf{NP}$-Hard to distinguish between the following two cases:

  * •

_Completeness_ : There exists
$\mathcal{C}^{\prime}:=\\{c_{1},\ldots,c_{k}\\}\subseteq\mathbb{\mathbb{R}}^{d}$
and $\sigma:\mathcal{P}\to\mathcal{C}^{\prime}$ such that

$\sum_{a\in\mathcal{P}}\|a-\sigma(a)\|_{1}^{2}\leq n$

  * •

_Soundness_ : For every
$\mathcal{C}^{\prime}:=\\{c_{1},\ldots,c_{k}\\}\subseteq\mathbb{R}^{d}$ and
every $\sigma:\mathcal{P}\to\mathcal{C}^{\prime}$ we have:

$\sum_{a\in\mathcal{P}}\|a-\sigma(a)\|_{1}^{2}\geq\left(\alpha+(1-\alpha)\frac{(z-y+1)^{2}}{(z-y)^{2}}-\varepsilon\right)n.$

###### Proof.

Given an instance $(U,E,k)$ of $(\alpha,z,y)$-Johnson Coverage∗, for any
$S\subseteq U$, let $\tau(S)$ be the indicator vector of $S$. We analyze the
completeness and soundness of this simple reduction. Since every point is in
the boolean hypercube, the embedding of 3.12 ensures that one can reduce the
dimension to $O(\log n)$ with losing an arbitrarily small constant in the
inapproximability factor.

In the completeness case, every point is connected to a center at distance
$z-y$. For the soundness case, fix one cluster $C$ and its center
$c\in\mathbb{R}^{U}$. Fix $\varepsilon>0$, and remove all points from $C$
whose $\ell_{1}$ distance to $c$ is at least $(z-y+1-\varepsilon)$.

First, note that for every $S,T\in C$, $|S\cap T|\geq y$. Otherwise,
$\|\tau(S)-\tau(T)\|_{1}\geq 2(z-y+1)$, so there is no center that are at
distance strictly less than $z-y+1$ from both $\tau(S)$ and $\tau(T)$.

Fix any $S\in C$. Then every $T\in C$ is covered by a $y$-set in
$\mathcal{F}=\\{S^{\prime}\subseteq U:|S^{\prime}|=y\mbox{ and
}S^{\prime}\subseteq S\\}$. Furthermore, argument similar to the proof of
Theorem 3.24 show except possibly one, every $y$-set can cover at most
$O(n^{z-y-1})$ sets in $C$, and the number of points that are covered at
distance strictly less than $z-y$ is also at most $O(n^{z-y-1})$.

Therefore, whenever $|C|=\omega(n^{z-y-1})$, there exists
$S^{\prime}\in\binom{U}{y}$ that covers all but a subconstant fraction of sets
in $C$. Since $|E|=\omega(kn^{y-z-1})$, we can use an argument similar to
Theorem 3.16 to show that in the soundness case, the fraction of points that
are covered by a center at distance at most $z-y+1-\varepsilon$ is at most
$\alpha+o(1)$, and at most an $o(1)$ fraction of points are covered at
distance at most $z-y-\varepsilon$. This proves the theorem. ∎

###  3.5 Integrality Gaps

In this subsection we present improved integrality gaps. Given an instance of
discrete $k$-$\mathsf{median}$ or $k$-$\mathsf{means}$ with a set of candidate
centers $\mathcal{C}$, a set of points $\mathcal{P}$, and distances
$\\{d_{p,c}\\}_{p\in\mathcal{P},c\in\mathcal{C}}$, the basic LP relaxation for
$k$-$\mathsf{median}$ or $k$-$\mathsf{means}$ is the following. (For
$k$-$\mathsf{means}$, $d_{p,c}$ becomes a squared distance.)

Minimize
$\displaystyle\quad\sum_{p\in\mathcal{P}}\sum_{c\in\mathcal{C}}x_{p,c}\cdot
d_{p,c}$ Subject to $\displaystyle\quad\sum_{c\in C}x_{p,c}=1$
$\displaystyle\forall p\in\mathcal{P}$ $\displaystyle\quad x_{p,c}\leq y_{c}$
$\displaystyle\forall p\in\mathcal{P},c\in\mathcal{C}$
$\displaystyle\quad\sum_{c\in C}y_{c}\leq k$ $\displaystyle\quad x,y\geq 0.$

The basic SDP relaxation, which replaces $x_{p,c}$ and $y_{c}$ by
$\|v_{p,c}\|_{2}^{2}$ and $\|u_{c}\|_{2}^{2}$ for some vectors $\\{v_{p,c}\\}$
and $\\{u_{c}\\}$ with additional constraints, is the following.

Minimize
$\displaystyle\quad\sum_{p\in\mathcal{P}}\sum_{c\in\mathcal{C}}{\|v_{p,c}\|_{2}^{2}\cdot
d_{p,c}}$ Subject to $\displaystyle\quad\langle v_{0},v_{0}\rangle=1$
$\displaystyle\quad\langle v_{p,c},v_{0}\rangle=\|v_{p,c}\|_{2}^{2}$
$\displaystyle\forall p\in\mathcal{P},c\in\mathcal{C}$ (9)
$\displaystyle\quad\langle u_{c},v_{0}\rangle=\|u_{c}\|_{2}^{2}$
$\displaystyle\forall c\in\mathcal{C}$ (10) $\displaystyle\quad\langle
v_{p,c},u_{c}\rangle=\|v_{p,c}\|_{2}^{2}$ $\displaystyle\forall
p\in\mathcal{P},c\in\mathcal{C}$ (11) $\displaystyle\quad\|\sum_{c\in
C}v_{p,c}-v_{0}\|_{2}^{2}=0$ $\displaystyle\forall p\in\mathcal{P}$ (12)
$\displaystyle\quad\sum_{c\in C}\|y_{c}\|_{2}^{2}\leq k$

We give stronger integrality gap instances than the standard notion. The LP or
SDP relaxation has a robust gap of $\alpha>1$ if there exists a family of
instances for infinitely many values of $k$ where for any $\varepsilon>0$,
there exists $\delta>0$ and $k_{0}\in\mathbb{N}$ such that for all instances
in the family with $k\geq k_{0}$, the gap between the optimal fractional
solution and the optimal integral solution is at least $\alpha-\varepsilon$
even when the optimal integral solution is allowed to open $k+\delta k$
facilities.

Our instances additionally satisfy well-separated the property that every pair
of points in $\binom{\mathcal{P}\cup\mathcal{C}}{2}$ are at distance at least
$1$ far part, where each instance is normalized so that $1$ is the average
connection cost of each point in the SDP solution.

The basic LP relaxation for metric $k$-$\mathsf{median}$ has a gap of $2$
under the standard notion [JMS02], but this instance does not give a robust
gap. The best approximation algorithms for $k$-$\mathsf{median}$ and
$k$-$\mathsf{means}$ in both general and Euclidean metrics bound the robust
gap of the LP relaxation [BPR+15, ANSW20], and to the best of our knowledge,
for well-separated instances, no robust gap of the LP relaxation better than
computational hardness results [GK99, CK19] were previously known.

######  Theorem 3.26.

Fix any $\varepsilon>0$. For discrete $k$-$\mathsf{median}$ in $\ell_{1}$ and
discrete $k$-$\mathsf{means}$ in $\ell_{2}$, there is a family of well-
separated instances where the SDP relaxation has a gap of at least
$149/125-\varepsilon\approx 1.192-\varepsilon$, even when the integral
solution opens $\Omega(k)$ more centers.

###### Proof.

Consider the complete graph $K_{n}=([n],E)$ with $E=\binom{[n]}{2}$. Let
$\tau:2^{E}\to\mathbb{R}^{n}$ where for any $p\subseteq E$, $\tau(p)$ is
defined to be the characteristic vector of $\cup_{e\in p}e$. The set points
$\mathcal{P}$ is defined to be $\mathcal{P}:=\\{\tau(p):p\mbox{ forms a
4-clique in }K_{n}\\}$. The set $C$ of candidate centers, for each edge $e\in
E$, has a center $\tau(e)$. To simplify notation, we use $p$ (resp. $e$) to
also denote $\tau(p)$ (resp. $\tau(e)$) when $p$ (resp. $e$) is used as part
of the clustering instance.

We say that an edge $e\in E$ covers a $4$-clique $p$ if $e\in p$; in this case
a center $e\in\mathcal{C}$ also covers a point $p\in\mathcal{P}$. Note that
$\|e-p\|_{0}=\|e-p\|_{1}=2$ if $e$ covers $p$ and at least $4$ otherwise.
Since each $4$-clique has 6 edges and each edge yields $m$ centers, note that
each point $p\in\mathcal{P}$ is covered by exactly $6$ centers. Therefore,
there is an LP solution that picks $\nicefrac{{1}}{{6}}$ of each $e\in C$ and
fractionally covers every $p\in\mathcal{P}$. We prove that even for the SDP,
there is such a solution that picks $\nicefrac{{1}}{{5}}$ of each $e\in C$.

######  Claim 3.27.

There exists a feasible SDP solution where every $p\in\mathcal{P}$ is
fractionally connected to only centers at distance at most $2$, and
$\|u_{e}\|_{2}^{2}=\nicefrac{{1}}{{5}}$ for every $e$.

###### Proof.

Let $t=5$. Let $v_{0}$ and $\\{w_{e},w^{\prime}_{e}\\}_{e\in E}$ be pairwise
orthogonal unit vectors. We explicitly construct the vectors for the SDP
relaxation.

  * •

For each $e\in E$,
$u_{e}=\frac{v_{0}}{t}+\big{(}\frac{(t-1)\sqrt{t+1}}{t^{2}}\big{)}w_{e}+\big{(}\frac{\sqrt{t-1}}{t^{2}}\big{)}w^{\prime}_{e}$.

  * •

For each $e\in E$, and a $4$-clique $p$, if $e\in p$,

$v_{p,e}=\frac{1}{t+1}\cdot v_{0}+\frac{t}{(t+1)^{3/2}}\cdot w_{e}-\sum_{f\in
p\setminus\\{e\\}}\frac{1}{(t+1)^{3/2}}\cdot w_{f}.$

Otherwise $v_{p,e}=0$.

Note that every point $p\in\mathcal{P}$ is only connected to $e$ that covers
$p$. We check each constraint of the SDP. The first constraint $\langle
v_{0},v_{0}\rangle=1$ is true by definition. Since

$\|u_{e}\|_{2}^{2}=\frac{1}{t^{2}}+\frac{(t-1)^{2}(t+1)}{t^{4}}+\frac{t-1}{t^{4}}=\frac{1}{t^{2}}+\frac{t-1}{t^{2}}=\frac{1}{t}=\langle
v_{0},u_{e}\rangle,$

it satisfies (10). Since for $e\in p$,

$\|v_{p,e}\|_{2}^{2}=\frac{1}{(t+1)^{2}}+\frac{t^{2}}{(t+1)^{3}}+\frac{t}{(t+1)^{3}}=\frac{1}{t+1}=\langle
v_{0},v_{p,e}\rangle,$

it satisfies (9). Furthermore, for each $p\in\mathcal{P}$, $\sum_{e\in
p}v_{p,e}=v_{0}$, since the coefficient of $w_{e}$ in the sum for any $e\in p$
is $\frac{t}{(t+1)^{3/2}}$ (from $v_{p,e}$) minus $t$ times
$\frac{1}{(t+1)^{3/2}}$ (from every other $v_{p,f}$), which is $0$. It
satisfies (12). Finally, (11) can be checked as for every $4$-clique $p$,
$e\in p$,

$\langle
u_{e},v_{p,e}\rangle=\frac{1}{t}\cdot\frac{1}{t+1}+\frac{(t-1)\sqrt{t+1}}{t^{2}}\cdot\frac{t}{(t+1)^{3/2}}=\frac{1}{t(t+1)}+\frac{t-1}{t(t+1)}=\frac{1}{t+1}=\|v_{p,e}\|_{2}^{2}.$

Since the solution satisfies every SDP constraint, each $p\in\mathcal{P}$ is
only connected to a center covering $p$, and $\|u_{e}\|_{2}^{2}=1/t$ for every
$e$, the claim is proved. ∎

Therefore the optimal relaxation value is at most $2\cdot\binom{n}{4}$ when
$k=\binom{n}{2}/5$. Now we consider if we pick at most $k$ edges $E$
integrally, how many $4$-cliques can be covered by them. Equivalently, we ask
if we pick at least $\binom{n}{2}-k$ edges, how many $4$-cliques are
completely contained by them. The clique density theorem of Reiher [Rei16]
answers this question, proving that if we pick at least an
$(1-\nicefrac{{1}}{{t}})$ fraction of edges for some integer $t\geq 4$, the
number of $4$-cliques completely contained in them is at least that of
complete $t$-partite graph with each partition having the same size. Note that
in the complete $t$-partite graph, the probability that a random $4$-tuple
becomes a clique is roughly
$1\cdot\frac{t-1}{t}\cdot\frac{t-2}{t}\cdot\frac{t-3}{t}$.

######  Theorem 3.28 ([Rei16]).

Let $t\geq 4$ be an integer. In every graph on $n$ vertices with at least
$\frac{(t-1)}{t}\cdot\binom{n}{2}$ edges, the number of 4-cliques is at least

$\binom{n}{4}\cdot\frac{t(t-1)(t-2)(t-3)}{t^{4}}.$

Applying the above theorem with $t=5$ shows that if we pick $k$ edges, the
fraction of 4-cliques covered by them is at most $1-\nicefrac{{(5\cdot 4\cdot
3\cdot 2)}}{{5^{4}}}=\nicefrac{{24}}{{125}}$. Therefore, while every point is
connected at distance $2$ the SDP solution, in the integral solution at least
a $\nicefrac{{24}}{{125}}$ fraction of the points are connected at distance at
least $4$. The gap is at least $(2+2(24/125)/2)=149/125\approx 1.192$. ∎

##  4 NP-Hardness of Approximatig 3-Hypergraph Vertex Coverage problem

In this section, we prove the following theorem showing that for any
$\varepsilon>0$, $(7/8+\varepsilon,3,1)$-Johnson Coverage Problem is NP-hard
for randomized reductions (even in the dense case). By the results in Sections
3.3 and 3.4, we obtain the inapproximability results for clustering problems
stated in Theorem 1.5 and Table 1.

######  Theorem 4.1.

For any $\varepsilon>0$, given a simple 3-hypergraph $\mathcal{H}=(V,H)$ with
$n=|V|$, it is NP-hard to distinguish between the following two cases:

  * •

Completeness: There exists $S\subseteq V$ with $|S|=n/2$ that intersects every
hyperedge.

  * •

Soundness: Any subset $S\subseteq V$ with $|S|\leq n/2$ intersects at most a
$(7/8+\varepsilon)$ fraction of hyperedges.

Furthermore, with randomized reductions, the above hardness holds when
$|H|=\omega(n^{2})$.

We first prove Theorem 4.1 without the lower bound on $|H|$; Section 4.1
presents the construction and proves the completeness of the reduction, and
Section 4.2, 4.3, and 4.4 analyze its soundness. Finally, Section 4.5 shows
how to ensure $|H|=\omega(n^{2})$.

###  4.1 Overview and Construction

Consider the setting of Theorem 4.1. A random set of $|V|/2$ elements will
intersect each hyperedge with probability $7/8$, so the theorem says that it
is hard to do even slightly better than the random solution. It is similar to
the notion of approximate resistance mainly studied for constraint
satisfaction problems. Indeed, given an instance of Max 3-SAT with variables
$\\{x_{1},\dots,x_{n}\\}$ and clauses
$\\{(\ell_{i,1}\cup\ell_{i,2}\cup\ell_{i,3})\\}_{i\in[m]}$ where each
$\ell_{i,j}$ denotes a literal $x_{k}$ or $\overline{x_{k}}$, consider the
simple reduction of creating a vertex for each literal and a hyperedge
$(\ell_{i,1},\ell_{i,2},\ell_{i,3})$ for each clause. This reduction almost
proves the above theorem, except that the soundness property only holds for
$S$ that satisfies $|S\cap\\{x_{i},\overline{x_{i}}\\}|\leq 1$ for each
$i\in[n]$. However, the resulting hypergraph produced by this reduction
combined with Håstad’s celebrated hardness for Max 3-SAT [Hås01] is always
bipartite due to the underlying bipartite structure of the outer verifier, so
there is a vertex cover of size at most $|V|/2$ even in the soundness case.

We bypass the above problem by plugging in Håstad’s inner verifier to the
outer verifier constructed in Guruswami et al. [DGKR05] and Khot [Kho02]. This
outer verifier is called a multilayered PCP and used for proving hardness of
the covering version of our problem called $k$-Hypergraph Vertex Cover. We
give a new analysis for the multilayered PCP and combine the analysis for
Håstad’s inner verifier to bound the number of uncovered hyperedges for all
$S$ with $|S|\leq|V|/2$.

We now formally present the reduction. We first describe multilayered PCPs
that we use.

######  Definition 4.2.

An $\ell$-layered PCP $\mathcal{M}$ consists of

  * •

An $\ell$-partite graph $G=(V,E)$ where $V=\cup_{i=1}^{\ell}V_{i}$. Let
$E_{i,j}=E\cap(V_{i}\times V_{j})$.

  * •

Sets of alphabets $\Sigma_{1},\dots,\Sigma_{\ell}$.

  * •

For each edge $e=(v_{i},v_{j})\in E_{i,j}$, a surjective projection
$\pi_{e}:\Sigma_{j}\to\Sigma_{i}$.

Given an assignment $(\sigma_{i}:V_{i}\to\Sigma_{i})_{i\in[\ell]}$, an edge
$e=(v_{i},v_{j})\in E_{i,j}$ is satisfied if
$\pi_{e}(\sigma_{j}(v_{j}))=\sigma_{i}(v_{i})$. There are additional
properties that $\mathcal{M}$ can satisfy.

  * •

$\eta$-smoothness: For any $i<j$, $v_{j}\in V$, and $x,y\in\Sigma_{j}$,
$\Pr_{(v_{i},v_{j})\in
E_{i,j}}[\pi_{(v_{i},v_{j})}(x)=\pi_{(v_{i},v_{j})}(y)]\leq\eta$.

  * •

Path-regularity: Call a sequence $p=(v_{1},\dots,v_{\ell})$ full path if
$(v_{i},v_{i+1})\in E_{i,i+1}$ for every $1\leq i<\ell$, and let $\mathcal{P}$
be the distribution of full paths obtained by (1) sampling a random vertex
$v_{1}\in V_{1}$ and (2) for $i=2,\dots,\ell$, sampling $v_{i}$ from the
neighbors of $v_{i-1}$ in $E_{i-1,i}$. $\mathcal{M}$ is called path-regular if
for any $i<j$, sampling $p=(v_{1},\dots,v_{\ell})$ from $\mathcal{P}$ and
taking $(v_{i},v_{j})$ is the same as sampling uniformly at random from
$E_{i,j}$.

######  Theorem 4.3 ([DGKR05, Kho02]).

For any $\tau,\eta>0$ and $\ell\in\mathbb{N}$, given an $\ell$-layered PCP
$\mathcal{M}$ with $\eta$-smoothness and path-regularity, it is NP-hard to
distinguish between the following cases.

  * •

Completeness:  There exists an assignment that satisfies every edge $e\in E$.

  * •

Soundness:  For any $i<j$, no assignment can satisfy more than an $\tau$
fraction of edges in $E_{i,j}$.

Given an $\ell$-layered PCP $\mathcal{M}$ described as above, we construct the
reduction from to Johnson Coverage. For simplicity of presentation, the
produced instance will be vertex-weighted and edge-weighted, so that the
problem becomes “choose a set of vertices of total weight at most $k$ to
maximize the total weight of covered edges.” Vertex weights can be easily
removed by duplicating vertices according to weights and creating edges
between duplicated vertices with appropriate weights. Edge weights will be
handled in Section 4.5.

  * •

Let $C_{i}:=\\{\pm 1\\}^{\Sigma_{i}}$ and $U_{i}:=V_{i}\times C_{i}$. The
resulting hypergraph will be denoted by $\mathcal{H}=(U,H)$ where
$U=\cup_{i=1}^{\ell}(V_{i}\times C_{i})$. The weight of vertex $(v,x)\in
V_{i}\times C_{i}$ is

$w(v,x):=\frac{1}{\ell}\cdot\frac{1}{|V_{i}|}\cdot\frac{1}{|C_{i}|}.$

Note that the sum of all vertex weights is $1$.

  * •

Let $\mathcal{D}_{I}$ be the distribution where $i\in[\ell]$ is sampled with
probability $(\ell-i)^{2}/(6\ell(\ell-1)(2\ell-1))$, and $\mathcal{D}$ be the
distribution over $(i,j)\in[\ell]^{2}$ where $i$ is sampled from
$\mathcal{D}_{I}$ and $j$ is sampled uniformly from $\\{i+1,\dots,\ell\\}$.
For each $i<j$, we create a set of hyperedges $H_{i,j}$ that have one vertex
in $U_{i}$ and two vertices in $U_{j}$. Fix each $e=(v_{i},v_{j})\in E_{i,j}$
and a set of three vertices $t\subseteq(\\{v_{i}\\}\times
C_{i})\cup(\\{v_{j}\\}\times C_{j})$. The weight $w(t)$ is $($the probability
that $(i,j)$ is sampled from $\mathcal{D})\cdot(1/|E_{i,j}|)\cdot($the
probability that $t$ is sampled from the following procedure$)$. The reduction
is parameterized by $\delta>0$ determined later.

    * –

For each $a\in\Sigma_{i}$, sample $x_{a}\in\\{\pm 1\\}$.

    * –

For each $b\in\Sigma_{j}$,

      * *

Sample $y_{b}\in\\{\pm 1\\}$.

      * *

If $x_{\pi(b)}=-1$, let $z_{b}=y_{b}$ with probability $1-\delta$ and
$z_{b}=-y_{b}$ otherwise.

      * *

If $x_{\pi(b)}=1$, let $z_{b}=-y_{b}$.

    * –

Output $\\{(v_{i},x),(v_{j},y),(v_{j},z)\\}$.

Note that the sum of all hyperedge weights is also $1$.

##### Completeness.

If $\mathcal{M}$ admits an assignment
$(\sigma_{i}:V_{i}\to\Sigma_{i})_{i\in[\ell]}$ that satisfies every edge $e\in
E$, let $S:=\\{(v_{i},x):v_{i}\in V_{i},x_{\sigma_{i}(v_{i})}=-1\\}$. Fix any
$e=(v_{i},v_{j})\in E_{i,j}$ and consider the above sampling procedure to
sample $x\in\\{\pm 1\\}^{\Sigma_{i}}$ and $y\in\\{\pm 1\\}^{\Sigma_{j}}$ when
$b=\sigma_{j}(v_{j})$. Since $\pi_{e}(\sigma_{j}(v_{j}))=\sigma_{i}(v_{i})$,
at least one of $x_{\sigma_{i}(v_{i})}$, $y_{\sigma_{j}(v_{j})}$,
$z_{\sigma_{j}(v_{j})}$ must be $-1$ always. This proves that $S$ intersects
every hyperedge with nonzero weight.

###  4.2 Soundness.

In the soundness case, we want to prove that any subset of weight at most
$1/2$ intersects hyperedges of total weight at most $7/8+o(1)$. We prove the
equivalent statement that for any $S\subseteq V$ of weight greater than $1/2$
contains hyperedges of total weight approximately at least $1/8-o(1)$.

Fix a set $S\subseteq V$ with $w(S)\geq 1/2$. Let $S_{i}:=S\cap V_{i}$. Let
$F=\\{e\in H:e\in S\\}$ and $F_{i,j}:=F\cap H_{i,j}$. Our goal is to show
$w(F)$ is approximately at least $1/8-o(1)$.

Given a vertex $v\in V_{i}$, let $C_{v}:=\\{v\\}\times C_{i}\subseteq U$ and

$\alpha_{v}:=\ell|V_{i}|\cdot\bigg{(}\sum_{v\in(S\cap C_{v})}w(v)\bigg{)}$

be the normalized weight of $S$ in $C_{v}$. Given vertices $v_{i}\in V_{i}$
and $v_{j}\in V_{j}$ with $i<j$, let
$D_{i,j}=\Pr_{(i^{\prime},j^{\prime})\sim\mathcal{D}}[i=i^{\prime},j=j^{\prime}]$
and

$\beta_{v_{i},v_{j}}:=\frac{1}{D_{i,j}}\cdot|E_{i,j}|\cdot\bigg{(}\sum_{e\in(F\cap
H(C_{v_{i}}\cup C_{v_{j}}))}w(e)\bigg{)}$

be the normalized weight of $F$ in $H(C_{v_{i}}\cup C_{v_{j}})$, where given
$T\subseteq V$, $H(T)$ is defined as $\\{e\in H:e\subseteq T\\}$. Note that
all $\alpha_{v},\beta_{v_{i},v_{j}}$ are in $[0,1]$. Furthermore,

$\mathbb{E}_{i\in[\ell]}\mathbb{E}_{v\in V_{i}}[\alpha_{v}]=w(S),$

and

$\mathbb{E}_{(i,j)\sim\mathcal{D}}\mathbb{E}_{(v_{i},v_{j})\in
E_{i,j}}[\beta_{v_{i},v_{j}}]=w(F).$

Let $\alpha_{i}:=\mathbb{E}_{v\in V_{i}}[\alpha_{v}]$ and
$\beta_{i,j}:=\mathbb{E}_{(v_{i},v_{j})\in E_{i,j}}[\beta_{v_{i},v_{j}}]$.
Finally, for each full path $p=(v_{1},\dots,v_{\ell})$, let
$\alpha_{p,i}:=\alpha_{v_{i}}$ and $\beta_{p,i,j}:=\beta_{v_{i},v_{j}}$.

Call a triple $(p,i,j)$ good if
$\beta_{p,i,j}<\alpha_{p,i}\alpha_{p,j}^{2}-\varepsilon$. The following lemma
says that we are done if few triples are good.

######  Lemma 4.4.

If $\Pr_{p\in\mathcal{P},(i,j)\in\mathcal{D}}[(p,i,j)\mbox{ is
good}]\leq\varepsilon$, then $w(F)\geq 1/8-3(\sqrt{\varepsilon}+1/\ell)$.

Therefore, it remains to consider the case that the condition of Lemma 4.4
does not hold. Then, there exists $i<j$ such that
$\Pr_{p\in\mathcal{P}}[(p,i,j)\mbox{ is good}]\geq\varepsilon.$ The following
lemma, essentially from Håstad’s analysis for Max 3-SAT [Hås01], states that
it cannot happen if there is no good assignment for the multilayered PCP
instance $\mathcal{M}$. For completeness, we reproduce a proof in Section 4.4

######  Lemma 4.5.

Fix any $i<j$. If $\Pr_{p\in\mathcal{P}}[(p,i,j)\mbox{ is
good}]\geq\varepsilon$, then there is an assignment for $\mathcal{M}$ that
satisfies at least an
$(\varepsilon\delta^{4}/2)\cdot(\varepsilon/2-2\delta-2\eta\delta^{-4})^{2}$
fraction of edges in $E_{i,j}$.

First take small enough $\varepsilon>0$ and large enough $\ell\in\mathbb{N}$
will ensure $w(F)\geq 1/8-3(\sqrt{\varepsilon}+1/\ell)$ is almost at least
$1/8$. Choosing $\delta=\varepsilon^{2}/4$, $\eta=\delta^{6}$ will ensure that
the guarantee in Lemma 4.5 is at least $\varepsilon^{c}$ for some absolute
constant $c\in\mathbb{N}$. By taking $\tau$ in Theorem 4.3 smaller than that,
we can ensure that $\Pr_{p\in\mathcal{P}}[(p,i,j)\mbox{ is
good}]\leq\varepsilon$ and $w(F)\geq 1/8-3(\sqrt{\varepsilon}+1/\ell)$ in the
soundness case, proving Theorem 4.1.

###  4.3 Proof of Lemma 4.4

###### Proof.

Recall that for any $i<j$, sampling $p=(v_{1},\dots,v_{\ell})\in\mathcal{P}$
and choosing $(v_{i},v_{j})$ is the same as sampling $(v_{i},v_{j})\in
E_{i,j}$ uniformly at random. Therefore,

$\displaystyle w(F)$
$\displaystyle=\mathbb{E}_{(i,j)\sim\mathcal{D}}\mathbb{E}_{(v_{i},v_{j})\in
E_{i,j}}[\beta_{v_{i},v_{j}}]$
$\displaystyle=\mathbb{E}_{(i,j)\sim\mathcal{D}}\mathbb{E}_{p\in\mathcal{P}}[\beta_{p,i,j}]$
$\displaystyle=\mathbb{E}_{p\in\mathcal{P}}\mathbb{E}_{(i,j)\sim\mathcal{D}}[\beta_{p,i,j}].$

Say $p$ is atypical $\Pr_{(i,j)\in\mathcal{D}}[(p,i,j)\mbox{ is
good}]\geq\sqrt{\varepsilon}$. Since
$\Pr_{p\in\mathcal{P},(i,j)\in\mathcal{D}}[(p,i,j)\mbox{ is
good}]\leq\varepsilon$,

$\Pr_{p\in\mathcal{P}}[p\mbox{ is atypical}]\leq\sqrt{\varepsilon}.$

Fix a typical $p$. Then

$\mathbb{E}_{(i,j)\sim\mathcal{D}}[\beta_{p,i,j}]\geq\mathbb{E}_{(i,j)\sim\mathcal{D}}[\alpha_{i,p}\alpha_{j,p}^{2}-\varepsilon]-\sqrt{\varepsilon},$

since we can apply the lower bound $\beta_{p,i,j}$ by
$\alpha_{i,p}\alpha_{j,p}^{2}-\varepsilon$ with probability at least
$1-\sqrt{\varepsilon}$ and $0$ otherwise.

Now we analyze
$\mathbb{E}_{(i,j)\sim\mathcal{D}}[\alpha_{i,p}\alpha_{j,p}^{2}]$. Recalling
the definition of $\mathcal{D}$ and applying Cauchy-Schwarz,

$\mathbb{E}_{(i,j)\sim\mathcal{D}}[\alpha_{i,p}\alpha_{j,p}^{2}]\geq\mathbb{E}_{i\sim\mathcal{D}_{I},j\in\\{i+1,\dots,\ell\\}}[\alpha_{i,p}\alpha_{j,p}^{2}]\geq\mathbb{E}_{i\sim\mathcal{D}_{I},j,k\in\\{i+1,\dots,\ell\\}}[\alpha_{i,p}\alpha_{j,p}\alpha_{k,p}].$
(13)

We compare the RHS of (13) to

$\big{(}\mathbb{E}_{i}[\alpha_{i,p}]\big{)}^{3}=\mathbb{E}_{i,j,k\in[l]}[\alpha_{i,p}\alpha_{j,p}\alpha_{k,p}].$
(14)

If we fix $i<j<k$, the probability that the monomial
$\alpha_{i,p}\alpha_{j,p}\alpha_{k,p}$ contributes to the expectation, after
incorporating permutations between $i,j,k$, is $6/\ell^{3}$ in (14) and

$\frac{(\ell-i)^{2}}{\ell(\ell-1)(2\ell-1)/6}\cdot\frac{2}{(\ell-i)^{2}}=\frac{2\cdot
6}{\ell(\ell-1)(2\ell-1)}$

in (13), which is greater than $6/\ell^{3}$. Since $\Pr[i=j\mbox{ or
}j=k\mbox{ or }k=i]\leq\frac{3}{\ell}$ when we sample $i,j,k\in[\ell]$
independently,

$\mathbb{E}_{i\sim\mathcal{D}_{I},j,k\in\\{i+1,\dots,\ell\\}}[\alpha_{i,p}\alpha_{j,p}\alpha_{k,p}]\geq\mathbb{E}_{i,j,k\in[l]}[\alpha_{i,p}\alpha_{j,p}\alpha_{k,p}]-\frac{3}{\ell}=\big{(}\mathbb{E}_{i}[\alpha_{i,p}]\big{)}^{3}-\frac{3}{\ell}.$

Therefore, if $p$ is typical, then

$\mathbb{E}_{(i,j)\sim\mathcal{D}}[\beta_{p,i,j}]\geq\bigg{(}\mathbb{E}_{i\in[\ell]}[\alpha_{i}]\bigg{)}^{3}-\frac{3}{\ell}-2\sqrt{\varepsilon}.$

Using $\mathbb{E}_{p}\mathbb{E}_{i}[\alpha_{p,i}]\geq 1/2$ and Jensen’s
inequality,

$\displaystyle w(F)$
$\displaystyle=\mathbb{E}_{p\in\mathcal{P}}\mathbb{E}_{(i,j)\sim\mathcal{D}}[\beta_{p,i,j}]$
$\displaystyle\geq\mathbb{E}_{p\in\mathcal{P}}\bigg{[}\big{(}\mathbb{E}_{i\in[\ell]}[\alpha_{i}]\big{)}^{3}\bigg{]}-\frac{3}{\ell}-2\sqrt{\varepsilon}-\Pr_{p\in\mathcal{P}}[p\mbox{
is atypical}]$
$\displaystyle\geq\bigg{(}\mathbb{E}_{p\in\mathcal{P}}\mathbb{E}_{i\in[\ell]}[\alpha_{i}]\bigg{)}^{3}-\frac{3}{\ell}-3\sqrt{\varepsilon}$
$\displaystyle\geq\frac{1}{8}-\frac{3}{\ell}-3\sqrt{\varepsilon}.$

∎

###  4.4 Proof of Lemma 4.5

###### Proof.

Fix $i<j$ given in the condition of the lemma. Call an edge
$e=(v_{i},v_{j})\in E_{i,j}$ good if
$\beta_{v_{i},v_{j}}<\alpha_{v_{i}}\alpha_{v_{j}}^{2}-\varepsilon$. For
$v_{i}\in V_{i}$, let $f_{v_{i}}:C_{i}\to\\{0,1\\}$ be the indicator function
of $S\cap(\\{v_{i}\\}\times C_{i})$, and Let $v_{j}\in V_{j}$, let
$g_{v_{j}}:C_{j}\to\\{0,1\\}$ be the indicator function of
$S\cap(\\{v_{j}\\}\times C_{j})$.

The path regularity and the promise of the lemma implies that at least an
$\varepsilon$ fraction of $e\in E_{i,j}$ is good. Fix such an edge
$e=(v_{i},v_{j})$. For notational simplicity, let $\pi=\pi_{e}$,
$L=\Sigma_{i}$, $R=\Sigma_{j}$, $f:=f_{v_{i}}$ and $g:=g_{v_{j}}$.

We use the standard notations in analysis of boolean functions. See [Hås01,
O’D14] for references. For two functions $f_{1},f_{2}:C_{i}\to\mathbb{R}$, let
$\langle f_{1},f_{2}\rangle:=\mathbb{E}_{x\in\\{\pm
1\\}^{L}}[f_{1}(x)f_{2}(x)]$ be the inner product between $f_{1}$ and $f_{2}$.
For $A\subseteq L$, let $\chi_{A}:C_{i}\to\mathbb{R}$ defined as
$\chi_{A}(x)=\prod_{a\in A}x_{a}$. It is well known that
$\\{\chi_{A}\\}_{A\subseteq L}$ forms an orthonormal basis, so that $f$ can be
written as $\sum_{A\subseteq L}\widehat{f}(A)\chi_{A}$ with
$\widehat{f}(A)=\langle f,\chi_{A}\rangle$. Define
$\\{\chi_{B}\\}_{B\in\subseteq R}$ similarly and write $g$ as
$\sum_{B\subseteq R}\widehat{g}(B)\chi_{B}$.

Now note that $\alpha_{i}=\mathbb{E}_{x}[f(x)]=\widehat{f}(\emptyset)$,
$\alpha_{j}=\mathbb{E}_{y}[g(y)]=\widehat{g}(\emptyset)$, and
$\beta_{i,j}=\mathbb{E}_{x,y,z}[f(x)g(y)g(z)]$ where $x,y,z$ were jointly
sampled the reduction given $e$. Expanding Fourier decompositions for $f$ and
$g$,

$\displaystyle\mathbb{E}_{x,y,z}[f(x)g(y)g(z)]$
$\displaystyle=\sum_{A\subseteq L,B\subseteq R,C\subseteq
R}\widehat{f}(A)\widehat{g}(B)\widehat{g}(C)\mathbb{E}[\chi_{A}(x)\chi_{B}(y)\chi_{C}(z)]$
$\displaystyle=\sum_{B\subseteq
R,A\subseteq\pi(B)}\widehat{f}(A)\widehat{g}(B)^{2}\mathbb{E}[\chi_{A}(x)\chi_{B}(y)\chi_{B}(z)]$
$\displaystyle=\sum_{B\subseteq
R}\widehat{g}(B)^{2}\sum_{A\subseteq\pi(B)}\widehat{f}(A)\mathbb{E}[\chi_{A}(x)\chi_{B}(y)\chi_{B}(z)].$
(15)

The second equality holds because if $b\in B\setminus C$, then $\chi_{B}(y)$
contains $y_{b}$ and it is independent from any other variable appearing in
$\chi_{A}(x)\chi_{B}(y)\chi_{C}(z)$. Similarly, the existence of $c\in
C\setminus B$ or $a\in A\setminus(B\cup C)$ will make
$\chi_{A}(x)\chi_{B}(y)\chi_{C}(z)$ vanish.

Suppose $B\subseteq\pi^{-1}(a)$ for some $a\in L$. For each $b\in B$,
$\mathbb{E}[y_{b}z_{b}]=-1$ if $x_{a}=1$ and $(1-2\delta)$ otherwise, so

$\mathbb{E}[\chi_{B}(y)\chi_{B}(z)]=\frac{1}{2}\big{(}(-1)^{|B|}+(1-2\delta)^{|B|}\big{)},$

and

$\mathbb{E}[x_{a}\chi_{B}(y)\chi_{B}(z)]=\frac{1}{2}\big{(}(-1)^{|B|}-(1-2\delta)^{|B|}\big{)}.$

Therefore, if we consider $\mathbb{E}[\chi_{A}(x)\chi_{B}(y)\chi_{B}(z)]$ for
general $A\subseteq B$, letting $s_{a}:=|B\cap\pi^{-1}(a)|$,
$p_{s}:=((-1)^{s}+(1-2\delta)^{s})/2$, $q_{s}:=((-1)^{s}-(1-2\delta)^{s})/2$,
it is equal to

$\bigg{(}\prod_{a\in
A}q_{s_{a}}\bigg{)}\cdot\bigg{(}\prod_{a\in\pi(B)\setminus
A}p_{s_{a}}\bigg{)}.$ (16)

Note that $p_{s}^{2}+q_{s}^{2}\leq 1-\delta$ for any $s\geq 1$. Then for fixed
$B$,

$\displaystyle\sum_{A\subseteq\pi(B)}\big{(}\mathbb{E}[\chi_{A}(x)\chi_{B}(y)\chi_{B}(z)]\big{)}^{2}$
$\displaystyle\leq\sum_{A\subseteq\pi(B)}\mathbb{E}[(\chi_{A}(x)\chi_{B}(y)\chi_{B}(z))^{2}]$
$\displaystyle=\sum_{A\subseteq\pi(B)}\bigg{(}\prod_{a\in
A}q_{s_{a}}^{2}\prod_{a\in\pi(B)\setminus A}p_{s_{a}}^{2}\bigg{)}$
$\displaystyle=\prod_{a\in\pi(B)}(p_{s_{a}}^{2}+q_{s_{a}}^{2})$
$\displaystyle\leq(1-\delta)^{|\pi(B)|}.$

Finally, we analyze (15). When $B=\emptyset$, we get
$\widehat{f}(\emptyset)\widehat{g}(\emptyset)^{2}=\alpha_{i}\alpha_{j}^{2}$.
Say $B$ big if $|B|>\delta^{-2}$ and small if $1\leq|B|\leq\delta^{-2}$. Fix
large $B$ and $v\in V_{j}$, and consider a random edge $(u,v)\in E_{i,j}$.
Since $\mathcal{M}$ is $\eta$-smooth, the probability that
$|\pi(B)|\geq\delta^{-2}$ is at least $1-\eta\delta^{-4}$, so using
$(1-\delta)^{1/2\delta^{2}}\leq\delta$,

$\displaystyle\mathbb{E}_{(u,v)\in
E_{i,j}}(1-\delta)^{|\pi(\beta)|/2}\leq\delta+\eta\delta^{-4}.$

Therefore, for any fixed $v\in V_{j}$, we can bound (15) for big $B$ as:

$\displaystyle\mathbb{E}_{(u,v)\in E_{i,j}}\bigg{[}\bigg{|}\sum_{B\mbox{
big}}\widehat{g}(B)^{2}\sum_{A\subseteq\pi(B)}\widehat{f}(A)\mathbb{E}[\chi_{A}(x)\chi_{B}(y)\chi_{B}(z)]\bigg{|}\bigg{]}$
$\displaystyle\leq\quad$ $\displaystyle\mathbb{E}_{(u,v)\in
E_{i,j}}\bigg{[}\sum_{B\mbox{
big}}\widehat{g}(B)^{2}\bigg{(}\sum_{A\subseteq\pi(B)}\widehat{f}(A)^{2}\bigg{)}^{1/2}\bigg{(}\sum_{A\subseteq\pi(B)}\mathbb{E}[\chi_{A}(x)\chi_{B}(y)\chi_{B}(z)]^{2}\bigg{)}^{1/2}\bigg{]}$
$\displaystyle\leq\quad$ $\displaystyle\mathbb{E}_{(u,v)\in
E_{i,j}}\bigg{[}\sum_{B\mbox{
big}}\widehat{g}(B)^{2}(1-\delta)^{|\pi(\beta)|/2}\bigg{]}\leq\delta+\eta\delta^{-4}.$

Similarly, we can bound (15) for small $B$ and $A=\emptyset$. With probability
at least $1-\eta|\pi(B)|^{2}\geq 1-\eta\delta^{-4}$ we have
$|\pi(\beta)|=|\beta|$, and if this happens,
$\mathbb{E}[|\chi_{B}(y)\chi_{B}(z)|]\leq|p_{1}|=\delta$. Therefore,

$\displaystyle\mathbb{E}_{(u,v)\in E_{i,j}}\bigg{[}\bigg{|}\sum_{B\mbox{
small}}\widehat{g}(B)^{2}\widehat{f}(\emptyset)\mathbb{E}[\chi_{B}(y)\chi_{B}(z)]\bigg{|}\bigg{]}$
$\displaystyle\mathbb{E}_{(u,v)\in E_{i,j}}\bigg{[}\bigg{|}\sum_{B\mbox{
small}}\mathbb{E}[\chi_{B}(y)\chi_{B}(z)]\bigg{|}\bigg{]}$
$\displaystyle\eta\delta^{-4}+\delta.$

Finally, for small $B$ and $\emptyset\subsetneq A\subseteq\pi(B)$, we bound
(15) as

$\displaystyle\bigg{|}\sum_{B\mbox{
small}}\widehat{g}(B)^{2}\sum_{\emptyset\subsetneq
A\subseteq\pi(B)}\widehat{f}(A)\mathbb{E}[\chi_{A}(x)\chi_{B}(y)\chi_{B}(z)]\bigg{|}$
$\displaystyle\leq\quad$ $\displaystyle\bigg{(}\sum_{B\mbox{
small}}\widehat{g}(B)^{2}\sum_{\emptyset\subsetneq
A\subseteq\pi(B)}\widehat{f}(A)^{2}\bigg{)}^{1/2}\bigg{(}\sum_{B\mbox{
small}}\widehat{g}(B)^{2}\sum_{\emptyset\subsetneq
A\subseteq\pi(B)}\mathbb{E}[\chi_{A}(x)\chi_{B}(y)\chi_{B}(z)]^{2}\bigg{)}^{1/2}$
$\displaystyle\leq\quad$ $\displaystyle\bigg{(}\sum_{B\mbox{
small}}\widehat{g}(B)^{2}\sum_{\emptyset\subsetneq
A\subseteq\pi(B)}\widehat{f}(A)^{2}\bigg{)}^{1/2}.$

Since at least an $\varepsilon$ fraction of $e\in E_{i,j}$ is good, at least
an $\varepsilon/2$ fraction of $v\in V_{j}$ satisfies that at least an
$\varepsilon/2$ fraction of $(u,v)\in E_{i,j}$ is good. Call such $v$ good. If
$v$ is good,

$\displaystyle\varepsilon/2\leq\mathbb{E}_{(u,v)\in
E_{i,j}}\bigg{[}\bigg{|}\beta_{u,v}-\alpha_{u}\alpha_{v}^{2}\bigg{|}\bigg{]}\leq
2\delta+2\eta\delta^{-4}+\mathbb{E}_{(u,v)\in
E_{i,j}}\bigg{[}\bigg{(}\sum_{B\mbox{
small}}\widehat{g}(B)^{2}\sum_{\emptyset\subsetneq
A\subseteq\pi(B)}\widehat{f}(A)^{2}\bigg{)}^{1/2}\bigg{]}.$

Consider the randomized assignment where all $v\in V_{j}$ first chooses a set
$B\subseteq R$ with probability $\widehat{g}(B)^{2}$ and gets random $b\in B$.
(Similarly, $u\in V_{i}$ chooses a set $A\subseteq L$ with probability
$\widehat{f}(A)^{2}$ and gets random $a\in A$.) Since the sum of squared
Fourier coefficients is at most $1$ for every $f$ and $g$, this is a well-
defined strategy. For good $v$, it will satisfy at least a

$\frac{(\varepsilon/2-2\delta-2\eta\delta^{-4})^{2}}{|A||B|}\leq\delta^{4}(\varepsilon/2-2\delta-2\eta\delta^{-4})^{2}$

fraction of constraints incident on $v$ in expectation. Therefore, there is an
assignment between that satisfies at least an
$(\varepsilon\delta^{4}/2)\cdot(\varepsilon/2-2\delta-2\eta\delta^{-4})^{2}$
fraction of edges in $E_{i,j}$. ∎

###  4.5 Make instances dense

In this section, we show how to convert hard instances to ensure
$|H|=\omega(|V|^{2})$ while preserving hardness, finishing the proof of
Theorem 4.1. From the previous discussion, given an edge-weighted
$3$-hypergraph $\mathcal{H}=(V,H)$ with $n=|V|$, $m=|H|$, and $k=n/2$ (without
loss of generality, assume that the sum of weights is $1$), it is NP-hard to
distinguish whether (1) there exists $S\subseteq V$ that intersects every
hyperedge or (2) every $S\subseteq V$ with $|S|\leq n/2$ intersects hyperedges
of weight at most $(7/8+\varepsilon)$, for any constant $\varepsilon>0$.

Let $b=\max(n,m)^{\beta},c=b^{2.5}$ where $\beta$ is a constant chosen later.