
Let A⊆R.
sup Adenotes the supremum of A, i.e. the least upper bound of A.
inf Adenotes the infimum of A, i.e. the greatest lower bound of A.
1A: Ω → {0,1},denotes the indicator function of A, so that
1A(ω) = (1 , if ω∈A
0 , otherwise.
Let g, h:R→R. Let t∈R.
(g∗h)(t) = Z∞
−∞
g(x)h(t−x)dx denotes the convolution of gand hat t∈R
We let Indenote the n×nidentity matrix.
References
[Aar11] Scott Aaronson, A linear-optical proof that the permanent is #p-hard, Electronic Colloquium
on Computational Complexity (ECCC) 18 (2011), 43.
[ACKS15] Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy, and Ali Kemal Sinop, The hard-
ness of approximation of euclidean k-means, Preprint, arXiv:1502.03316, 2015.
[ANFSW0] Sara. Ahmadian, Ashkan. Norouzi-Fard, Ola. Svensson, and Justin. Ward, Better guarantees for
$
k
$
-means and euclidean
$
k
$
-median by primal-dual algorithms, SIAM Journal on Computing
0(0), no. 0, FOCS17–97–FOCS17–156.
[BK15] Amey Bhangale and Swastik Kopparty, The complexity of computing the minimum rank of a
sign pattern matrix, CoRR abs/1503.04486 (2015).
[CAEMN22] Vincent Cohen-Addad, Hossein Esfandiari, Vahab Mirrokni, and Shyam Narayanan, Improved
approximations for euclidean k-means and k-median, via nested quasi-independent sets, Pro-
ceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (New York,
NY, USA), STOC 2022, Association for Computing Machinery, 2022, p. 1621–1628.
[CAS19] Vincent Cohen-Addad and Karthik Srikanta, Inapproximability of Clustering in Lp-metrics,
FOCS’19 - 60th Annual IEEE Symposium on Foundations of Computer Science (Baltimore,
United States), November 2019.
[CEM+15] Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu,
Dimensionality reduction for k-means clustering and low rank approximation, Proceedings of
the Forty-seventh Annual ACM Symposium on Theory of Computing (New York, NY, USA),
STOC ’15, ACM, 2015, pp. 163–172.
[Che09] Ke Chen, On coresets for k-median and k-means clustering in metric and euclidean spaces and
their applications, SIAM Journal on Computing 39 (2009), no. 3, 923–947.
[FMS07] Dan Feldman, Morteza Monemizadeh, and Christian Sohler, A ptas for k-means clustering
based on weak coresets, Proceedings of the Twenty-third Annual Symposium on Computational
Geometry (New York, NY, USA), SCG ’07, ACM, 2007, pp. 11–18.
[Gal14] Fran¸cois Le Gall, Powers of tensors and fast matrix multiplication, Preprint, arXiv:1401.7714.
ISAAC 2014., 2014.
[GOR+21] Fabrizio Grandoni, Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman, and Rakesh Venkat,
A refined approximation for Euclidean k-means, preprint, arXiv:2107.07358, 2021.
[GVL13] G.H. Golub and C.F. Van Loan, Matrix computations, Johns Hopkins Studies in the Mathe-
matical Sciences, Johns Hopkins University Press, 2013.
157