Vincent Cohen-Addad

Inapproximability of Clustering in Lp metrics

Keywords: clustering, k-means, k-median, hardness of approximation, graph embedding

Proving hardness of approximation for min-sum objectives is an infamous challenge. For classic problems such as the Traveling Salesman problem, the Steiner tree problem, or the k-means and k-median problems, the best known inapproximability bounds for L-p metrics of dimension O(log n) remain well below 1.01.

In this paper, we take a significant step to improve the hardness of approximation of the k-means problem in various L-p metrics, and more particularly on Manhattan (L-1), Euclidean (L-2), Hamming (L-0) and Chebyshev (L-infinity) metrics of dimension log n and above.

We show that it is hard to approximate the k-means objective in O(log n) dimensional space:

(1) To a factor of 3.94 in the L-infinity metric when centers have to be chosen from a discrete set of locations (i.e., the discrete case). This improves upon the result of Guruswami and Indyk (SODA'03) who proved hardness of approximation for a factor less than 1.01. (2) To a factor of 1.56 in the L-1 metric and to a factor of 1.17 in the L-2 metric, both in the discrete case. This improves upon the result of Trevisan (SICOMP'00) who proved hardness of approximation for a factor less than 1.01 in both the metrics. (3) To a factor of 1.07 in the L-2 metric, when centers can be placed at arbitrary locations, (i.e., the continuous case). This improves on a result of Lee-Schmidt-Wright (IPL'17) who proved hardness of approximation for a factor of 1.0013. We also obtain similar improvements over the state of the art hardness of approximation results for the k-median objective in various L-p metrics.

Our hardness result given in (1) above, is under the standard NP is not equal to P assumption, whereas all the remaining results given above are under the Unique Games Conjecture (UGC). We can remove our reliance on UGC and prove standard NP-hardness for the above problems but for smaller approximation factors.

Finally, we note that in order to obtain our result for the L-1 and L-infinity metrics in O(log n) dimensional space we introduce an embedding technique which combines the transcripts of certain communication protocols with the geometric realization of certain graphs.

I. INTRODUCTION

Clustering is a classic, routinely-used process, to solve a large variety of problems. Case in point, it is used to carryout unsupervised learning, or to analyze large amount of data, or to solve information retrieval problems, or to detect communities in social networks. Given a dataset and a metric defined over the data elements, a clustering is a partition of the data such that similar data elements are in the same part. Hence, clustering allows to extract information from the data by identifying data elements that share common features. Clustering problems have thus become of fundamental importance and have received a considerable amount of attention through the years.

Arguably, the k-means and k-median objectives are the most successful models for clustering problems. They have been studied since the sixties and the most popular algorithms used in practice, such as the famous KMEANS++ algorithm [START_REF] Arthur | k-means++: the advantages of careful seeding[END_REF] or Lloyd's method, are designed so as to optimize the classic k-means objective: given a set of points P in a metric space, find a set of k points, called centers, in the metric space so as to minimize the sum of squared distances from each point to its closest center (see Section I-A for a slightly more formal definition). Similarly, the k-median objective asks to minimize the sum of distances from each point to its closest center.

Therefore, the question of designing algorithms for optimizing the k-means and k-median objectives has taken a preponderant role in both theory and practice. From a theory perspective, both problems are unfortunately NP-Hard, even when the underlying metric space is the Euclidean plane [START_REF] Megiddo | On the complexity of some common geometric location problems[END_REF] but admits a PTAS when d is a fixed constant [START_REF] Cohen-Addad | Local search yields approximation schemes for k-means and k-median in euclidean and minor-free metrics[END_REF], [START_REF] Friggstad | Local search yields a PTAS for k-means in doubling metrics[END_REF], [START_REF] Kolliopoulos | A nearly lineartime approximation scheme for the euclidean kmedian problem[END_REF], [START_REF] Cohen-Addad | A fast approximation scheme for lowdimensional k-means[END_REF], [START_REF] Cohen-Addad | Near-linear time approximation schemes for clustering in doubling metrics[END_REF]. Nonetheless, for several applications arising in machine learning and data analysis, the dimension of the point set corresponds to the number of features of the datasets, which is large for many datasets. Thus, researchers have considered the k-median and k-means in Euclidean space of arbitrary dimension, and also in more general metric spaces, or through the lenses of parameterized complexity. For general metric spaces, both problems are known to be hard to approximate within respectively a 1 + 2/e ≈ 1.73 and 1 + 8/e ≈ 3.94 factor since the late 90's [START_REF] Guha | Greedy strikes back: Improved facility location algorithms[END_REF]. After a long line of work, the best known approximation algorithms for general metric spaces achieve 2.67 and 9 approximation factors for k-median and k-means respectively [START_REF] Byrka | An improved approximation for k-median, and positive correlation in budgeted optimization[END_REF], [START_REF] Ahmadian | Better guarantees for k-means and euclidean k-median by primal-dual algorithms[END_REF]. Then it becomes natural and of practical significance to ask whether there exist better approximation algorithms for the Euclidean metric.

However, our understanding of the Euclidean clustering inputs is pretty limited. The best known hardness of approximation for O(log n)-dimensional p metrics, where p is finite, is due to the celebrated result of Trevisan [START_REF] Trevisan | When hamming meets euclid: The approximability of geometric TSP and steiner tree[END_REF] and remains below 1.01. While this result was later extended to ∞ metrics by Guruswami and Indyk [START_REF] Guruswami | Embeddings and nonapproximability of geometric problems[END_REF] who obtained comparable hardness bounds, little progress has been made over the last 15 years and the hardness of approximation for these problems remains below 1.01, even for the ∞ metric 1 . In fact, showing hardness of approximation in Euclidean space for min-sum objectives is a fundamental challenge. For most of the classic optimization problems in metric spaces such as the traveling salesman problem (TSP), Steiner tree (ST), or k-median and k-means, the best known hardness of approximation are also obtained through the work of Trevisan [START_REF] Trevisan | When hamming meets euclid: The approximability of geometric TSP and steiner tree[END_REF] and Guruswami and Indyk [START_REF] Guruswami | Embeddings and nonapproximability of geometric problems[END_REF], and also remain below 1.01. Even after the advances on hardness of approximation based on the unique games conjecture, no better hardness has been established for these problems in p -metrics.

This stands in sharp contrast to the best known approximation ratios for the k-means and k-median problems and creates a somewhat frustrating situation: for example, the current approximation ratio for the k-median in any p metric is the same as that for a general metric space (i.e., we are not able to leverage the geometry/topology of the pmetric space, for any p), while the hardness of approximation in the p -metrics is below 1.01 which is in contrast to the 1 + 2/e inapproximability for general metric spaces. A somewhat less frustrating case is the k-means problem, for which Ahmadian et al. [START_REF] Ahmadian | Better guarantees for k-means and euclidean k-median by primal-dual algorithms[END_REF] have recently shown how to use the structure of the 2 -metric to obtain an approximation ratio of 6.47 improving upon the approximation ratio of 9 for general metric space. Yet, the best known hardness of approximation for the k-means problem in the 2 -metric remains below 1.01.

This also stands in contrast with the problem of showing NP-hardness for computing exact solutions to clustering problems in p -metrics, a question which is much better understood. For example, when parameterized by the number of centers, k, both the k-median and k-means problems are known to be W [START_REF] Arthur | k-means++: the advantages of careful seeding[END_REF]-Hard, even in R 4 , and to not admit a better than n o(k) exact algorithm assuming the Exponential Time Hypothesis [START_REF] Cohen-Addad | The bane of low-dimensionality clustering[END_REF]. However, and perhaps surprisingly, a (1 + ε)-approximation algorithm running in time 2 k/ε O (1) nd [START_REF] De La Vega | Approximation schemes for clustering problems[END_REF], [START_REF] Kumar | A simple linear time (1+ ") -approximation algorithm for k-means clustering in any dimensions[END_REF] is known for the 2 -metric of arbitrary dimension d, while there is no better than 1+ 2 /e-factor approximation (for k-median) and 1+ 8 /e-factor approximation (for k-means) algorithms, for general metrics, running in time f (k, ε)n o(k) for any arbitrary computable function f , assuming the Gap Exponential Time Hypothesis [START_REF] Cohen-Addad | Tight FPT Approximations for k-Median and k-Means[END_REF].

Yet, in terms of hardness of approximation, no significant progress has been made. Bridging the gap between upper and lower bound on the approximability of the k-means and kmedian problems in Euclidean instances is thus an important open problem.

"Discrete" vs "Continuous".: Unfortunately, our poor understanding of the k-means and k-median problems does not stop here. To explain this we need to distinguish between two variants of the k-median and k-means problems: the discrete and the continuous. In the discrete case, centers have to be chosen from a specific set of so-called candidate centers that is part of the input, while in the continuous case, centers can be chosen arbitrarily in the p -metric space.

While hardness of approximation for the discrete variant has been known since the work of Trevisan [START_REF] Trevisan | When hamming meets euclid: The approximability of geometric TSP and steiner tree[END_REF] and Guruswami and Indyk [START_REF] Guruswami | Embeddings and nonapproximability of geometric problems[END_REF] as mentioned earlier, the hardness of the continuous version had remained an open problem for a while. Dasgupta first showed that the problem is NP-Hard in large dimensions [START_REF] Dasgupta | The hardness of k-means clustering[END_REF]. A recent work of Awasthi et al. [START_REF] Awasthi | The hardness of approximation of euclidean kmeans[END_REF] showed the APX-Hardness of the k-means problem in the Euclidean metric and the inapproximability bound was recently improved to 1.0013 by Lee et al. [START_REF] Lee | Improved and simplified inapproximability for k-means[END_REF]. Yet, we do not know of a better approximation algorithm for the continuous version and so the best known approximation algorithm achieves a 6.47-approximation.

Previous Approaches.: One of the main roadblock for obtaining higher hardness of approximation is perhaps the "degree constraint". More concretely, the embedding technique that is used by Trevisan [START_REF] Trevisan | When hamming meets euclid: The approximability of geometric TSP and steiner tree[END_REF] for p -metrics, where p is finite, and by Guruswami and Indyk [START_REF] Guruswami | Embeddings and nonapproximability of geometric problems[END_REF] for the ∞metric requires to reduce from a "bounded degree" instance of a covering problem, such as vertex cover on bounded degree graphs. However, the hardness of approximation for these problems is very close to 1 and, combined with the loss induced by the embedding, this cannot lead to a hardness greater than 1.01. For example, the recent approach of Awasthi et al. [START_REF] Awasthi | The hardness of approximation of euclidean kmeans[END_REF] and Lee et al. [START_REF] Lee | Improved and simplified inapproximability for k-means[END_REF] is a reduction from vertex cover on triangle-free graphs which introduces a direct embedding for the k-means problem. Unfortunately, the gap of the reduction is also a function of the degree of the input graph, and so requires that the instance of vertex cover has bounded degree.

We bypass the above barriers in two ways. We first provide better reductions, based on the vertex coverage problem (maximization variant of the vertex cover problem), which through a careful analysis leads to a higher gap in O(n) dimensions. While these reductions are satisfactory for the 2metric, since they imply hardness of approximation for the problems in O(log n)-dimensional space using the Johnson-Lindenstrauss lemma [START_REF] Johnson | Extensions of Lipschitz mappings into a Hilbert space[END_REF], they only lead to hardness of approximation for the problems in 1and ∞ -metrics of dimension Ω(n). We then use a interesting, and perhaps surprising, blend of communication protocol and embedding techniques to extend the result to O(log n)-dimensional space. We discuss these ideas further in Section I-B.

A. Our Results

Given two sets of points P and C in a metric space, we define the k-means cost of P for C as the For every p ∈ R ≥1 ∪ {∞}, we define two quantities ζ 1 (p) and ζ 2 (p) (see Section III for details). The behavior of these quantities is quite intricate, but for our purpose it suffices to know their values for p = 1, 2, and ∞. We show that

ζ 1 (1) = 1.1416, ζ 2 (1) = 1.5664, ζ 1 (2) ≈ 1.06, ζ 2 (2) ≈ 1.1709, and as p → ∞, we have ζ 1 (p) → ζ 1 (∞) = ζ 1 (1) and ζ 2 (p) → ζ 2 (∞) = ζ 2 (1).
1) Inapproximability Results with Candidate Centers: We start by presenting our results on the "discrete" k-median and k-means problems. In these versions, the centers must be chosen from a specific set of points of the metric. We start with an informal statement below and note that some of the results are under the unique games conjecture (UGC).

Theorem I.1 (Informal statement). Given n points and poly(n) candidate centers in O(log n)-dimensional space it is NP-hard to approximate

• the k-means objective within a 1.17 factor in 2 -metric (under UGC), 1.56 factor in 1 -metric (under UGC), and 1 + 8 /e ≈ 3.94 in ∞ -metric. • the k-median objective within a 1.06 factor in 2 -metric (under UGC), 1.14 factor in 1 -metric (under UGC), and 1 +2 /e ≈ 1.73 in ∞ -metric.

Our above results generalizes to any p -metric, with a bound which depends on the underlying metric and on the problem.

Theorem I.2 (Informal statement of Theorems VII.1 and VII.2). Let p ∈ R ≥1 ∪ {∞}. Assuming UGC, given n points and poly(n) candidate centers in O(log n) dimensional p -metric space it is NP-hard to distinguish between the following two cases:

• Completeness: The k-means objective (resp. k-median objective) is at most β (resp. β ), • Soundness: The k-means objective (resp. k-median objective) is at least ζ 2 (p) • β (resp. ζ 1 (p) • β ),
where β (resp. β ) is some positive real number depending only on n.

Note that the hardness of approximation factor for the ∞metric, given in Theorem I.2 is worse than the one stated in Theorem I.1. This is because, the result in Theorem I.2 follows from combining the hardness of approximation of the vertex coverage problem (under UGC) with certain graph embeddings into p -metrics, whereas, the result in Theorem I.1 for the ∞ -metric follows from combining the hardness of approximation of the hypergraph vertex coverage problem with certain hypergraph embeddings, which currently yield meaningful results only for the ∞ -metric.

2) Inapproximability Results without Candidate Centers: We then move to the "continuous" version of the problems. Here, centers can be placed anywhere in the metric space.

Theorem I.3 (k-means in Euclidean metric; Informal statement of Theorem VII.4). Assuming UGC, given n points in O(log n) dimensional Euclidean space it is NP-hard to distinguish between the following two cases:

• Completeness: The k-means objective is at most β,

• Soundness: The k-means objective is at least 1.07 • β, where β is some positive real number depending only on n. Moreover, the above hardness holds even when the n points have all their coordinate entries in {0, 1}.

For the k-median problem without candidate centers, it is in fact more natural to consider the 1 -metric. Indeed, given a set of points in the 2 -metric, computing the median of this set of points is hard, even in the Euclidean plane and no exact algorithm is known. However, in the case of the Theorem I.4 (k-median in 1 -metric; Informal statement of Theorem VII.3). Assuming UGC, given n points in O(log n) dimensional 1 -metric space it is NP-hard to distinguish between the following two cases:

• Completeness: The k-median objective is at most β,

• Soundness: The k-median objective is at least 1.07 • β, where β is some positive real number depending only on n. Moreover, the above hardness holds even when the n points have all their coordinate entries in {0, 1}.

The above theorem is obtained through an intermediate hardness of approximation proof for k-median in the Hamming metric (see Theorem V.2). Also, Theorem I.3 can be extended to the Hamming metric so as to obtain a slightly higher inapproximability gap of 1.21 (see Theorem V.1). Typically, it is possible to extend hardness in the Hamming metric to hardness in the edit metric for similarity search type problems. We formalize this intuition and extend Theorem I.2 to the edit metric as well (see Theorems A.2 and A.3).

Next, we discuss about the hardness results that we can obtain under the more standard NP = P assumption. From the exciting progress on the unique games conjecture [START_REF] Khot | On independent sets, 2-to-2 games, and grassmann graphs[END_REF], [START_REF] Dinur | Towards a proof of the 2-to-1 games conjecture?[END_REF], [START_REF]On non-optimally expanding sets in grassmann graphs[END_REF], [START_REF] Barak | Small-set expansion in shortcode graph and the 2-to-2 conjecture[END_REF], [START_REF] Khot | Pseudorandom sets in grassmann graph have near-perfect expansion[END_REF], [START_REF] Bhangale | Ug-hardness to np-hardness by losing half[END_REF], we can get the following unconditional NP-hardness for approximate vertex coverage problem.

Theorem I.5 (Essentially combining [START_REF] Bhangale | Ug-hardness to np-hardness by losing half[END_REF] and [START_REF] Austrin | Global cardinality constraints makes approximating some max-2-csps harder[END_REF]). There is some ε > 0 and d 0 ∈ N, such that for all d min > d 0 , deciding an instance (G, k) of (0.9807 -ε)-vertex coverage problem on minimum degree d min graphs is NP-hard. Now we may define for every p ∈ R ≥1 ∪ {∞}, ζ 1 (p) and ζ 2 (p). Again for our purpose we only define them for p = 1, 2, and ∞:

ζ 1 (1) = 1.04, ζ 2 (1) = 1.15, ζ 1 (2) ≈ 1.02, ζ 2 (2) ≈ 1.05, and as p → ∞, we have ζ 1 (p) → ζ 1 (∞) = ζ 1 (1) and ζ 2 (p) → ζ 2 (∞) = ζ 2 (1).
We can then combine Theorem I.5 with the embedding given in the proof of Theorem I.2 to get the hardness of approximation results of Theorem I.2 where ζ i (p) is now replaced by ζ i (p) for i ∈ {1, 2}, and we are no longer reliant on UGC. Similarly, we also get NP-hardness (without UGC) as in Theorems I.3 and I.4, but for approximation factors roughly equal to 1.02.

Finally, we summarize in Table I, the state-of-the-art inapproximability factors for the discrete and continuous cases of the k-means and k-median problems in various metric spaces.

B. Proof Overview

We now give an overview of our techniques. 1) Warm up: To better understand the state of the art for the hardness of approximation for clustering problems and the different barriers to obtain hardness of approximation for k-median and k-means, let us recall the result of Guha and Khuller [START_REF] Guha | Greedy strikes back: Improved facility location algorithms[END_REF] who showed the 1+2/e hardness of approximation for k-median in general metric spaces.

Given an instance of the set cover problem, where S denote the sets and U denote the universe, create an instance of the k-median (or k-means) instance by creating a candidate center c S for each set S ∈ S and a point p u to be clustered for each element u ∈ U. Then, set the distances from p u to each c S such that u ∈ S to be 1 and from p u to each c S such that u / ∈ S to be 3. Other distances are set so as to satisfy the triangle inequality. It is then easy to see that the instance generated is a metric. Now, standard inapproximability result for set cover or for variants such as set coverage imply that it is hard to distinguish between an instance where there is a set of size k covering the universe, and an instance where no set of size k covers more than a (1-1/e) of the universe. Thus, this implies that it is hard to distinguish between an instance of the k-median problem where all points are at distance exactly 1 from their center, and so of cost |U| and an instance where for any set of k centers, the number of points at distance 1 is at most (1 -1/e)|U| (and the remaining ones are at distance 3). Hence, hard to distinguish between an instance of cost |U| and an instance of cost (1 + 2/e)|U|.

While this reduction yields high inapproximability results in general metric spaces, and so in ∞ -metrics of dimension Ω(n) through the Fréchet embedding of general metric spaces to ∞ , it seems unrealistic that it can be adapted to

1 -or 2 -metrics, or even O(log n)-dimensional ∞ -metrics.
This is mainly due to the high degree of the hard set cover instances. Indeed, let d ∈ N and δ ∈ (0, 1) be such that d > 1 1-δ 2 . Then it seems unlikely that we can embed (in any dimension) every d-regular graph into 2 metric space such that every pair of vertices which had an edge are at distance δ and every non-adjacent pair are at distance 1. The intuition for the previous statement stems from Theorem 5 in [START_REF] Maehara | Dispersed points and geometric embedding of complete bipartite graphs[END_REF], which is a special case of the above claim. In other words, the above claim basically says that the maximum gap one can hope for is poly(1/d). This is a constant only when d is a constant.

Another argument for this to be an important roadblock is given recent advances on the parameterized complexity of the problem (parameterized by k), we observe that high dimensional Euclidean space admits a PTAS for k-median and k-means, while arbitrary metric spaces don't (assuming Gap-ETH). The proof that general metric spaces don't admit a fixed-parameter approximation schemes is very similar and so, having an embedding to high dimensional Euclidean space of the above type of instances would contradict Gap-ETH.

2) Inapproximability in High Dimensions: To obtain our hardness results in high dimensions we will start from the α-vertex coverage problem: given a graph G(V, E) and a parameter k as input, the goal is to distinguish between the following two cases. The Completeness case: There exists S := {v 1 , . . . , v k } ⊆ V such that each edge of E is adjacent to at least one vertex of S, and the Soundness case: For every S := {v 1 , . . . , v k } ⊆ V at most an α fraction of the edges are adjacent to a vertex of S. This problem will serve for both the discrete and continuous cases (namely the problem where centers have to be picked at specific location and the problem where centers can be picked arbitrarily). We have that the (0.9292 -ε)vertex coverage problem is NP-hard (under unique games conjecture).

Our way of circumventing the problems with embedding the set cover instance (discussed in previous subsubsection) is to reduce from the maximization variant instead of the covering variant as done in previous works [START_REF] Trevisan | When hamming meets euclid: The approximability of geometric TSP and steiner tree[END_REF], [START_REF] Guruswami | Embeddings and nonapproximability of geometric problems[END_REF], [START_REF] Awasthi | The hardness of approximation of euclidean kmeans[END_REF], [START_REF] Lee | Improved and simplified inapproximability for k-means[END_REF]. The observation is the that a clustering problems are not covering problems therefore all previous works implicitly paid a factor equal to the degree of the graph in the approximation factor while moving from the vertex cover problem to the clustering problem. By directly using results on the vertex coverage problem, we avoid this. It allows us to look at embeddings where the degree does not inhibit, on the contrary we use the fact that the degree is large to our benefit in some of of our results. Also, there was no techniques developed in previous works to address all p -metrics for the clustering problems. We make an interesting connection to contact dimension of a graph, motivated by recent advances in hardness of approximation in fine-grained complexity [START_REF] David | On the complexity of closest pair via polar-pair of point-sets[END_REF], [START_REF] Karthik | On closest pair in euclidean metric: Monochromatic is as hard as bichromatic[END_REF]. Elaborating, from the vertex coverage instance G = (V, E) we create the bipartite graph on partite sets V and E where we have an edge (i, {j, j }) ∈ V × E if and only if i = j or i = j . Then, we show that embedding this graph so that adjacent vertices are at distance at most β and non-adjacent vertices are at distance at least λβ. From there our inapproximability result follows.

3) Dimension Reduction: Extending our result to O(log n)-dimensional space while preserving the gap is a challenge for 1 -and ∞ -metric since dimension reduction is very limited for these metrics.

Before we dive into this, let us make the following observation. For the 2 -metric and the k-means objective, the cost of the k-means objective can be expressed as the sum over all clusters of the sum of pairwise distances of points in the cluster divided by the size of the cluster (see Fact V.6). Thus, it has long been known that dimension reduction using the Johnson-Lindenstrauss lemma preserve the cost of the solutions by a (1 + ε) 2 factor. Hence, we will simply use this to obtain a hardness of approximation for the Euclidean k-means problem in O(log n) dimension.

Inspired by the recent connections between communication complexity and the hardness of approximation for (geometric) fine-grained and parameterized problems [START_REF] Abboud | Distributed PCP theorems for hardness of approximation in P[END_REF], [START_REF] Karthik | On the parameterized complexity of approximating dominating set[END_REF], [START_REF] Chen | On the hardness of approximate and exact (bichromatic) maximum inner product[END_REF] we develop a O(log n) dimensional embedding technique for all p -metrics. An appealing feature of this embedding is that it arises naturally out of the transcript of a (one-way) communication protocol for two-players, where one player is given a vertex of the graph and the other player is given an edge in the graph and the goal is to determine if the vertex covers the edge. We develop non-trivial randomized protocols using algebraic-geometric codes for the aforementioned communication problem, and show how to interpret the transcript to obtain an embedding for both inputs (i.e., the vertex and the edge).

C. Organization of the Paper

Section II introduces some notations and relevant coding theory concepts and results that will be used throughout the paper. Section III discusses graph embedding in pmetrics, which form a critical gadget for our hardness results. Section IV shows our result for the "discrete case", namely when centers have to be picked from a prescribed set. Our results of this section apply to high dimensional spaces, namely when the dimension of the input points is Θ(n). Section V presents our proofs for the "continuous" versions, where centers can be placed at arbitrary locations, also in the case of high dimensional inputs. Sections VI and VII presents our dimensionality reduction framework. Finally, Section VIII presents some interesting open problems. II. PRELIMINARIES Notations.: For any two points a, b ∈ R d , the distance between them in the p -metric is denoted by a -

b p = d i=1 |a i -b i | p 1/p . Their distance in the ∞ - metric is denoted by a -b ∞ = max i∈[d] {|a i -b i |}, and in the 0 -metric is denoted by a -b 0 = |{i ∈ [d] : a i = b i }|, i.e.
, the number of coordinates on which a and b differ. For every n ∈ N, we denote by [n] the set of first n natural numbers, i.e., {1, . . . , n}. We denote by [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 1 2 , the vector that is 1 /2 on all coordinates.

A. Error Correcting Codes

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

Theorem II.1 ( [START_REF] Garcia | On the asymptotic behaviour of some towers of function fields over finite fields[END_REF], [START_REF] Shum | A low-complexity algorithm for the construction of algebraic-geometric codes better than the Gilbert-Varshamov bound[END_REF]). For every prime square q greater than 49, there is a code family over alphabet of size q of positive constant (depending on q) rate and relative distance at least 1 -3 √ q . Moreover, the encoding time of any code in the family is polynomial in the message length.

The following is an informal argument justifying the existence of the above code family. Fix q a prime square greater than 49.

The authors in [START_REF] Garcia | On the asymptotic behaviour of some towers of function fields over finite fields[END_REF] provide us with a family of curves C = {C i } i∈N over F q such that for every ∈ N, we have that C has at least rational points and genus at most g := 2 / √ q. Fix ∈ N. Let P be a rational point on C . Consider the Riemann-Roch space L (m • P ) where m = 3 √ q . This has dimension at least m + 1 -g = / √ q + 1. Also, any two elements have at most m common zeroes among the rational points of C . Pick any set S of F q -rational points of C that does not contain P . Then the code is given by the evaluations of elements of L (m • P ) at the points of S. The dimension of the code is greater than / √ q. Therefore the rate is greater than 1 / √ q. Also the relative distance of the code is at least 1 -m / = 1 -3 / √ q as any two codewords agree on at most m coordinates. Finally, the efficient encoding of such a code was given in [START_REF] Shum | A low-complexity algorithm for the construction of algebraic-geometric codes better than the Gilbert-Varshamov bound[END_REF].

In fact, random codes obtaining weaker parameters than the parameters stated above (see Gilbert-Varshamov bound [START_REF] Gilbert | A comparison of signalling alphabets[END_REF], [START_REF] Varshamov | Estimate of the number of signals in error correcting codes[END_REF]) suffice for us 2 , but there is no known explicit efficient construction of such codes to the best of our knowledge. It may 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.

III. GADGET CONSTRUCTIONS VIA GRAPH EMBEDDINGS

In this section, we first introduce the notion of graph embedding that is of interest to this paper. And then we prove some bounds on the embedding for important pmetrics. 2 To be precise, we need for some infinite increasing sequence (q i ) i∈N and some increasing function f : N → N, a code family over alphabet of size q i of positive constant (depending on q) rate, relative distance at least 1 -1 f (q i ) , and efficient encoding.

Let K r t denote the complete r-uniform hypergraph on t vertices (i.e., has all t r possible hyperedges). Let I be an operator on hypergraphs which maps every hypergraph to its incidence graph. More formally, for any hypergraph H(V, E) we define I(H) to be the bipartite graph on partite sets V and E where we have an edge (i, J) ∈ V × E in I(G) (i.e., J ⊆ V ) if and only if i ∈ J. For every t, r ∈ N, consider the incidence bipartite graph of the complete hypergraph on t vertices of uniformity (arity) r, which we denote by H * (t, r) := I(K r t ). The vertex set of H * (t, r) is the partite sets A * (t) := [t] and B * (t, r) := [t] r and (i, J) is an edge in H * (t, r) if and only if i ∈ J.

We would like to analyze the embedding of H * (t, r) into p -metric spaces for all p ∈ R ≥1 ∪ {∞}. Definition III.1 (Gap Realization of a Bipartite graph). Let p ∈ R ≥1 ∪ {∞}. For any bipartite graph G = (A ∪B, E) and λ ≥ 1, a mapping τ : V → R d is said to λ-gap-realize G (in the p -metric) if for some β > 0, the following holds:

(i) For all (u, v) ∈ E, τ (u) -τ (v) p = β. (ii) For all (u, v) ∈ (A×B)\E, we have τ (u)-τ (v) p ≥ λ • β.
Moreover, we require that τ λ-gap-realize G in the p -metric efficiently, i.e., there is a polynomial time algorithm (in the size of G) which can compute τ .

We remark here that the above definition is a variant of the notion gap contact dimension introduced in [START_REF] Karthik | On closest pair in euclidean metric: Monochromatic is as hard as bichromatic[END_REF] in the sense that the authors in [START_REF] Karthik | On closest pair in euclidean metric: Monochromatic is as hard as bichromatic[END_REF] required that for all distinct u, v both from A or both from B, τ (u)-τ (v) p ≥ λ•β and for all (u, v) ∈ (A × B) \ E, we have τ (u) -τ (v) p > β. They were also interested in the size of the dimension on to which the graph was embedded. Finally, we note that the notion of contact dimension (i.e., with any gap greater than 1) has been studied in literature since the early eighties [START_REF] Pach | Decomposition of multiple packing and covering[END_REF], [START_REF] Maehara | Contact patterns of equal nonoverlapping spheres[END_REF], [START_REF] Frankl | Embedding the n-cube in lower dimensions[END_REF], [START_REF]On the contact dimensions of graphs[END_REF], [START_REF] Maehara | Dispersed points and geometric embedding of complete bipartite graphs[END_REF], [START_REF] David | On the complexity of closest pair via polar-pair of point-sets[END_REF].

Definition III.2 (Gap number). Let p ∈ R ≥1 ∪ {∞}. For any bipartite graph G = (A ∪B, E), its gap number in the p -metric g p (G) is the largest λ for which there exists a mapping τ that λ-gap-realizes G in a d-dimensional pmetric space 3 where d ≤ |A| + |B|.

In this paper, we are interested in analyzing g p (H * (t, r)) for all t, r ∈ N and p ∈ R ≥1 ∪ {∞}. We prove the following upper bound4 :

Proposition III.3. Let t ≥ 3, r ≥ 2, and p ∈ R ≥1 ∪ {∞}. If r < t then g p (H * (t, r)) ≤ 3. Proof: Let S = [r -1]. Let T = S ∪ {r} and T = S ∪ {r + 1}.
Let τ be a λ-gap-realization of H * (t, r) in the p -metric. Then, we have for some β > 0, that τ (r)-τ (T ) p = τ (r-1)-τ (T ) p = τ (r-1)-τ (T ) p = β.

But we also have have that τ (r) -τ (T ) p ≥ λβ. From triangle inequality this implies λ ≤ 3.

We can meet the above bound in the ∞ -metric as shown below.

Lemma III.4. For all t ≥ 3 and r ≥ 2, we have g ∞ (H * (t, r)) = 3.

Proof: For the ∞ -metric consider the mapping τ : A * (t) ∪ B * (t, r) → R t defined as follows. For every u ∈ A * (t), we define

τ (u) = e u + 1 2 ,
and for every J ∈ B * (t, r) (i.e., J ∈

[n] r ), we define τ (J) = i∈J e i .
Fix some u ∈ A * (t) and J ∈ B * (t, r) such that u ∈ J. Then we have that

η := τ (J) -τ (u) =   i∈J\{u} e i   - 1 2 . Since η ∈ { -1 /2, 1 /2} t , we have that η ∞ = τ (J) - τ (u) ∞ = 1 /2.
On the other hand if we fix some u ∈ A * (t) and J ∈ B * (t, r) such that u / ∈ J then we have that

τ (J) -τ (u) ∞ ≥ |(τ (J)) u -(τ (u)) u | = 3 2 .
Thus we have that τ , 3-gap-realizes H * (t, r) in the ∞metric. Finally, the equality on the gap number follows from Proposition III.3.

Next, we consider the 1 -metric and show that we can meet Proposition III.3 for r = 2.

Lemma III.5. For all t ≥ 3 and r ≥ 2, we have g 1 (H * (t, r)) ≥ r+1 r-1 . Proof: For the 1 -metric consider the mapping τ : A * (t) ∪ B * (t, r) → {0, 1} t defined as follows. For every u ∈ A * (t), we define

τ (u) = e u ,
and for every J ∈ B * (t, r) (i.e., J ∈ [n] r ), we define

τ (J) = i∈J e i .
Fix some u ∈ A * (t) and J ∈ B * (t, r) such that u ∈ J. Then we have that

τ (J)-τ (u) = i∈J\{u} e i ⇒ τ (J)-τ (u) 1 = |J|-1 = r-1.
On the other hand if we fix some u ∈ A * (t) and J ∈ B * (t, r) such that u / ∈ J then we have that

τ (J) -τ (u) 1 = i∈J e i -e u 1 = |J| + 1 = r + 1.
Thus we have that τ , r+1 r-1 -gap-realizes H * (t, r) in the 1 -metric. Now we focus our attention to bounding the gap number in the Euclidean metric. We focus on bounding the gap number of H * (t, r) where r = 2, as we only use it later for this fixing of r.

Lemma III.6. For all t ≥ 3, we have

g 2 (H * (t, 2)) ≥ 2 √ ( √ 2-1) 2 +1
≈ 1.848.

Proof: Consider the mapping τ : A * (t) ∪ B * (t) → {0, 1} t defined as follows. For every u ∈ A * (t), we define

τ (u) = √ 2 • e u ,
and for every {u, v} ∈ B * (t), we define

τ ({u, v}) = e u + e v .
Let i, j, j ∈ [t] be three distinct numbers. We have

τ (i) -τ ({i, j}) 2 = e i ( √ 2 -1) + e j 2 = ( √ 2 -1) 2 + 1, and
τ (i) -τ ({j , j}) 2 = √ 2 • e i + e j + e j 2 = 2.
This implies τ ,

2 √ ( √ 2-1) 2 +1
-gap realizes H * (t, 2) in the 2 -metric. We wrap up our computation of gap numbers by showing that as p grows the gap number of H * (t, r) in the p -metric approaches 3. The proof of the below lemma is very similar to the proof of Lemma III.4 but we provide it nonetheless for the sake of completeness.

Lemma III.7. For all t ≥ 3 and r ≥ 2, we have that for every ε > 0 there exists p ∈ N such that g p (H * (t, r)) > 3 -ε.

Proof: Fix t ≥ 3, r ≥ 2, and ε > 0. Let p ∈ N such that t 1/p < 1+ ε /3. Consider the mapping τ : A * (t)∪B * (t, r) → R t defined as follows. For every u ∈ A * (t), we define

τ (u) = e u + 1 2 .
and for every J ∈ B * (t, r) (i.e., J ∈ [n] r ), we define

τ (J) = i∈J e i .
Fix some u ∈ A * (t) and J ∈ B * (t, r) such that u ∈ J. Then we have that

η := τ (J) -τ (u) =   i∈J\{u} e i   - 1 2
.

Since η ∈ { -1 /2, 1 /2} t , we have that η p = τ (J)τ (u) p = t 1/p /2. On the other hand if we fix some u ∈ A * (t) and J ∈ B * (t, r) such that u / ∈ J then we have that

τ (J) -τ (u) p ≥ |(τ (J)) u -(τ (u)) u | = 3 2 .
Thus we have that τ , 3 t 1/p -gap-realizes H * (t, r) in the p -metric. Finally note that 3

t 1/p > 9 3+ε = 3 -3ε 3+ε > 3 -ε.
For most of the results in this paper, we will only use the gap numbers of H * (t, r) when r = 2, and therefore for compactness of statements in the future, we introduce the following.

Definition III.8. For all p ∈ R ≥1 ∪ {∞}, we define γ p = min

t≥3 g p (H * (t, 2)).
Finally, we conclude this section by showing a 'hereditary' property of our embedding which will be invoked for all applications.

Proposition III.9. Let G be a r-uniform hypergraph on t ≥ 3 vertices and let H := I(G). Let τ be a λ-gap realization of H * (t, r) in the p -metric. Then τ restricted to the vertices of H is a λ-gap realization of H in the p -metric. In particular, for r = 2, there exists a mapping τ * which is a γ p -gap realization of H in the p -metric.

We skip the proof of the above proposition as it follows in a straightforward manner from Definition III.1.

IV. INAPPROXIMABILITY OF k-means AND k-median WITH CANDIDATE CENTERS IN HIGH DIMENSIONS

In this section, we prove Theorem I.2 but in high dimensions by a reduction from the gap vertex coverage problem. First, we define the gap vertex coverage problem.

Let G(V, E) be a graph. Let S ⊆ V . We define the cover of S, denoted by cov(S) as follows:

cov(S) = {e ∈ E | ∃v ∈ S such that v ∈ e}.
Definition IV.1 (α-vertex coverage). In the α-vertex coverage problem, we are given a graph G(V, E) and a parameter k as input. We would like to distinguish between the following two cases:

• Completeness: There exists S := {v 1 , . . . , v k } ⊆ V such that cov(S) = E. • Soundness: For every S := {v 1 , . . . , v k } ⊆ V we have |cov(S)| ≤ α • |E|.
We recall that the minimum degree of a graph is said to be d min ∈ N if every vertex in the graph has degree at least d min . Strong inapproximability results were given for the vertex coverage problem in5 [START_REF] Austrin | Inapproximability of vertex cover and independent set in bounded degree graphs[END_REF]. Recently, Austrin and Stanković provided the tight inapproximability result, which is stated below.

Theorem IV.2 (Austrin and Stanković [START_REF] Austrin | Global cardinality constraints makes approximating some max-2-csps harder[END_REF]). There is some ε > 0 and d 0 ∈ N, such that for all d min > d 0 , assuming the unique games conjecture, deciding an instance (G, k) of (0.9292 -ε)-vertex coverage problem on minimum degree d min graphs is NP-hard.

We remark here that [START_REF] Austrin | Global cardinality constraints makes approximating some max-2-csps harder[END_REF] computed the inapproximability factor up to 3 decimal places, and the above hardness of approximation factor follows from additional computation. Also note that in [START_REF] Austrin | Global cardinality constraints makes approximating some max-2-csps harder[END_REF] the hardness is not shown for minimum degree d min graphs6 but if we look at the removal of vertex weights step in Section 4 of [START_REF] Austrin | Inapproximability of vertex cover and independent set in bounded degree graphs[END_REF] then we can take large enough number of copies (> d min ) of each vertex (proportional to its weight) and this will ensure the theorem as stated above.

Another important remark is that the hardness results of [START_REF] Austrin | Inapproximability of vertex cover and independent set in bounded degree graphs[END_REF], [START_REF] Austrin | Global cardinality constraints makes approximating some max-2-csps harder[END_REF] are for multigraph instances of the vertex coverage problem. However, in this paper, we treat that the hard instances of Theorem IV.2 are simple graphs for the sake of brevity. This assumption is reasonable, because in all our reductions, we realize every edge of the graph as a point in space, and in the case of a multigraph, we realize two edges with the same pair of end points, as two distinct points, where one of the points is just a slightly perturbed version of the other point. It is then clear that all points which correspond to edges with the same pair of end points, will be in the same cluster, in the optimal solution.

Next we define for every p ∈ R ≥1 ∪ {∞},the quantities ζ 1 (p) and ζ 2 (p) as follows:

ζ 1 (p) := 0.9292 + (γ p • 0.0708) and , ζ 2 (p) := 0.9292 + (γ 2 p • 0.0708). Again notice that ζ 1 (1) = 1.1416, ζ 2 (1) = 1.5664, ζ 1 (2) ≈ 1.06, ζ 2 (2) ≈ 1.1709, and as p → ∞, we have ζ 1 (p) → ζ 1 (∞) = ζ 1 (1) and ζ 2 (p) → ζ 2 (∞) = ζ 2 (1).
Now, we state our inapproximability results for k-means and k-median in high dimensions. for some constant β > 0.

Proof of Theorems IV.3 and IV.4 : Starting from a hard instance of (0.9292 -ε)-vertex coverage problem G = (V, E) which is guaranteed by Theorem IV.2, we create an instance of the k-means, or of the k-median problem using the embedding given in Proposition III.9 as follows. Let τ be the embedding of G := I(G) prescribed by Proposition III.9. We think of G as G(V ∪ B, E) where V is simply the vertex set of the (0.9292 -ε)-vertex coverage instance, and B is obtained by defining a vertex b i,j for each edge (u i , u j ) of the (0.9292 -ε)-vertex coverage instance, and E is obtained by defining an edge from each vertex

u i ∈ V to each vertex b i,j ∈ B.
The k-median or k-means instance consists of the set of candidate centers C and the set of points to be clustered P defined as follows:

P = {τ (v) | v ∈ B} and C = {τ (u) | u ∈ V }.
We now analyze the k-means and k-median cost of the instance. Consider the completeness case first.

Completeness.: In this case, we know that there is a set S ⊂ V such that |S| = k and S covers all the edges of the (0.9292 -ε)-vertex coverage instance G. We focus on the set of centers C induced by S, namely

C = {τ (u i ) | u i ∈ S} ⊆ C.
Since each edge (u i , u j ) is adjacent to at least one element of S, we have that for every τ (b i,j ), the following holds:

S = {v ∈ V | τ (v) ∈ C }.
By the assumptions of the soundness case, S covers at most (0.9292 -ε)|E| number of edges of G. For each such edge, e = (u i , u j ), we have that the contribution of τ (e) to the k-means cost is exactly β 2 , and to the k-median cost is exactly β. By the definition of the gadget τ , we have that for any other edge e = (u i , u j ) that is not covered by S, the contribution of τ (e) to the k-median and k-means cost is respectively γ p •β and γ 2 p •β 2 . Therefore, the optimal solution w.r. We would like to conclude this section by remarking that the hardness of approximation results for the ∞metric given above are strictly weaker than the known hardness of approximation factors for this metric [START_REF] Guha | Greedy strikes back: Improved facility location algorithms[END_REF]. By a straightforward application of the Fréchet embedding 7 to the constructions in [START_REF] Guha | Greedy strikes back: Improved facility location algorithms[END_REF], we obtain the NP-hardness of approximating k-means (resp. k-median) to a factor better than 1 + 8 /e (resp. 1 + 2 /e). These inapproximability factors are much higher than the ones given in Theorems IV.3 and IV.4. However, our main contribution as far as the ∞ -metric is concerned is to obtain the same inapproximability factor as [START_REF] Guha | Greedy strikes back: Improved facility location algorithms[END_REF] but in low dimensions (i.e., O(log n) dimensions). This result is proven in Section VII-C.

V. INAPPROXIMABILITY OF k-median AND k-means WITHOUT CANDIDATE CENTERS IN HIGH DIMENSIONS

In this section, we prove Theorems I.3 and I.4 but in high dimensions. In particular, in Section V-A we show our inapproximability results for the k-median and k-means objectives without candidate centers in the Hamming metric.

In Section V-B, we show our inapproximability result for the k-median objective without candidate centers in the 1metric. Finally, in Section V-C, we show our inapproximability result for the k-means objective without candidate centers in the 2 -metric.

A. Inapproximability in Hamming metric

In this subsection, we prove our inapproximability results for the k-median and k-means objectives without candidate centers in the Hamming metric. Our proof considers the same reduction from the gap vertex coverage problem as described in the proofs of Theorem IV.3 and IV.4, but performs the completeness and soundness analysis for the case where there is no candidate centers set given as part of the input. Theorem V.1 (k-means without candidate centers in n O (1) dimensional Hamming metric space). Assuming the unique games conjecture, given a point-set P ⊂ {0, 1} m of size n (and m = poly(n)) and a parameter k as input, it is NP-hard to distinguish between the following two cases: dimensional Hamming metric space). Assuming the unique games conjecture, given a point-set P ⊂ {0, 1} m of size n (and m = poly(n)) and a parameter k as input, it is NP-hard to distinguish between the following two cases:

• Completeness: There exists C := {c 1 , . . . , c k } ⊆ {0, 1} m and σ : P → C such that a∈P a -σ(a) 0 ≤ n,

• Soundness: For every C := {c 1 , . . . , c k } ⊆ {0, 1} m and every σ : P → C we have:

a∈P a -σ(a) 0 ≥ 1.07 • n.
Proof of Theorems V.1 and V.2: Starting from an instance of (0.9292 -ε)-vertex coverage problem G = (V, E), we create an instance of the k-means, or of the k-median problem using the 3-gap realization mapping τ for the 1 -metric given in Lemma III.5 (by setting r = 2) as follows. First note that τ maps points to the Boolean hypercube and for a pair of points on the Boolean hypercube the distances in the Hamming and 1 -metric are the same. Let τ be the embedding of G := I(G) prescribed by Lemma III.5. We think of G as G(V ∪ B, E) where V is simply the same set of vertices as the vertex set of vertices of the vertex coverage instance, B is obtained by defining a vertex b i,j for each edge (u i , u j ) of the vertex coverage instance, and E is obtained by defining an edge from each vertex u i ∈ V to each vertex b i,j ∈ B.

The k-median or k-means instance without candidate centers is just the set of points P := {τ (v) | v ∈ B} that we would like to cluster. In particular notice that for all v ∈ B we have τ (v) 0 = 2. We now analyse the k-means and k-median cost of the instance. Consider the completeness case first.

Completeness.: In that scenario, pick a vertex coverage V * of the instance and focus on the set of centers C * induced by V * , namely

C * = {τ (u i ) | u i ∈ V * }.
Since by definition of vertex coverage, each edge (u i , u j ) is adjacent to at least one element of V * and so for each point τ (b i,j ) we have that min c∈C * τ (b i,j ) -c 2 0 = 1 = min c∈C * τ (b i,j ) -c 0 . The k-means and k-median cost of the overall instance is at most |E|. Thus, let's turn to the soundness case.

Soundness.: Consider any set of centers then its distance from the center is 1; but if it is contained in N σ * c then its distance from the center is 3. Therefore we have that there are at least (0.0708 + ε)|E| -4|V | edges that are distance at least 2 from their allocated center according to the clustering σ * . Notice that in Theorem IV.2 we can choose the minimum degree of G to be as large a constant as we want. We choose it to be greater than 8/ε. In this case we have that |E| ≥ 4|V |/ε. Therefore, the optimal solution w.r. We can thus conclude the proof of the above theorem by proving Claim V.3.

C * = {c 1 , . . . , c k } ⊆ {0, 1} |V | that is optimal for the k-median or k-means objective. Fix some arbitrary i ∈ [k]. Note that if c i 0 ≥ 4 then, c i -τ (u) ≥ 2
Proof of Claim V.3: Now we show how to construct σ * from σ. Consider c ∈ C 3 . Let the three coordinates where c is 1 be i, j, j . We think of i, j, j as vertices in G. Let F = {(i, j), (i, j ), (j, j )}. For any edge not in F its distance to C 3 is 3 from c. If any of the points corresponding to i, j, j under τ was picked in our set of centers then, we could replace c by another point in τ (i), τ (j), τ (k). If this is not the case then only the edges in E ∩ F would be at distance 1 from c, and for the rest we could choose some point in C 1 or C 0 . Thus we would obtain a new optimal classification in which points assigned to c would be at most 3. Similar (and simpler) argument holds for c ∈ C 2 as any two edges under τ are at distance 2.

B. Inapproximability of k-median in 1 -metric

In this subsection, we prove Theorem I.4 but in high dimensions. At a high level, our proof simply considers the hard instances built in the Hamming metric in Theorem V.2, and notes that the optimum cluster centers for those instances in the 1 -metric must have coordinate entries in {0, 1}. Theorem V.4 (k-median without candidate centers in n O (1) dimensional 1 -metric space). Assuming the unique games conjecture, given a point-set P ⊂ {0, 1} m of size n (and m = poly(n)) and a parameter k as input, it is NP-hard to distinguish between the following two cases: Proof: The proof follows from a simple observation and mimicking the proof of Theorem V.2. Recall first that given a set of z integers X = {x 1 , . . . , x z }, we have that a median of X is a point x * that minimizes z i=1 |x * -x i |. Note that if X contains an even number of points, then the median is not unique, nonetheless, there is always at least one point of X minimizing z i=1 |x * -x i |. We refer to these points as the discrete medians.

Thus, consider a set of points P in a dimensional 1metric space. The points p * that minimizes p∈P p -p * 1 is therefore the point p * whose ith coordinate is the median of the ith coordinates of the points in P .

Hence, consider an instance of the k-median problem in Hamming metric as defined in the proof of Theorem V.2 and apply the same construction to obtain an instance in 1 . We have that for this instance all the coordinates of the points to be clustered are in {0, 1}. Thus, for any subset (i.e. cluster) of the points of the instance, an optimal center of the set is such that its ith coordinate is the median of a set of values in {0, 1}. From the above discussion, we conclude that assuming that the ith coordinate is also in {0, 1} is without loss of generality. It follows that for any clustering, we can assume that the centers induced by the partition have coordinates in {0, 1}.

Therefore, the rest of the proof follows by applying the same reasonning than in the proof of Theorem V.2 since the instance created behaves in 1 metric like the instance described in the proof of Theorem V.2 in Hamming metric.

C. Inapproximability of k-means in Euclidean metric

In this section, we prove Theorem I.3 but in high dimensions.

Theorem V.5 (k-means without candidate centers in n O(1) dimensional 2 -metric space). Assuming the unique games conjecture, given a point-set P ⊂ {0, 1} m of size n (and m = poly(n)) and a parameter k as input, it is NP-hard to distinguish between the following two cases: Proof: Let ε > 0 and (G = (V, E), k) be an instance of the (0.9292-ε)-vertex coverage problem on graph of minimum degree at least ε -1 0 := 20 ε 4 . By Theorem IV.2, for some ε > 0, we have that deciding such an instance is NP-hard, assuming the unique games conjecture.

We build a set of points P as follows 8 : for each edge e ui,uj , we create a point p i,j whose ith and jth coordinates are both 1 and whose remaining coordinates are all 0. We say that p i,j is the point corresponding to edge e ui,uj . We thus have the following fact: Fact V.6. Consider two edges e, f . If e = (u i , u j ) and f = (u i , u ) then p i,j -p i, 2 2 = 2. If e = (u i , u j ) and f = (u r , u ), where r, / ∈ {i, j} then p i,j -p r, 2 2 = 4. We now prove the completeness and soundness cases.

Completeness.: In the completeness case, we show that the cost of the optimal solution is at most |E| -|V |/2. By definition, there exists a vertex cover S of size k = n/2 of the instance. Define a partition of the edge set into k parts by assigning each edge it to one of its extremity that is in S, let {C 1 , . . . , C k } be the partition induced by the assignment. Note that since there exists such a vertex cover, such a partition is indeed possible. We now bound the kmeans cost of solution {C 1 , . . . , C k }. We claim that for each cluster

C i , cost(C i ) = m i -1, where m i = |C i |.
Indeed, let v j be the vertex covering all edges of C i . Observe first that the jth coordinate of the centroid of C i is 1. The remaining coordinates of the centroid of C i are 0 except for m i of them which are 1/m i .

Then, for a given edge

(v j , v ), the k-means cost of the corresponding point is (1 -1/m i ) 2 + (m i -1)(1/m i ) 2 = 1-2/m i +m 2 i +1/m i -1/m 2 i which is 1-1/m i .
Summing up over all the m i edges of C i yields that cost(C i ) = m i -1. Therefore, the total k-means cost of the clustering is mn/2.

Soundness: In the soundness case, we show that the optimal k-means cost is at least (1.114 -2ε)|E| -|V |. We will use the following classic fact about the k-means objective.

Fact V.7. Given a clustering {C 1 , . . . , C k }, the k-means cost is exactly k i=1 1 2|C i | p∈Ci q∈Ci p -q 2 2
Now, consider an optimal clustering {C 1 , . . . , C k } of the instance in the soundness case. For each cluster C i , we define the graph G i to be the subgraph of the graph G induced by the edges whose corresponding points are in C i . We let ∆ i be the maximum degree in G i . We have the following claim. Claim V.8. For any cluster C i such that 8 The construction described here is equivalent to using the 1.848-gap realization mapping τ for the 2 -metric given in Lemma III.6 in the following way. The k-median or k-means instance without candidate centers is just the set of points P := {τ (e) | e ∈ E} that we would like to classify. In particular notice that for all e ∈ E we have τ (e) 2 2 = 2.

|C i | ≥ 10/ε 3 , we have cost(C i ) ≥ 2(1 -ε)|C i | -(1 + ε)∆ i .
Assume Claim V.8 is true for a moment. Then, the proof of the lemma can be completed as follows. First, observe that since the number of clusters is k = n/2 and the graph G has at least 10n/ε 4 , the total number of edges in clusters C i such that |C i | < 10/ε 3 is at most εm/2. Let's assume the cost for these edges is 0 and let's focus on the cost of clusters of size at least 10/ε 3 , let k be the number of such clusters. Summing up over all such clusters we have that the total k-means cost is at least

k i=1 2(1 -ε)|C i | -(1 + ε)∆ i ≥ (2 -3ε)m -(1 + ε) k i=1 ∆ i .
Then, to provide a lower bound on ∆ i , consider the set S obtained by picking a vertex of degree ∆ i from each G i . This set has size at most n/2 and so by definition of the soundness case the sum of the degrees of the vertices in S in G is at most (0.9292-ε)m. It follows that the cost of the optimal solution is at least 2m -

((1 + ε)0.9292 -4ε)m which is at least (1.0708 -O(ε)) • m as stated.
We can thus conclude the proof of the above theorem by proving Claim V.8.

Proof of Claim V.8: Consider a cluster C i such that |C i | ≥ 10/ε 3 . Consider an edge e = (u , u j ) whose corresponding point p is in C i . By Facts V.7 and V.6 we have that

1 2|C i | q∈Ci p -q 2 2 = 1 2|C i | (2(d i, + d i,j -2) + 4(|C i | -d i, -d i,j + 2)) ,
where d i, , d i,j are the degrees of vertices u , u j respectively in G i . Now, summing up over all edges in C i this gives a total cost for the cluster C i of

|C i | 2|C i | (4|C i |) - 2 2|C i | e=(u ,uj )∈Ci (d i, + d i,j -2) which is 2|C i | + 2 - 1 |C i | uj d 2 i,j .
We now need to provide an upper bound on 1 |Ci| uj d 2 i,j . First, consider the set S of vertices u j such that d i,j < ε|C i | and let m 0 i be the number of edges with at least one extremity in S. We have that

1 |C i | uj ∈S d 2 i,j ≤ ε|C i | |C i | uj ∈S d i,j ≤ 2εm 0 i . (1)
We then bound uj / ∈S d 2 i,j . Let S be the set of vertices with degree larger than ε|C i | in G i . Moreover, let m 1 i be the set of edges with both extremities in S . We start by arguing that m 1 i < εm. We have that uj ∈S d i,j ≤ m 1 i + |C i | and so, there exists a vertex u j in S such that d i,j ≤ (m 1 i + |C i |)/|S |. Thus, since d i,j ∈ S , we have that d i,j > ε|C i | and so (m

1 i + |C i |)/|S | ≥ ε|C i | ≥ εm 1 i . This implies that |S |m 1 i ≤ (m 1 i + |C i |)ε -1 . Now, assume towards contra- diction that m 1 i > ε|C i |. Then |S | < ε -1 (ε -1 + 1). Combining this with the fact that ε|C i | ≤ (m 1 i + |C i |)/|S |, we have that |C i |(|S | -1) ≤ m 1 i ≤ |S |(|S |-1)

2

. Hence,

|C i | ≤ |S |/2 ≤ ε -1 (ε -1 + 1) and so |C i | ≤ 10ε -3 , a contradiction. Therefore m 1 i ≤ ε|C i |. We can now bound uj / ∈S d 2 i,j . We have uj / ∈S d 2 i,j ≤ ∆ i uj / ∈S d i,j ≤ ∆ i (1 + ε)|C i |. (2)
Finally, combining Equations 1 and 2 we deduce that

1 |Ci| uj d 2 i,j ≤ 2ε|C i | + (1 + ε)∆ i . Therefore, cost(C i ) ≥ 2(1 -ε)|C i | -(1 + ε)∆ i .
1) k-means in Euclidean Metric over Reals in Low Dimensions: In this subsection, we prove Theorem I.3 albeit over real vectors. Theorem V.9 (k-means in Euclidean metric in O(log n) dimensions without Candidate Centers over Reals). Let ε be an arbitrarily small constant. Assuming the unique games conjecture, given a point-set P ⊂ R d of size n (and d = O(log n)) and a parameter k as input, it is NP-hard to distinguish between the following two cases:

• Completeness: There exists C := {c 1 , . . . , c k } ⊆ R d and σ : P → C such that a∈P a -σ(a) 2 2 ≤ βn,
• Soundness: For every C := {c 1 , . . . , c k } ⊆ R d and every σ : P → C we have:

a∈P a -σ(a) 2 2 ≥ (1.07 -ε) • βn,
for some constant β > 0.

Proof: By Theorem V.5, we have that given a set of points P ∈ R O(n) , it is hard to distinguish between the following cases:

• Completeness: There exists C := {c 1 , . . . , c k } ⊆ R d and σ : P → C such that a∈P a -σ(a) 2 2 ≤ βn,
• Soundness: For every C := {c 1 , . . . , c k } ⊆ R d and every σ : P → C we have:

a∈P a -σ(a) 2 2 ≥ 1.07 • βn,
The proof of Theorem V.9 follows from the Johnson-Lindenstrauss lemma and the following well-known observation. Given a set of n points in R d , we have that by Fact V.7 the k-means cost of a given partition {C 1 , . . . , C k } can be expressed as

k i=1 1 2|Ci|
x,y∈Ci x -y 2 2 . Thus, applying the Johnson-Lindenstrauss lemma with target dimension O(log n/ε 5 ) for small enough ε, yields an instance where the k-means cost of any clustering C is within a factor (1 + ε) of the k-means cost of C in the original d-dimensional instance. It follows that the gap is preserved up to a (1 + ε) factor and the theorem follows.

Note that this can be made deterministic (for example, see the result of Engebretsen et al. [START_REF] Engebretsen | Derandomized dimensionality reduction with applications[END_REF]).

VI. EMBEDDING VIA COMMUNICATION PROTOCOLS

In this section, we introduce our (hyper)graph embedding technique, which will enable us to prove the same hardness results as in Sections IV and V but for point-sets in O(log n) dimensions.

A. One-Way Communication Model and Protocols

In this subsection, we first introduce a communication model known in literature as the one-way communication model.

The two-player One-Way Communication (OWC) model was introduced by Yao [START_REF] Yao | Some complexity questions related to distributive computing (preliminary report)[END_REF] and has been extensively studied in literature [START_REF] Kushilevitz | Communication Complexity[END_REF]. One-Way Communication Model. Let X and Y be two finite sets. Let f : X × Y → {0, 1}. In the two-player oneway communication model, we have Alice and Bob each with an input x ∈ X and y ∈ Y respectively, and the communication task is for Bob to determine if f (x, y) = 1. In this model, only Alice is allowed to send messages to Bob. In the randomized setting, we allow the players to jointly toss some random coins before sending messages, i.e., we allow public randomness. Moreover, we assume that the sets X , Y are public knowledge.

Next, we introduce the notion of OWC protocols, which are in a nutshell one-round randomized protocols where the players are in a computationally bounded setting. OWC Protocols. Let π be a communication protocol for a problem in the OWC model. We say that π is a (r, µ, α, s)-OWC protocol if the following holds:

• The protocol is one-round with public randomness, i.e., the following actions happen sequentially: 1) The players receive their inputs.

2) The players jointly toss r random coins.

3) Alice on seeing the randomness (i.e. results of r coin tosses) deterministically sends an µ-bit message to Bob. 4) Based on the µ bits sent from Alice and randomness r, Bob outputs accept or reject.

• The protocol has completeness 1 and soundness s, i.e., -If f (x, y) = 1, then Bob always accepts.

-If f (x, y) = 0, then Bob accepts with probability at most s.

• We have that the expected number of distinct messages that Alice could send (on randomness r) which Bob would accept is α, where the expectation is over the randomness r.

• The players are computationally bounded, i.e., all of them perform all their computations in poly(|X |+|Y|)time. In a (r, µ, α, s)-OWC protocol, we refer to r as the randomness complexity of the protocol, µ as the message complexity of the protocol, α as the acceptance complexity of the protocol, and s as the soundness of the protocol. We note here that while the randomness complexity and message complexity are standard measures of interest in literature, the acceptance complexity is non-standard but the measure is important for our embedding later. We note here that the acceptance complexity is closely related to the free bit complexity measure studied in PCP literature [START_REF] Bellare | Free bits, pcps, and nonapproximability-towards tight results[END_REF]. For every c-left bounded f , there is a trivial (deterministic) (0, log |X |, c, 0)-OWC protocol. We would like to use randomness to do better on the message complexity.

Theorem VI.2. Let X and Y be sets of size m and n respectively. Let f : X × Y → {0, 1} be a c-left bounded function. For every prime square q c 4 , there is a (O q (1) + log log m, log 2 q , α, c( 3 / √ q))-OWC protocol for f , where

c 1 - c 2 3 √ q ≤ α ≤ c.
Proof: Let C be the code guaranteed by Theorem II.1 over alphabet of size q of message length β := log q m, block length := O q (β), and relative distance at least 1 -3 / √ q.

The protocol.: Alice on receiving input x ∈ X and Bob on receiving input y ∈ Y follow the below protocol.

1) Alice and Bob pick a uniformly random r ∈ [ ].

2) Alice sends Bob s := C(x) r , i.e., the r th coordinate of the encoding of x. 3) Bob computes the set of field elements, S := {C(a) r } a∈Sy , i.e., the r th coordinate of the encoding of all a ∈ S y . 4) Bob accepts if and only if s ∈ S.

Parameters.: It is clear that the above protocol adheres to the structure of an OWC protocol. We now show the specific parameters of the protocol claimed in the theorem statement hold. Alice's message is a field element and thus sends log 2 q bits. The randomness complexity is clearly log 2 = O q (1) + log Soundness.: Suppose that f (x, y) = 0. This implies that x / ∈ S y . This implies that for any a ∈ S y , we have that C(a) and C(x) agree on at most (3/ √ q) coordinates.

As before, by taking a union bound we have that there are at most c (3/ √ q) coordinates of [ ] on which C(x) agrees with C(a) for some a ∈ S y . Therefore for the remaining coordinates Bob would reject. This implies that Bob rejects with probability at least 1 -c(3/ √ q).

By Theorem II.1, the computation time for Alice and Bob is polynomial time.

Informally, for large enough q the above theorem gives a (log log m, O(1), c(1 -o(1)), o(1))-OWC protocol for f . This should be compared with the trivial (0, log m, c, 0)-OWC deterministic protocol for f that was mentioned earlier. We rewrite the vertex coverage problem that we had introduced in Section IV as a special case of the more general max coverage problem. This is done so as to enable us to prove stronger hardness of approximation factors for the ∞ -metric.

Definition VI.4 ((freq, gap)-max coverage). In the (freq, gap)-max coverage problem, we are given a universe U of size n, a collection S of m subsets of U where each element in U appears in exactly freq number of subsets in S, and a parameter k as input. We would like to distinguish between the following two cases: S i = U.

• Soundness: For every S 1 , . . . , S k ∈ S we have

i∈[k] S i ≤ gap • |U |.
We can now rewrite our Theorem IV.2 as follows:

Theorem VI.5 (Austrin and Stanković [START_REF] Austrin | Global cardinality constraints makes approximating some max-2-csps harder[END_REF]). There is some ε > 0 and d 0 ∈ N, such that for all d min > d 0 , assuming the unique games conjecture, deciding an instance (U, S, k) of (2, 0.9292-ε)-max coverage problem where |U| = n and |S| = poly(n), and each set in S is of cardinality at least d min is NP-hard.

We are now ready to state our main connection between OWC-protocols and k-means and k-median inapproximability. For every γ ∈ {0, 1} r and every q ∈ {0, 1} µ we define T S (S, γ) = q if in the OWC model where Alice and Bob are trying to compute Mem m,n : S × U → {0, 1}, Alice given input S, following the protocol Π would send q on randomness γ. Similarly, we define R u,γ ⊆ {0, 1} µ , where q ∈ {0, 1} µ is contained in R u,γ if and only if Bob given input u, following the protocol Π would accept the message q sent by Alice on randomness γ. Then, we define T

U (u, γ) = R u,γ if |R u,γ | = freq and T U (u, γ) =⊥ otherwise.
For every possible randomness γ ∈ {0, 1} r let c γ be the number of distinct messages that Bob would accept on input u and randomness γ. Note that E γ∈{0,1} r [c γ ] = α. Let δ := α + 1 -freq. From a standard averaging argument, it is easy to see that for every u ∈ U there is a subset L u of {0, 1} r of size 2 r • δ such that for all γ ∈ L u we have T U (u, γ) =⊥.

Now we can construct functions T

U : U → R d•2 r and T S : S → R d•2 r
as follows:

∀γ ∈ {0, 1} r , T U (u)| γ = τ (T U (u, γ)) if T U (u, γ) =⊥ τ ( u) otherwise and T S (S)| γ = τ (T S (S, γ)),
where u is any arbitrary element in B * such that u is a superset of R u,γ .

Completeness.: Suppose there exist S 1 , . . . , S k ∈ S such that

i∈[k] S i = U. Then, we define C = { T S (S i ) | i ∈ [k]}.
We define σ : P → C as follows: for every a ∈ P, where a := T U (u) for some u ∈ U, let σ(a) be equal to T S (S i ) such that u ∈ S i (if there is more than one i ∈ [k] for which S i contains u then we choose one arbitrarily). Fix a := T U (u) in P. Let c := σ(a) be the image of S i under T S . By definition of σ we have that u ∈ S i . Therefore, Mem m,n (S i , u) = 1, and Bob would accept Alice's message for every randomness if both of them follow Π.

Fix the randomness γ. Since Mem m,n (S i , u) = 1 we have that T S (S i , γ) ∈ R u,γ and thus we have τ (T S (S i , γ)) -τ (T U (u, γ)) p p = β p . Summing over all the blocks of coordinates we have: Fix some u ∈ U . Let Bad ⊆ {0, 1} r such that for all γ ∈ Bad Bob would reject Alice's message, if both of them follow Π. Similarly, let Good ⊆ {0, 1} r such that for all γ ∈ Good Bob would accept Alice's message, if both of them follow Π. We have |Good| ≤ s • 2 r and |Bad| ≥ (1 -s) • 2 r .

T U (u) -T S (S i ) p =   γ∈Lu τ (T S (S i , γ)) -τ (T U (u, γ)) p p   1/p = 2 r/p • β (3)
Fix γ ∈ Bad∩L u . Since Mem m,n (S, u) = 0 we have that T S (S, γ) / ∈ R u,γ and thus we have τ (T S (S i , γ)) -τ (T U (u, γ)) p p ≥ λ p β p . Summing over all the blocks of coordinates we have:

T U (u) -T S (S i ) p ≥   γ∈Bad∩Lu τ (T S (S i , γ)) -τ (T U (u, γ)) p p   1/p = 2 r/p • λ • β • (δ -s) 1/p • (4)
On the other hand, if we fix some u ∈ U \ U then, we have that (3) holds.

Finally, it is easy to see that T U and T S can be computed in polynomial time as Π is a OWC protocol where the players are bounded to run in poly(|U|, |S|) time.

VII. INAPPROXIMABILITY OF k-median

a -σ(a) p ≥ ζ 1 (p) • βn(log n) 1/p ,
for some constant β > 0.

Proof of Theorems VII.1 and VII.2: At a high level, we use the embedding developed in Proposition III.9 on the instances built in Theorem VI.6 with the protocol of Theorem VI.2 (setting q to be a super large constant and noting freq to be 2), and then finally use the inapproximability given in Theorem VI.5 to prove the theorems. We provide some additional details below.

Consider the (r, µ, α, s) protocol given in Theorem VI.2. Fix some δ > 0 and c = 2. For large enough q we have that s < δ and α ∈ (2 -δ, 2]. It is clear that the point-sets P and candidate centers C are in dimension 2 Oq(1)+log log m = O q (1) • log m = O q (log n).

Fix p ∈ R ≥1 ∪ {∞}. Plugging the above calculation into Theorem VI.6, for some fixed constant β > 0 we have that in the completeness case that the k-median cost in p -metric is at most β • n(log n) 1/p (and the k-means cost in 1 -metric would be at most nβ 2 (log n) 2/p ). In the soundness case we have that the k-median cost in p -metric is at least

β • n • (log n) 1/p • (0.0708 • γ p • (1 -2δ) 1/p + 0.9292) = β • n • (log n) 1/p • ζ 1 (p).
Similarly from a simple computation of the k-means cost in (4) we have the k-means cost in p -metric would be at least

β • n • (log n) 2/p • (0.0708 • γ 2 p • (1 -2δ) 2/p + 0.9292) = β • n • (log n) 2/p • ζ 2 (p).
Note that we can choose δ to be as small as we want.

B. k-median in 1 -metric without Candidate Centers

In this subsection, we prove Theorem I.4. We also show Theorem I.3 (now over Boolean vectors).

Theorem VII.3 (k-median in 1 -metric in O(log n) dimensions without Candidate Centers). Assuming the unique games conjecture, given a point-set P ⊂ {0, 1} d of size n (and d = O(log n)) and a parameter k as input, it is NPhard to distinguish between the following two cases: Proof: Simply note that after fixing the randomness, the problem on most blocks looks exactly like the instances considered in Theorem V.2, so the same arguments go through with arbitrarily small loss in approximation factor, in case we restricted our centers to be Boolean valued. Then notice that the translation of the hardness from Hamming metric to 1 -metric as in Theorem V.4 also holds here. Proof: Simply note that after fixing the randomness, the problem on most blocks looks exactly like the instances considered in Theorem V.5, so the same arguments go through with arbitrarily small loss in approximation factor.

C. Stronger Inapproximability of k-means and k-median in

∞ -metric

In this section, we prove the result for the ∞ -metric given in Theorem I.1 by a reduction from the gap hypergraph coverage problem. First, we define the gap hypergraph coverage problem.

Let G(V, E) be a hypergraph. Let S ⊆ V . We define the cover of S, denoted by cov(S) as follows: cov(S) = {e ∈ E | ∃v ∈ S such that v ∈ e}.

Definition VII.5 (α-hypergraph coverage). In the αhypergraph coverage problem, we are given a hypergraph G(V, E) and a parameter k as input. We would like to distinguish between the following two cases:

• Completeness: There exists S := {v 1 , . . . , v k } ⊆ V such that cov(S) = E. • Soundness: For every S := {v 1 , . . . , v k } ⊆ V we have |cov(S)| ≤ α • |E|.

We remark here that the hardness of approximation of the minimization version of the hypergraph coverage problem was already shown by Trevisan nearly two decades ago [START_REF] Trevisan | Non-approximability results for optimization problems on bounded degree instances[END_REF], but standard techniques to convert inapproximability results for optimization problems from minimization instances to maximization instances does not yield the requisite (or even any meaningful) hardness of approximation result that is stated in Theorem VII.6. Nonetheless a careful analysis of the original inapproximability of the max-coverage problem by Feige [START_REF] Feige | A threshold of ln n for approximating set cover[END_REF] yields the following.

Theorem VII.6 (Hypergraph Coverage Inapproximability; Essentially [START_REF] Feige | A threshold of ln n for approximating set cover[END_REF]). For every δ > 0 there is some h ∈ N such that deciding an instance of (1 -1 /e -ε)-hypergraph vertex coverage problem on h-uniform hypergraphs is NP-hard.

Below are the results in focus of this subsection. Proof of Theorems VII.7 and VII.8: At a high level, we use the hypergraph embedding developed in Lemma III.4 on the instances built in Theorem VI.6 with the protocol of Theorem VI.2 (setting q to be a super large constant and noting freq to be some large h ∈ N), and then finally use the inapproximability given in Theorem VII.6 to prove the theorems. I, and in particular to improve upon the inapproximability results of this paper. In this regard, a direction worth pursuing is to design suitable OWC-protcols (for example with acceptance complexity close to 2, arbitrarily small constant soundness, and not too high randomness) for the membership function corresponding to the hypergraph coverage problem. Combining such a protocol with Theorems VI.6 and VII.6 would enable us to prove close to (1 + 8/e) ≈ 3.94 inapproximability for k-means in the 1metric and roughly 1.88 inapproximability for k-means in the Euclidean metric (we refer to both the problems in the discrete case here).

VIII. OPEN PROBLEMS It remains an important open question to improve upon any of the hardness of approximation results given in Table

Another interesting open question is to improve upon the (1 + 8/e) inapproximability of k-means or the (1 + 2/e) inapproximability of k-median for any metric space. An obvious barrier to getting such an improvement by starting from the max coverage problem is the triangle inequality.

Finally, we raise the following combinatorial geometry question: can we improve the lower bound given in Lemma III.6? In particular, can we show that g 2 (H * (t, 2)) ≥ 2 for large enough t? Notice that when t = 3, we have g 2 (H * (2, 2)) ≥ 2 by placing the six points on the vertices of a regular hexagon in the plane. On the other hand, we suspect that g 2 (H * (t, 2)) ≤ 2, and confirming such a claim would also be interesting.

2 and

 2 the k-median cost as the p∈P min c∈C dist(p, c) . Given a set of points P , the k-means (respectively k-median) objective is the minimum over all C of cardinality k of the k-means (respectively k-median) cost of P for C. Given a point p ∈ P , the contribution to the kmeans (respectively k-median) cost of p is min c∈C (dist(p, c)) 2 (respectively min c∈C dist(p, c)).

Theorem IV. 3

 3 (k-means with candidate centers in n O(1) dimensional p -metric space). Let p ∈ R ≥1 ∪{∞}. Assuming the unique games conjecture, given a point-set P ⊂ R m of size n (and m = poly(n)), a collection C of m candidate centers in R m , and a parameter k as input, it is NP-hard to distinguish between the following two cases:• Completeness: There exists C := {c 1 , . . . , c k } ⊆ C and σ : P → C such that a∈P a -σ(a) 2 p ≤ β 2 n,• Soundness: For every C := {c 1 , . . . , c k } ⊆ C and every σ : P → C we have:a∈P a -σ(a) 2 p ≥ ζ 2 (p) • β 2 n,for some constant β > 0.Theorem IV.4 (k-median with candidate centers in n O(1) dimensional p -metric space). Let p ∈ R ≥1 ∪{∞}. Assuming the unique games conjecture, given a point-set P ⊂ R m of size n (and m = poly(n)), a collection C of m candidate centers in R m , and a parameter k as input, it is NP-hard to distinguish between the following two cases: • Completeness: There exists C := {c 1 , . . . , c k } ⊆ C and σ : P → C such that a∈P a -σ(a) p ≤ βn, • Soundness: For every C := {c 1 , . . . , c k } ⊆ C and every σ : P → C we have: a∈P a -σ(a) p ≥ ζ 1 (p) • βn,

  min c∈C τ (b i,j ) -c 2 p = β 2 and min c∈C τ (b i,j ) -c p = β, for some β > 0. The k-means cost of the overall instance is thus β 2 • |P|, while the k-median cost is β • |P|. Finally, we turn to the soundness analysis. Soundness.: Consider any set of centers C = {c 1 , . . . , c k } ⊂ C that is optimal for the k-median or kmeans objective. Let S := {v 1 , . . . , v k } be the set of vertices corresponding to the centers of C , namely

  t. k-median objective has cost at least ζ 1 (p) • β • |P|, and optimal solution w.r.t. k-means objective has cost at least ζ 2 (p) • β 2 • |P|, as claimed.

•

  Completeness: There exists C := {c 1 , . . . , c k } ⊆ {0, 1} m and σ : P → C such that a∈P a -σ(a) 2 0 ≤ n, • Soundness: For every C := {c 1 , . . . , c k } ⊆ {0, 1} m and every σ : P → C we have: a∈P a -σ(a) 2 0 ≥ 1.21 • n. Theorem V.2 (k-median without candidate centers in n O(1)

  for any u ∈ B, and thus we could replace c i by the all zeroes vector and the cost of k-means or k-median would not increase. Therefore we assume all the centers have Hamming weight at most 3. We partition C * into C 0 , C 1 , C 2 , and C 3 where c ∈ C * belongs to C j if the Hamming weight of c is j. Consider an optimal classification σ : P → C * . For every point c ∈ C * let T σ c ⊆ B be defined as follows:T σ c = {u ∈ B | σ(τ (u)) = c}.We propose the following claim. Claim V.3. Given an optimal classification σ we can construct an optimal classification σ * (which might be same as σ) such that for any c ∈ C 3 we have |T σ * c | ≤ 3 and for any c ∈ C 2 we have |T σ * c | ≤ 1. Before we prove the above claim, we see how it completes the proof. For every c ∈ C 1 if its 1 is on coordinate i we associate it with the vertex i in G. Now we partition T σ * c into Y σ * c and N σ * c where for any u ∈ B such that σ * (τ (u)) = c we have that u ∈ Y σ * c if c ∈ u (think of c as the vertex in G) and u ∈ N σ * c otherwise. By definition of the soundness case, we have that c∈C1 |Y σ * c | is at most (0.9292 -ε)|E|. Notice that there are at most 3|C 3 |+|C 2 | edges which are not assigned to a center in C 1 ∪ C 0 . We upper bound |C 3 |, |C 2 by |V | and thus we have that there are at most 4|V | edges which are not assigned to a center in C 1 ∪ C 0 . If an edge is assigned a center in C 0 then its distance from the center is 2. If an edge is assigned a center in c ∈ C 1 and it is contained in Y σ * c

  t. k-median objective has cost at least (2(0.0708) + 0.9292) • |E| = 1.0708 • |E|, and optimal solution w.r.t. k-means objective has cost at least (4(0.0708) + 0.9292) • |E| = 1.2124 • |E|, as claimed.

•

  Completeness: There exists C := {c 1 , . . . , c k } ⊆ R d and σ : P → C such that a∈P a -σ(a) 1 ≤ n, • Soundness: For every C := {c 1 , . . . , c k } ⊆ R d and every σ : P → C we have: a∈P a -σ(a) 1 ≥ 1.07 • n.

•

  Completeness: There exists C := {c 1 , . . . , c k } ⊆ R d and σ : P → C such that a∈P a -σ(a) 2 2 ≤ βn, • Soundness: For every C := {c 1 , . . . , c k } ⊆ R d and every σ : P → C we have: a∈P a -σ(a) 2 2 ≥ 1.07 • βn, for some constant β > 0.

Definition VI. 1

 1 (c-left bounded functions). Let X and Y be two finite sets and c ∈ N. Let f : X ×Y → {0, 1}. For every y ∈ Y, let S y = {a ∈ X | f (a, y) = 1}. Then f is said to be c-left bounded if for every y ∈ Y, we have |S y | = c.

  2 β . Bob accepts only if Alice's message (a field element) is in S, but since f is c-left bounded, we have |S y | = c and thus |S| ≤ c. The acceptance complexity of the protocol is clearly the expected size of S over the randomness. Consider the set C y = {C(a) | a ∈ S y }. Since any two codewords of C agree on at most 3/ √ q fraction of coordinates, we have by union bound that there are at least 1 -c 2 (3/ √ q) fraction of coordinates of [ ] on which all codewords in C y are distinct. For such coordinates we have |S| = c. Therefore the acceptance complexity is at least c(1 -c 2 (3/ √ q)) and at most c. Completeness.: Suppose that f (x, y) = 1 then x ∈ S y and Bob always accepts.

B

  . Connecting OWC protocol to Hardness of Approximating k-median and k-means Definition VI.3 (Membership function). Let X and Y be sets of size m and n respectively, where each element in X is a subset of Y. Then Mem m,n : X × Y → {0, 1} is defined by Mem m,n (x, y) = 1 if y ∈ x, 0 otherwise, .

•

  Completeness: There exists S 1 , . . . , S k ∈ S such that i∈[k]

Theorem VI. 6 .

 6 Let p ∈ R ≥1 ∪{∞}. Let Π be a (r, µ, α, s)-OWC protocol for Mem m,n . Let τ be a λ-gap realization of H * (2 µ , α) in the d-dimensional p -metric. There is a polynomial time (in input size) algorithm A which takes as input an instance (U, S, k) of the (freq, gap)-max coverage problem where |U| = n and |S| = m and outputs an instance (P, C, k) of the k-median/k-means problem where we are given a point-set P ⊂ R 2 r d of size n, a collection C of m candidate centers in R 2 r d such that the following holds: • Completeness: If there exists S 1 , . . . , S k ∈ S such that i∈[k] S i = U then there exists C := {c 1 , . . . , c k } ⊆ C and σ : P → C such that for all a ∈ P we have a -σ(a) p = 2 r/p • β, • Soundness: If for every S 1 , . . . , S k ∈ S we have i∈[k] S i ≤ gap•|U | then for every C := {c 1 , . . . , c k } ⊆ C and every σ : P → C we have that there exists P ⊆ P such that |P | ≥ gap • |P| and for all a ∈ P we have a -σ(a) p ≥ 2 r/p • λ • (α + 1 -freq -s) 1/p • β, and for all a ∈ P \ P we have a -σ(a) p = 2 r/p • β, for some β > 0.Proof: Recall from Section III that A * (t) and B * (t, r) are the partite vertex sets of H * (t, r). Here we use the short hand A * := A * (2 µ ) and B * := B * (2 µ , freq). Also let τ : A * ∪B * → R d and let β > 0 be the constant from Definition III.1. We define functions T U : U ×{0, 1} r → B * ∪{⊥} and T S : S × {0, 1} r → A * below. Then, we will construct functions TU : U → R d•2 rand T S : S → R d•2 r . Given T U and T S the point-set P is just defined to be { T U (u) | u ∈ U} and the set of candidate centers C is just { T S (S) | S ∈ S}.

Soundness. :

 : Suppose for every S 1 , . . . , S k ∈ S we have i∈[k] S i ≤ gap • |U |. Fix some subset C ⊆ C of size k. Let σ : P → C be some mapping. Consider the mapping ξ : U → S defined by σ as follows. For every u ∈ U fix some S ∈ S such that T S (S) = σ( T U (u)) (in case there are more than one S satisfying T S (S) = σ( T U (u)), pick one arbitrarily). Set ξ(u) = S. Clearly the range of ξ is of size at most k. Let S = {S 1 , . . . , S k } be the range of ξ where k ≤ k. We know that there are at least (1 -gap) • |U| elements of U that are not contained in i∈[k ] S i . Let's call this set U . Therefore for any (S, u) ∈ S × U we have Mem m,n (S, u) = 0 and Bob would accept Alice's message with probability at most s over the randomness, if both of them follow Π.

  AND k-means IN O(log n) DIMENSIONS In this section, we finally prove Theorems I.2, I.3, and I.4. A. k-means and k-median in p -metric with Candidate Centers In this subsection, we prove Theorem I.2. Theorem VII.1 (k-means with candidate centers in O(log n) dimensional p -metric space). Let p ∈ R ≥1 ∪{∞}. Assuming the unique games conjecture, given a point-set P ⊂ R d of size n (and d = O(log n)), a collection C of m candidate centers in R d (where m = poly(n)), and a parameter k as input, it is NP-hard to distinguish between the following two cases: • Completeness: There exists C := {c 1 , . . . , c k } ⊆ C and σ : P → C such that a∈P a -σ(a) 2 p ≤ βn • (log n) 2/p , • Soundness: For every C := {c 1 , . . . , c k } ⊆ C and every σ : P → C we have: a∈P a -σ(a) 2 p ≥ ζ 2 (p) • βn • (log n) 2/p , for some constant β > 0. Theorem VII.2 (k-median with candidate centers in O(log n) dimensional p -metric space). Let p ∈ R ≥1 ∪{∞}. Assuming the unique games conjecture, given a point-set P ⊂ R d of size n (and d = O(log n)), a collection C of m candidate centers in R d (where m = poly(n)), and a parameter k as input, it is NP-hard to distinguish between the following two cases: • Completeness: There exists C := {c 1 , . . . , c k } ⊆ C and σ : P → C such that a∈P a -σ(a) p ≤ βn(log n) 1/p , • Soundness: For every C := {c 1 , . . . , c k } ⊆ C and every σ : P → C we have:

  a∈P

•

  Completeness: There exists C := {c 1 , . . . , c k } ⊆ R d and σ : P → C such that a∈P a -σ(a) 2 2 ≤ βn log n, • Soundness: For every C := {c 1 , . . . , c k } ⊆ R d and every σ : P → C we have: a∈P a -σ(a) 2 2 ≥ 1.07 • βn log n,for some constant β > 0.

  Theorem VII.4 (k-means in Euclidean metric in O(log n) dimensions without Candidate Centers). Assuming the unique games conjecture, given a point-set P ⊂ {0, 1} d of size n (and d = O(log n)) and a parameter k as input, it is NP-hard to distinguish between the following two cases: • Completeness: There exists C := {c 1 , . . . , c k } ⊆ R d and σ : P → C such that a∈P a -σ(a) 2 2 ≤ βn log n, • Soundness: For every C := {c 1 , . . . , c k } ⊆ R d and every σ : P → C we have: a∈P a -σ(a) 2 2 ≥ 1.07 • βn log n,for some constant β > 0.

Theorem VII. 7

 7 (k-means with candidate centers in O(log n) dimensional ∞ -metric space). Let ε > 0. Given a point-set P ⊂ R d of size n (and d = O(log n)), a collection C of m candidate centers in R d (where m = poly(n)), and a parameter k as input, it is NP-hard to distinguish between the following two cases: • Completeness: There exists C := {c 1 , . . . , c k } ⊆ C and σ : P → C such that a∈P a -σ(a) 2 ∞ ≤ βn, • Soundness: For every C := {c 1 , . . . , c k } ⊆ C and every σ : P → C we have: a∈P a -σ(a) 2 ∞ ≥ 1 + 8 e -ε • βn, for some constant β > 0. Theorem VII.8 (k-median with candidate centers in O(log n) dimensional ∞ -metric space). Let ε > 0. Given a point-set P ⊂ R d of size n (and d = O(log n)), a collection C of m candidate centers in R d (where m = poly(n)), and a parameter k as input, it is NP-hard to distinguish between the following two cases: • Completeness: There exists C := {c 1 , . . . , c k } ⊆ C and σ : P → C such that a∈P a -σ(a) ∞ ≤ βn, • Soundness: For every C := {c 1 , . . . , c k } ⊆ C and every σ : P → C we have: a∈P a -σ(a) ∞ ≥ 1 + 2 e -ε • βn, for some constant β > 0.

  IN THISTABLE WE SUMMARIZE THE STATE-OF-THE-ART INAPPROXIMABILITY FOR k-means AND k-median CLUSTERING OBJECTIVES IN VARIOUS METRIC SPACES FOR BOTH THE DISCRETE AND CONTINUOUS VERSIONS OF THE PROBLEM. IF A CITATION IS NOT PROVIDED FOR AN ENTRY IN THE TABLE THEN IT IMPLIES THAT THE RESULT WAS OBTAINED IN THIS PAPER. ALSO, HARDNESS OF APPROXIMATION FACTORS OBTAINED UNDER THE STRONGER ASSUMPTION OF THE UNIQUE GAMES CONJECTURE ARE STAR MARKED. FINALLY, THE TWO ENTRIES WHICH ARE DAGGER MARKED, I.E., THE INAPPROXIMABILITY FOR k-means AND k-median FOR THE GENERAL METRIC IN THE CONTINUOUS CASE, IS NOT EXPLICITLY DETERMINED IN LITERATURE, BUT IT might BE POSSIBLE TO EXTEND FEIGE'S HARD INSTANCES OF THE MAX-COVERAGE PROBLEM [28], [8] TO OBTAIN 1 + 8 FOR k-means AND k-median RESPECTIVELY FOR THE GENERAL METRIC IN THE CONTINUOUS CASE AS WELL.

	Problem	Discrete	Discrete	Continuous	Continuous
	Metric	k-means	k-median	k-means	k-median
	General	1 + 8 e ≈ 3.94 [8]	1 + 2 e ≈ 1.73 [8]	Not Determined †	Not Determined †
	0	1.56 *	1.14 *	1.21 *	1.07 *
	1	1.56 *	1.14 *	Not Determined	1.07 *
	2	1.17 *	1.06 *	1.07 *	Not Determined
	∞	1 + 8 e ≈ 3.94	1 + 2 e ≈ 1.73	Not Determined	Not Determined
			Table I
	1 + 2 e				e AND

Note that ∞-metric of large dimensions are not of high interest since hardness of approximation for general metric space directly implies hardness of approximation for the same factor in ∞-metric of high dimension by applying the Fréchet embedding.

-metric, it follows easily, it is as simple as computing the location of the mean of a set of points in the

-metric. We thus show the following:

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

More generally this upper bound holds for any metric (and not necessarily just the p-metrics).

The result is implicit in[START_REF] Austrin | Inapproximability of vertex cover and independent set in bounded degree graphs[END_REF], and is explicitly written in[START_REF] Manurangsi | A note on max k-vertex cover: Faster fpt-as, smaller approximate kernel and improved approximation[END_REF].

We require the hard instances of gap vertex coverage problem to have this additional minimum degree requirement only for proving our inapproximability results of clustering objectives in the continuous case (i.e., Theorems I.3 andI.4), and do not need it to prove our hardness of approximation results in the discrete case (i.e., Theorem I.2).

The Fréchet embedding maps n points in any metric into the ∞- metric with polynomial in n blowup in the dimension such that all pairwise distances are preserved.

ACKNOWLEDGMENT

We are truly grateful to Per Austrin, Amey Bhangale, Euiwoong Lee, and Pasin Manurangsi for discussions about the inapproximability of the vertex coverage and max coverage problem.

Ce projet a bénéficié d'une aide de l' État gérée par l'Agence Nationale de la Recherche au titre du Programme Appel à projets générique JCJC 2018 portant la référence suivante : ANR-18-CE40-0004-01.

Karthik C. S. was supported by ERC-CoG grant 772839, the Israel Science Foundation (grant number 552/16), and from the Len Blavatnik and the Blavatnik Family foundation. Most of this work was done while Karthik C. S. was a Ph. D. student at the Weizmann Institute of Science.

APPENDIX

In this section, we show how our inapproximability results for k-median and k-means can be extended to the edit metric. First, we recall the following technical tool established in [START_REF] Rubinstein | Hardness of approximate nearest neighbor search[END_REF].

Lemma A.1 (Rubinstein [START_REF] Rubinstein | Hardness of approximate nearest neighbor search[END_REF]). For large enough d ∈ N, there is a function η : {0, 1} d → {0, 1} d , where d = O(d log d), such that for all a, b ∈ {0, 1} d the following holds for some constant λ > 0:

Moreover, for any a ∈ {0, 1} d , η(a) can be computed in 2 o(d) time.

We state our hardness of approximation result for the edit metric below.

Theorem A.2 (k-means with candidate centers in O(log n • log log n) dimensional Edit-metric space). Assuming the unique games conjecture, given a point-set P ⊂ {0, 1} d of size n (and d = O(log n log log n)), a collection C of m candidate centers in {0, 1} d (where m = poly(n)), and a parameter k as input, it is NP-hard to distinguish between the following two cases:

• Completeness: There exists C := {c 1 , . . . , c k } ⊆ C and σ :

• Soundness: For every C := {c 1 , . . . , c k } ⊆ C and every σ : P → C we have:

for some fixed β :

• Soundness: For every C := {c 1 , . . . , c k } ⊆ C and every σ : P → C we have that there exists P σ ⊆ P such that |P σ | ≥ (0.0708 + ε) • |P|, for some small ε > 0, we have

for some constant β > 0 and any δ > 0.

We consider the above given point-set P ⊂ {0, 1} d and the collection C of candidate centers in {0, 1} d , and construct the input point-set P * ⊂ {0, 1} d and the collection C * of candidate centers in {0, 1} d for the edit-metric, where d = O(d log d). We define P * and C * as follows:

where η was as given in Lemma A.1.

Let us suppose that (5) holds. Consider C ⊆ C * defined as

Then, we have that for all a * ∈ P * ,

Now, let us suppose that ( 6) and ( 7