#  Quantization of Second Order Fermions

Rodolfo Ferro-Hernández<EMAIL_ADDRESS>PRISMA+ Cluster of Excellence
and Institute for Nuclear Physics Johannes Gutenberg University, 55099 Mainz,
Germany.  Julio Olmos<EMAIL_ADDRESS>Departamento de Física, DCI,
Campus León, Universidad de Guanajuato, Loma del Bosque 103, Lomas del
Campestre C.P. 37150, León, Guanajuato, México  Eduardo Peinado
<EMAIL_ADDRESS>Instituto de Física, Universidad Nacional Autónoma de
México, A.P. 20-364, Ciudad de México 01000, México  Carlos A. Vaquera-Araujo
<EMAIL_ADDRESS>Consejo Nacional de Humanidades, Ciencias y
Tecnologías, Av. Insurgentes Sur 1582. Colonia Crédito Constructor, Del.
Benito Juárez, C.P. 03940, Ciudad de México, México  Departamento de Física,
DCI, Campus León, Universidad de Guanajuato, Loma del Bosque 103, Lomas del
Campestre C.P. 37150, León, Guanajuato, México  Dual CP Institute of High
Energy Physics, C.P. 28045, Colima, México

###### Abstract

The quantization of a massive spin $1/2$ field that satisfies the Klein-Gordon
equation is studied. The framework is consistent, provided it is formulated as
a pseudo-hermitian quantum field theory by the redefinition of the field dual
and the identification of an operator that modifies the internal product of
states in Hilbert space to preserve a real energy spectrum and unitary
evolution. Since the fermion field has mass dimension one, the theory admits
renormalizable fermion self-interactions.

In this letter, we introduce a consistent pseudo-hermitian quantum field
theory for second-order massive fermions $\psi$ transforming under the
$(\tfrac{1}{2},0)\oplus(0,\tfrac{1}{2})$ representation of the Restricted
Lorentz Group (RLG). A pseudo-hermitian Lagrangian satisfies [1]

$\mathcal{L}^{\\#}\equiv\eta\mathcal{L}^{\dagger}\eta=\mathcal{L}.$ (1)

This generalization of hermiticity was proposed in [2, 3] extending the
results of $PT$-symmetric quantum mechanics introduced in [4], and has two
important features: 1) the energy spectrum of the theory is real and 2) time
evolution is unitary upon the definition of a suitable internal product of
states with the aid of the $\eta$ operator.

The Lagrangian for the $\psi$ field is given by

$\mathcal{L}=\partial^{\mu}\widehat{\psi}\partial_{\mu}\psi-m^{2}\widehat{\psi}\psi,$
(2)

where $\widehat{\psi}$ is not the Dirac adjoint of $\psi$, but instead a
redefinition of its dual that renders the theory pseudo-hermitian. This
redefinition also eliminates the presence of negative norm states in the
spectrum [5], which appear when the standard Dirac adjoint is used in this
Lagrangian.

The first observation we can make about this theory is that the conjugate-
momenta are $\pi_{\psi}=\dot{\widehat{\psi}}$,
$\pi_{\widehat{\psi}}=\dot{\psi}$, where the dot denotes the derivative with
respect to time. Without imposing further constraints, this formalism involves
a spinor with 4 complex (8 real) components, and the phase space is
parameterized by both $\psi$ and $\dot{\widehat{\psi}}$, yielding 16 real
components. Thus, the second-order formalism describes a field with 8 degrees
of freedom. In contrast, the momentum conjugate associated to a four component
Dirac spinor $\chi$ is $i\chi^{\dagger}$, and therefore, the whole phase space
is parameterized by the 8 real components of $\chi$, giving a total number of
4 real degrees of freedom for the Dirac field. A second observation about the
second-order formalism is that the field $\psi$ has a mass dimension of one,
in sharp contrast with Dirac spinors, which have mass dimension $3/2$.

It can be shown that the most general solution to the Klein-Gordon equation
for spin $1/2$ fields can be written in terms of two solutions to the Dirac
equation $\chi_{1}$ and $\chi_{2}$ of the form [6]

$\psi=\frac{1}{\sqrt{2m}}(\chi_{1}+\gamma^{5}\chi_{2}).$ (3)

The plane wave expansions of $\psi$ and $\widehat{\psi}$ are

$\displaystyle\psi(x)=$
$\displaystyle\int\frac{d^{3}\mathbf{p}}{(2\pi)^{3}2\sqrt{m\omega_{\mathbf{p}}}}\sum_{s}\bigg{\\{}\left[u^{s}_{\mathbf{p}}a^{1s}_{\mathbf{p}}+\gamma^{5}u^{s}_{\mathbf{p}}a^{2s}_{\mathbf{p}}\right]e^{-ip\cdot
x}+\left[v^{s}_{\mathbf{p}}b^{1s\dagger}_{\mathbf{p}}+\gamma^{5}v^{s}_{\mathbf{p}}b^{2s\dagger}_{\mathbf{p}}\right]e^{ip\cdot
x}\bigg{\\}},$ $\displaystyle\widehat{\psi}(x)=$
$\displaystyle\int\frac{d^{3}\mathbf{p}}{(2\pi)^{3}2\sqrt{m\omega_{\mathbf{p}}}}\sum_{s}\bigg{\\{}\left[\bar{u}^{s}_{\mathbf{p}}a^{1s\dagger}_{\mathbf{p}}+\bar{u}^{s}_{\mathbf{p}}\gamma^{5}a^{2s\dagger}_{\mathbf{p}}\right]e^{ip\cdot
x}+\left[\bar{v}^{s}_{\mathbf{p}}b^{1s}_{\mathbf{p}}+\bar{v}^{s}_{\mathbf{p}}\gamma^{5}b^{2s}_{\mathbf{p}}\right]e^{-ip\cdot
x}\bigg{\\}},$ (4)

with $\omega_{\mathbf{p}}=+\sqrt{|\mathbf{p}|^{2}+m^{2}}$,
$p^{\mu}=(\omega_{\mathbf{p}},\mathbf{p})$, $u^{s}_{\mathbf{p}}$,
$v^{s}_{\mathbf{p}}$ as the positive and negative energy solutions of the
Dirac free equation, and $s=\pm\frac{1}{2}$. The theory is by construction
explicitly Lorentz invariant.

The pseudo-hermitian nature of the formalism emerges from the introduction of
a unitary and hermitian operator $\eta$ defined by the following relations
[1]:

$\begin{array}[]{cccc}\eta
a^{js}_{\mathbf{p}}\eta=(-1)^{j-1}a^{js}_{\mathbf{p}},\qquad\eta
b^{js\dagger}_{\mathbf{p}}\eta=(-1)^{j-1}b^{js\dagger}_{\mathbf{p}},\end{array}$
(5)

where $j=1,2$. Notice that the difference between the new dual
$\widehat{\psi}$ and the Dirac adjoint $\overline{\psi}$ is the sign of the
modes involving $\gamma^{5}$ in Eq. (4). The dual field in terms of $\eta$, is
given by $\widehat{\psi}=\eta\bar{\psi}\eta$. This implies
$\eta(\widehat{\psi}\psi)^{\dagger}\eta=\widehat{\psi}\psi$. fulfilling the
pseudo-hermiticity of the free Lagrangian in Eq. (2), as prescribed in Eq.
(1). Assuming the following anti-commutation relations for the momentum-space
field operators:

$\begin{split}\left\\{a^{js}_{\mathbf{p}},a^{kr\dagger}_{\mathbf{p}^{\prime}}\right\\}&=(2\pi)^{3}\delta^{jk}\delta^{rs}\delta^{(3)}(\mathbf{p}-\mathbf{p}^{\prime}),\\\
\left\\{b^{js}_{\mathbf{p}},b^{kr\dagger}_{\mathbf{p}^{\prime}}\right\\}&=(2\pi)^{3}\delta^{jk}\delta^{rs}\delta^{(3)}(\mathbf{p}-\mathbf{p}^{\prime}),\end{split}$
(6)

with all other anti-commutators vanishing, an explicit solution for the
operator $\eta$ is given by

$\eta=\exp\left[i\pi\int\frac{d^{3}\mathbf{p}}{(2\pi)^{3}}\sum_{s}\left(a^{2s\dagger}_{\mathbf{p}}a^{2s}_{\mathbf{p}}+b^{2s\dagger}_{\mathbf{p}}b^{2s}_{\mathbf{p}}\right)\right].$
(7)

This operator satisfies $\eta=\eta^{\dagger}$ and $\eta\eta^{\dagger}=1$,
meaning that $\eta^{2}=1$, and thus their eigenvalues are $\pm 1$.

The dynamics of the pseudo-hermitian quantum theory with $H^{\\#}=\eta
H^{\dagger}\eta=H$ are guaranteed to be unitary if the inner product between
two states is defined as $\braket{a}{b}_{\eta}\equiv\bra{a}\eta\ket{b}$. In
this way, probability amplitudes are preserved under time evolution an the
energy spectrum is real. The conjugate momenta satisfy the time canonical
anti-commutation relations

$\begin{split}\left\\{\psi_{\alpha}(\mathbf{x},t),\pi_{\psi}{}_{\beta}(\mathbf{x}^{\prime},t)\right\\}&=-\left\\{\widehat{\psi}_{\alpha}(\mathbf{x},t),\pi_{\widehat{\psi}}{}_{\beta}(\mathbf{x}^{\prime},t)\right\\}\\\
&=i\delta_{\alpha\beta}\delta^{(3)}(\mathbf{x}-\mathbf{x}^{\prime}).\end{split}$
(8)

Due to the redefinition of the dual implemented by the $\eta$ operator, these
anti-commutation relations lead to the standard non-vanishing canonical
relations for the momentum space operators in Eq. (6). Additionally, it can be
shown that the fields display the correct properties under microcausality. In
particular, we have

$\left\\{\psi_{\alpha}(x),\psi_{\beta}(y)\right\\}=\left\\{\widehat{\psi}_{\alpha}(x),\widehat{\psi}_{\beta}(y)\right\\}=0,$
(9)

and

$\begin{split}&\left\\{\psi_{\alpha}(x),\widehat{\psi}_{\beta}(y)\right\\}\equiv\Delta(x-y)\delta_{\alpha\beta}\\\
&\qquad=\int\frac{d^{3}\mathbf{p}}{(2\pi)^{3}2\omega_{\mathbf{p}}}\bigg{\\{}e^{-ip\cdot(x-y)}-e^{ip\cdot(x-y)}\bigg{\\}}\delta_{\alpha\beta},\end{split}$
(10)

where $\Delta(x-y)$ is the well known Lorentz invariant and causal Schwinger’s
Green function. The Hamiltonian and the momentum operator are given by

$\begin{split}H&=:\int
d^{3}\mathbf{x}\bigg{\\{}\dot{\widehat{\psi}}\dot{\psi}+\nabla\widehat{\psi}\cdot\nabla\psi+m^{2}\widehat{\psi}\psi\bigg{\\}}:,\\\
\mathbf{P}&=:-\int
d^{3}\mathbf{x}\bigg{\\{}\dot{\widehat{\psi}}\nabla\psi+\nabla\widehat{\psi}\dot{\psi}\bigg{\\}}:,\end{split}$
(11)

where $:{}:$ stands for normal ordering. In terms of the momentum space
operators, the generators of space-time translations $P^{\mu}=(H,\mathbf{P})$
read

$P^{\mu}=\int\frac{d^{3}\mathbf{p}}{(2\pi)^{3}}p^{\mu}\sum_{j,s}\bigg{\\{}a^{js\dagger}_{\mathbf{p}}a^{js}_{\mathbf{p}}+b^{js\dagger}_{\mathbf{p}}b^{js}_{\mathbf{p}}\bigg{\\}}.$
(12)

Furthermore, defining the vacuum $\ket{0}$ as the state annihilated by
$a^{js}_{\mathbf{p}}$ and $b^{js}_{\mathbf{p}}$, we can conclude that all
states have positive energy.

The spin of the field is

$\begin{split}\mathbf{S}=:-i\int
d^{3}\mathbf{x}\left\\{\dot{\widehat{\psi}}\mathbf{J}\psi-\widehat{\psi}\mathbf{J}\dot{\psi}\right\\}:,\end{split}$
(13)

where the components of $\mathbf{J}$ are given by
$J^{k}=\frac{1}{2}\epsilon_{ijk}M^{ij}$, where
$M^{\mu\nu}=\frac{i}{4}\left[\gamma^{\mu},\gamma^{\nu}\right]$ are the Lorentz
Generators of the $(\tfrac{1}{2},0)\oplus(\tfrac{1}{2},0)$ representation. To
show that the field contains particles of spin $1/2$, one can evaluate the
action of the operator $S^{3}$ on one-particle states with zero momentum in
the chiral representation of the Dirac matrices. The resulting relations are

$S^{3}a^{js\dagger}_{\mathbf{0}}\ket{0}=sa^{js\dagger}_{\mathbf{0}}\ket{0},\quad
S^{3}b^{js\dagger}_{\mathbf{0}}\ket{0}=sb^{js\dagger}_{\mathbf{0}}\ket{0}.$
(14)

The free theory of second order fermions in Eq. (2) is invariant under the
phase transformation

$\psi\rightarrow\psi^{\prime}=e^{i\theta}\psi,\qquad\widehat{\psi}\rightarrow\widehat{\psi}^{\prime}=\widehat{\psi}e^{-i\theta},$
(15)

where $\theta$ is a constant real parameter. The conserved charge associated
to this $\mathrm{U}(1)$ global symmetry is

$\begin{split}Q=&:i\int
d^{3}\mathbf{x}\bigg{\\{}\widehat{\psi}\dot{\psi}-\dot{\widehat{\psi}}\psi\bigg{\\}}:\\\
=&\int\frac{d^{3}\mathbf{p}}{(2\pi)^{3}}\sum_{j,s}\bigg{\\{}a^{jr\dagger}_{\mathbf{p}}a^{js}_{\mathbf{p}}-b^{jr\dagger}_{\mathbf{p}}b^{js}_{\mathbf{p}}\bigg{\\}}.\end{split}$
(16)

From the commutation relation of this operator with the creation and
annihilation operators, one can conclude that $a^{js\dagger}_{\mathbf{p}}$ and
$b^{js}_{\mathbf{p}}$ have charge $+1$, whereas $a^{js}_{\mathbf{p}}$ and
$b^{js\dagger}_{\mathbf{p}}$ have charge $-1$. Labeling the one-particle
states with this eigenvalue, one can show that they are eight-fold degenerate

$\begin{split}Ha^{js\dagger}_{\mathbf{p}}\ket{0}&\propto
H\ket{\mathbf{p},+,j,s}=\omega_{\mathbf{p}}\ket{\mathbf{p},+,j,s},\\\
Hb^{js\dagger}_{\mathbf{p}}\ket{0}&\propto
H\ket{\mathbf{p},-,j,s}=\omega_{\mathbf{p}}\ket{\mathbf{p},-,j,s}.\end{split}$
(17)

The free theory displays a larger symmetry. Since the field $\psi$ and its
dual anticommute $\\{\psi_{\alpha}(x),\widehat{\psi}_{\beta}(x)\\}=0$, we can
write Eq. (2) as

$\mathcal{L}=\frac{1}{2}\partial^{\mu}\Psi^{T}\Omega\partial_{\mu}\Psi-\frac{m^{2}}{2}\Psi^{T}\Omega\Psi,$
(18)

where $\Psi$ is a column matrix defined as

$\Psi(x)=\begin{pmatrix}\widehat{\psi}^{T}(x)\\\ \psi(x)\end{pmatrix},$ (19)

and $\Omega$ is the $8\times 8$ symplectic matrix, written in $4\times 4$
blocks as

$\Omega=\begin{pmatrix}0_{4\times 4}&1_{4\times 4}\\\ -1_{4\times
4}&0_{4\times 4}\end{pmatrix}.$ (20)

Thus, Eq. (18) is symmetric under the global transformations
$\Psi\rightarrow\Psi^{\prime}=S\Psi$ with $S^{T}\Omega S=\Omega.$ This is the
defining relation for an element of the symplectic group
$\mathrm{Sp}(8,\mathbb{C})$, whose algebra has 36 generators.

The second order theory is invariant under Parity ($\mathrm{P}$), Charge
conjugation ($\mathrm{C}$) and Time reversal ($\mathrm{T}$), and therefore
under $\mathrm{CPT}$. We define the discrete transformations of the $\psi$
field through their action on the creation operators, as follows:

$\displaystyle\mathrm{P}a^{js\dagger}_{\mathbf{p}}\mathrm{P}^{-1}=-i(-1)^{j-1}a^{js\dagger}_{-\mathbf{p}},\quad\mathrm{P}b^{js\dagger}_{\mathbf{p}}\mathrm{P}^{-1}=-i(-1)^{j-1}b^{js\dagger}_{-\mathbf{p}},$
$\displaystyle\mathrm{C}a^{js\dagger}_{\mathbf{p}}\mathrm{C}^{-1}=b^{js\dagger}_{\mathbf{p}},\quad\quad\quad\mathrm{C}b^{js\dagger}_{\mathbf{p}}\mathrm{C}^{-1}=a^{js\dagger}_{\mathbf{p}},$
(21)
$\displaystyle\mathrm{T}a^{js\dagger}_{\mathbf{p}}\mathrm{T}^{-1}=2sa^{j(-s)\dagger}_{-\mathbf{p}},\quad\quad\quad\mathrm{T}b^{is\dagger}_{\mathbf{p}}\mathrm{T}^{-1}=2sb^{i(-s)\dagger}_{-\mathbf{p}}.$

With this choice, the discrete transformations have the familiar
representations

$\displaystyle\mathrm{P}\psi(x)\mathrm{P}^{-1}=i\gamma^{0}\psi(\mathcal{P}x),\quad\mathrm{P}\widehat{\psi}(x)\mathrm{P}^{-1}=-i\widehat{\psi}(\mathcal{P}x)\gamma^{0},$
$\displaystyle\mathrm{C}\psi(x)\mathrm{C}^{-1}=\mathcal{C}\widehat{\psi}^{\,T},\qquad\mathrm{C}\widehat{\psi}\mathrm{C}^{-1}=\psi^{T}\mathcal{C}$
(22)
$\displaystyle\mathrm{T}\psi(x)\mathrm{T}^{-1}=\mathcal{C}\gamma^{5}\psi(\mathcal{T}x),\qquad\mathrm{T}\widehat{\psi}\mathrm{T}^{-1}=-\widehat{\psi}(\mathcal{T}x)\gamma^{5}\mathcal{C},$

where we have defined $\mathcal{P}=\mathrm{diag}(1,-1,-1,-1)$,
$\mathcal{T}=\mathrm{diag}(-1,1,1,1)$, and
$\mathcal{C}=-i\gamma^{2}\gamma^{0}$ in the chiral representation. The
simplest $\mathrm{C}$, $\mathrm{P}$ and $\mathrm{T}$ invariant pseudo-
hermitian interactions that can be introduced in this framework are 4-fermion
self-interactions represented by a dimension-four renormalizable operator

$\begin{split}\mathcal{L}_{\text{int}}=&\frac{\lambda_{1}}{2}\left(\widehat{\psi}\psi\right)^{2}+\frac{\lambda_{2}}{2}\left(\widehat{\psi}\gamma^{5}\psi\right)\left(\widehat{\psi}\gamma^{5}\psi\right)\\\
&+\frac{\lambda_{3}}{2}\left(\widehat{\psi}M^{\mu\nu}\psi\right)\left(\widehat{\psi}M_{\mu\nu}\psi\right).\end{split}$
(23)

Other self-interactions are not independent since they arise in terms of these
three through a Fierz transformation. In particular, taking
$\lambda_{2}=\lambda_{3}=0$, we get the simplest model of self-interacting
fermions that at one-loop has vanishing beta function $\beta_{\lambda_{1}}=0$.
The authors of [7] obtained this result in the context of the naïve hermitian
second-order theory. All the results contained in [7] and its non-abelian
generalization [8] can be readily applied to the non-hermitian version of the
theory presented here.

Recently, it has been shown in [9] that under the helicity-amplitude formalism
the mass dimension for an operator with four mass-less external legs must be
six, which may seem to contradict the results in this paper. Nevertheless, as
can be seen from the mode expansion, our theory is only valid for $m\neq 0$,
so it is not possible to have mass-less fermions with a second-order
Lagrangian, leaving room for consistency with the helicity-amplitude
formalism.

Summarizing, in this work, we have studied the quantization of the massive
field transforming in the $(\tfrac{1}{2},0)\oplus(0,\tfrac{1}{2})$
representation of the RLG that satisfies the Klein-Gordon equation. We have
shown that the canonical quantization is free from negative norm states by the
redefinition of the field dual and the introduction of a unitary and hermitian
operator $\eta$ that renders the free Lagrangian pseudo-hermitian according to
Eq.(1). The resulting canonical quantization of the theory is consistent with
microcausality, and the Hamiltonian is bounded from below with real
eigenvalues, as expected for a pseudo-hermitian approach. For consistency, we
have verified that the fields have spin $1/2$, and we have identified the
global and discrete symmetries of the theory. Finally, we have sketched the
possible interactions for a theory of second-order fermions, including a novel
class of renormalizable fermion self-interactions.

To conclude, we remark that this new field would couple with the Higgs field
$H$ through a quartic dimensionless coupling

$\mathcal{L}_{\psi
H}=\frac{\lambda_{H}}{2}\left(\widehat{\psi}\psi\right)H^{\dagger}H.$ (24)

Furthermore, since $\psi$ has nothing to decay in, it is stable and could play
the role of dark matter. From Eq. (24), the DM, in this case, has a Higgs
portal, and the dark matter phenomenology is determined by the mass of the
Fermion and its coupling with the Higgs in a similar way as for the scalar
dark matter [10, 11]. The same interaction contributes to the running of the
Higgs mass in the same way an extra scalar does, and since the sign of
$\lambda_{H}$ is undetermined, we can choose it in such a way as to cancel the
top quark contribution. This phenomenology and further consequences will be
the subject of another letter.

We thank M. Napsuciale, J. Erler, M. Gorshteyn, and H. Spiesberger for their
valuable comments and fruitful discussions. This work was supported by the
grants CONACYT CB-2017-2018/A1-S-13051, DGAPA-PAPIIT IN107621, and PIIF UNAM.
J.O. acknowledges CONAHCYT national grants, CAV-A is supported by the CONAHCYT
Investigadoras e Investigadores por México project 749 and SNI 58928. E.P. is
grateful for funding from ‘Cátedras Marcos Moshinsky’ (Fundación Marcos
Moshinsky). R. F. and CAV-A thank Instituto de Física de la UNAM for their
generous hospitality and support during our stay where this work took place.

## References

  * [1] A. LeClair and M. Neubert, JHEP 10, 027 (2007) doi:10.1088/1126-6708/2007/10/027 [arXiv:0705.4657 [hep-th]].
  * [2] A. Mostafazadeh, J. Math. Phys. 43, 205-214 (2002) doi:10.1063/1.1418246 [arXiv:math-ph/0107001 [math-ph]].
  * [3] A. Mostafazadeh, Int. J. Geom. Meth. Mod. Phys. 7, 1191-1306 (2010) doi:10.1142/S0219887810004816 [arXiv:0810.5643 [quant-ph]].
  * [4] C. M. Bender and S. Boettcher, Phys. Rev. Lett. 80, 5243-5246 (1998) doi:10.1103/PhysRevLett.80.5243 [arXiv:physics/9712001 [physics]].
  * [5] T. W. B. Kibble and J. C. Polkinghorne, Higher order spinor Lagrangians, Nuovo Cimento 8 (1958) 74. https://doi.org/10.1007/BF02828852
  * [6] N. Cufaro Petroni, P. Gueret, J. P. Vigier and A. Kyprianidis, Phys. Rev. D 31, 3157-3161 (1985) doi:10.1103/PhysRevD.31.3157
  * [7] C. A. Vaquera-Araujo, M. Napsuciale and R. Angeles-Martinez, JHEP 01, 011 (2013) doi:10.1007/JHEP01(2013)011 [arXiv:1205.1557 [hep-ph]].
  * [8] C. A. Vaquera-Araujo, JHEP 07, 049 (2013) doi:10.1007/JHEP07(2013)049 [arXiv:1303.5119 [hep-ph]].
  * [9] G. Durieux and C. S. Machado, Phys. Rev. D 101 (2020) no.9, 095021 doi:10.1103/PhysRevD.101.095021 [arXiv:1912.08827 [hep-ph]].
  * [10] L. Feng, S. Profumo and L. Ubaldi, JHEP 03, 045 (2015) doi:10.1007/JHEP03(2015)045 [arXiv:1412.1105 [hep-ph]].
  * [11] G. Arcadi, M. Dutra, P. Ghosh, M. Lindner, Y. Mambrini, M. Pierre, S. Profumo and F. S. Queiroz, Eur. Phys. J. C 78, no.3, 203 (2018) doi:10.1140/epjc/s10052-018-5662-y [arXiv:1703.07364 [hep-ph]].


Over the last few years Explainable Clustering has gathered a lot of attention. Dasgupta et al. [ICML'20] initiated the study of explainable $k$-means and $k$-median clustering problems where the explanation is captured by a threshold decision tree which partitions the space at each node using axis parallel hyperplanes.
Recently, Laber et al. [Pattern Recognition'23] made a case to consider the depth of the decision tree as an additional complexity measure of interest.

In this work, we prove that even when the input points are in the Euclidean plane, then any depth reduction in the explanation incurs unbounded loss in the $k$-means and $k$-median cost.
Formally, we show that there exists a data set $X\subseteq \mathbb{R}^2$, for which there is a decision tree of depth $k-1$ whose $k$-means/$k$-median cost matches the optimal clustering cost of $X$, but every decision tree of depth less than $k-1$ has unbounded cost w.r.t. the optimal cost of clustering. We extend our results to the $k$-center objective as well, albeit with  weaker guarantees.

§ INTRODUCTION

Clustering is a fundamental task that needs to be carried out for numerous applications in the areas of data analysis and unsupervised learning. The input to clustering in these applications is typically
a set of points in Euclidean space and the goal is to find a solution that minimizes a specified clustering objective. Arguably, the three most popular clustering objectives are  $k$-means, $k$-median, and $k$-center, and there is a long line
of theoretical research on designing algorithms for optimizing these objectives [35].

Explainable AI  has gained significant popularity in recent years [27, 31] as it provides reliable and helpful insights about the model and its predictions, and more importantly allows human users to comprehend and trust the results and output created by machine learning algorithms.  Dasgupta et al. [11]  introduced a notion of Explainable Clustering for the $k$-means and $k$-median objectives, which produces a threshold decision tree with $k$ leaves as the clustering result. That is, all cuts are axis-parallel at some thresholds (e.g. $x_r = \theta$, where $r$ is a certain coordinate and $\theta$ is a threshold value). The performance of explainable clustering is then evaluated by the price of explainability, defined to be the ratio of the clustering objective cost   given by the decision tree to the optimal cost of the clustering. The initial attempt by [11] gave an upper bound of $O(k^2)$ (resp. $O(k)$) and a lower bound of $\Omega(k)$
(resp. $\Omega(\log k)$) on the price of explainability of $k$-means clustering (resp. $k$-median clustering).

Laber and Murtinho [25] expanded the study of explainable clustering to the $k$-center objective, giving an upper bound of $O(\sqrt{d} k^{1-1/d})$ and a lower bound of $\Omega\left(\sqrt{d}\cdot \frac{k\sqrt{\ln \ln k}}{\ln^{1.5}k}\right)$ on the price of explainability for $k$-center clustering.
Over the last two years, a sequence of works has almost closed the above gap on price of explainability for all three clustering objectives [17, 28, 12, 6, 30, 19]. Additionally, other aspects and variants of explainable clustering have been explored in recent literature, some examples being, bicriteria approximability of the price of explainability [14, 29], computational complexity of finding good explanations [23], providing explanations via oblique decision trees [16], constructing a polyhedron around each cluster as an explanation [24],  removing outliers from clusters
for better explainability [2], and so on.

Piltaver et al. [32]  studied how tree structure parameters (such as the number of leaves, branching factor, tree depth) affect tree interpretability, and the authors  concluded that based on empirical data (from a survey with 98 questions answered by 69 respondents),
that the most important parameter is question depth (i.e., the length of the path that must be traversed from the root to a leaf to answer a question in a classification tree).
Building on this study, Laber, Murtinho, and Oliveira [26]  argued that in practice, an explanation via decision trees is useful only if the decision tree is of low depth (a.k.a. shallow decision trees).
Indeed, intuitively explaining leaves that are
far from the root involve many tests, which makes it harder to
grasp the model’s logic. In other words, short explanations are easy to understand and thus trust!

The authors of [26]  proposed an empirically-effective algorithm that leverages the price of the tree depth in the objective to return a desired cut. However, there has been no theoretical study in this direction. We thus raise the following question:

Can we always obtain short explanations without  compromising too much on the classification quality?

In order to answer the above question, we first introduce a notion called price of depth reduction. Given an input point-set $X$, the price of depth reduction to $h$, denoted $\Depth(X,h)$, is  the ratio of the clustering objective cost of the clustering given by the best decision tree of depth $h$  to the cost of the clustering given by the optimal decision tree.
Note that the depth of any decision tree with $k$ leaves is at least $\log_2 k$ and at most $k-1$. Therefore, we always have $\Depth(X,k-1)=1$.

One may wonder, if every point-set can be explained by  decision trees of low depth (say $O(\log k)$) while only paying a small price of depth reduction. Our first result is an answer in the negative; we show that in high dimensions, there exists a point-set which admits a decision tree of depth $k-1$ whose $k$-means/$k$-median/$k$-center cost is equal to the cost of an optimal cluster, but  the cost of every decision tree of depth $k-2$ for the point-set arbitrarily high relative to the optimum. Our result indicates that for certain datasets, it is impossible to reduce the decision tree depth regardless of the price of depth reduction that one is willing to pay. This also demystifies why we do not have an algorithm for depth reduction in explainable clustering with theoretically provable worst-case guarantees.

The following holds for $k$-means, $k$-median, and $k$-center clustering objectives.
For every $k,d\in \mathbb{N}$, such that $d\ge k/2$, there is a point-set $X\in\mathbb{R}^d$, such that $\Depth(X,k-2)$ is unbounded. Moreover, the price of explainability of $X$ is 1.

The above unbounded inapproximability result stands in stark contrast to clustering literature (for $k$-means, $k$-median, and $k$-center) for which we have constant factor polynomial time approximation algorithms [18, 20, 1, 4]. One may attribute the above bad dataset to the Curse of Dimensionality [21, 36, 34].

That said, while we know  high dimensional clustering is hard to approximate for the classical clustering problems [13, 7, 8, 9], the $k$-means and $k$-median objectives inapproximability is alleviated in fixed dimensions as they admit a PTAS [3, 15, 22, 10, 5]. Even in the explainable clustering literature, we have algorithms which have lower price of explainability when the dataset is in fixed dimenesions  [6, 12].
However, our next result is that the impossibility of shallow explanations continues to hold for $k$-means and $k$-median objectives even in the plane.

The following holds for $k$-means and $k$-median clustering objectives.
For every $k\in \mathbb{N}$, there is a point-set $X\in\mathbb{R}^2$, such that $\Depth(X,k-2)$ is unbounded. Moreover, the price of explainability of $X$ is 1.

We remark that while the construction of the dataset in <Ref> is quite simple, the dataset construction in the above theorem is quite involved and very subtle. It is inspired from what can be termed as “blocking examples”, that are seen in   discrete geometry (for example, in the context of the conjectured extremal examples for the Pach-Tardos conjecture on axis parallel rectangles [33]).

Our results for $k$-center in the plane are not as strong as the ones above for $k$-means and $k$-median. Nevertheless we are able to prove a lower bound of 2 on the price of depth reduction in the plane for $k$-center.

For every $k\in \mathbb{N}$ and every $\varepsilon>0$, there is a point-set $X\in\mathbb{R}^2$, such that $\Depth(X,k-2)$ is at least $2-\varepsilon$ for the $k$-center objective. Moreover, the price of explainability of $X$ is 1.

The rest of the paper is organized as follows. In <Ref>, we provide formal definitions that are relevant to this paper. Next, in <Ref>, we prove <Ref>, i.e., prove our impossibility results for high dimensions. Our main impossibility results for $k$-means and $k$-median (i.e., <Ref>) in the plane is proved in <Ref> and in <Ref> we prove <Ref> (which is related to the $k$-center objective). Finally, in <Ref> we conclude with some discussion and a couple of open problems.

§ PRELIMINARIES

Throughout the paper, we say a point set $X$ has dimension $d$ with size $n$, and denote by $\dist(x, y)$ the Euclidean distance between points $x$ and $y$ in the point set.

Given two sets of points $X$ and $C$ in Euclidean space, we define
the $k$-means cost of $X$ for $C$
to be $\cost_2(C):=\underset{x \in X}{\sum}\left(\underset{c \in C}{\min}\ \left(\dist(x,c)\right)^2\right)$, the $k$-median cost to be $\cost_1(C):=\underset{x \in X}{\sum}\left(\underset{c \in C}{\min}\ \dist(x,c)\right)$, and the $k$-center cost to be $\cost_{\infty}(C):=\underset{x \in X}{\max}\left(\underset{c \in C}{\min}\ \dist(x,c)\right)$.
Given a set of points $X$, the $k$-means/$k$-median/$k$-center
objective is the minimum over all point-sets $C$  of cardinality $k$ of the $k$-means/$k$-median/$k$-center
cost of $X$ for $C$. Given a cluster  $Y\subseteq X$, the contribution of $Y$ to the
$k$-means/$k$-median cost of $X$ is simply the $1$-means/$1$-median cost of $Y$.

Dasgupta et al. [11] introduced  explainable clustering through decision trees. In a threshold decision tree $\mathsf{T}$ of depth $h_{\mathsf{T}}$ and $k$ leaves, every non-leaf node is labelled  by the hyperplane $x_r = \theta$ for some $r\in [d]$ and $\theta\in\mathbb{R}$. A point $x$ is then classified by the node to the left if it's $r^{\text{th}}$ coordinate is less than $\theta$
and to the right otherwise.

They also introduced the notion of price of explainability, which is formally defined in <Ref>. Furthermore, we define price of depth reduction in <Ref> to evaluate the cost of obtaining shallow explanations.

Let $\Lambda(k)$ be the optimal  cost of  $k$-means/$k$-median/$k$-center objective for a  point-set $X$, and let $\Tilde{\Lambda}(k)$ be the optimal  cost for the same clustering objective but provided through explanations from a decision tree, the price of explainability is defined to be $\nicefrac{\tilde{\Lambda}(k)}{\Lambda(k)}$.

Let $\tilde \Lambda(k)$ be the optimal  cost of  $k$-means/$k$-medinas/$k$-center objective for a  point-set $X$ provided through explanations from a decision tree (of arbitrary depth), and let $\hat{\Lambda}(k)$ be the optimal  cost for the same clustering objective but provided through explanations from a decision tree of depth $h$, then the price of depth reduction is defined to be $\Depth(X,h):=\nicefrac{\hat{\Lambda}(k)}{\tilde\Lambda(k)}$.

§ IMPOSSIBILITY OF DEPTH REDUCTION IN HIGH DIMENSION

In this section, we give a simple construction of a dataset in high dimensions which has unbounded price of depth reduction for all three clustering objectives of interest. Formally, our results are stated in <Ref>.

For every $k\geq 3,d\ge 2$, such that $d\geq \nicefrac{k}{2}$, and every polynomial function $p:\mathbb{N}\to\mathbb{N}$, there exists a point-set $X \subset \mathbb{R}^d$ (which can be represented in $|X|^{O(1)}$ bits) such that the following properties hold for $k$-means/$k$-median/$k$-center objectives:

Correctness: There exists a decision tree of depth $k-1$ such that the price of explainability is 1.

Price of Depth Reduction: For every $h<k-1$, every decision tree of depth $h$ yields a clustering whose cost is at least $p(|X|)$ times the optimum. In other words, $\Depth(X, k-2) \geq p(|X|)$.

We emphasize that $\Depth(X, k-2)$ in the above theorem is lower bounded by some polynomial in the size of $X$ and thus is larger than every function of $k$.

§.§ Point-set Construction

We show the proof of <Ref> by explicitly constructing the desired point-set $X$. The construction is simple and applies to all three objectives. The formal description of the point-set is shown below. Let $n$ and $N$ be natural numbers.

High-Dimensional Point-set $X(n, N, d)$

Let $\eps=1/N$. For each coordinate $i,j\in [d]$, and each $a,b\in\{1,-1\}$, $X$ contains $n$ copies of the point $a\cdot \vec{e}_i + \eps\cdot b\cdot  \vec{e}_j$, where $\vec{e}_i$ is the $i$-th standard basis unit vector.

One may observe that the point-set is well-structured with $k$ balls of radius $\eps$ in $d$-dimension (named $\eps$-balls from now on), each $\eps$-ball contains $\nicefrac{n}{k}$ points evenly distributed on the sphere. Therefore the set of centers $C:=\{a\cdot \vec{e}_i:i\in [d], a\in\{1,-1\}\}$ gives optimal cost for all three objectives, provided that $\eps$ is not too big ($\eps < \frac{1}{\sqrt{2}}$). The optimal costs for the $k$-means, $k$-median, $k$-center objectives are $2nkd\cdot \eps^2$, $2kd\cdot \eps$, and $\eps$ respectively.

Note that $X \subseteq \IR^d$ and each of the points in $X$ can be stored using $2 \log(N)$ bits. Hence, $X$ can be stored using $O(|X| \log N)$ bits of storage, where $|X|$ is the number of points in the set $X$. It transpires later that $N = 1/\eps = O(p(|X|))$, therefore $X$ requires at most $O(|X|^{O(1)})$ bits.

§.§ Proof of <Ref>

We consider the case that $k$ is even. We then set $d=k/2$ and show that for an appropriate choice of $N$ and $d$, the set of centers $C:=\{a\cdot \vec{e}_i:i\in [d], a\in\{1,-1\}\}$ gives optimal cost for all $k$-means, $k$-median and $k$-center objective functions, up to any polynomial approximation factor in the size of above point set point set. If $k$ is odd, we just use a slightly different point set, where we set $d=\ceil{k/2}$, and for $i=\ceil{d/2}$, we only include $n$ copies of the point $\vec{e}_i + \eps\cdot b\cdot  \vec{e}_j$ for each $j \in [d]$ and $b \in \{0,1\}$ and not $-\vec{e}_i + \eps\cdot b\cdot  \vec{e}_j$. The proofs of all three objectives proceed in a similar fashion.

Let $d=k/2$. We can chose $N$ such that the optimal clustering for $X(n,N, d)$ w.r.t. $k$-means/$k$-median/$k$-center objective is given by the set of clusters $C:=\{C_{i,a}: 0 \leq i \leq d, a \in \{1,-1\}\}$, where $C_{i,a}:=\{a\cdot \vec{e}_i + \eps\cdot b\cdot  \vec{e}_j: 1\leq j \leq n, b \in \{1,-1\}\}$. Furthermore, for any polynomial function $p:\mathbb{N}\rightarrow \mathbb{N}$, any other choice of explainable clustering $\Tilde{C} \neq C$ has $k$-means/$k$-median/$k$-center cost at least $p(|X|)$ times the optimum.

We first calculate the costs of for three objectives with $C$ as a clustering assignment. Note that the cluster center for the cluster $C_{i,a}$ is $\mu_{i,a}=a\cdot \vec{e}_i$. Hence, the $k$-means objective has total cost of  $2nkd\cdot \eps^2=\eps|X|$, the $k$-median objective has $2nkd\cdot \eps = \eps|X|$. For the $k$-center objective, recall that $\cost_{\infty}(C):=\underset{x \in X}{\max}\left(\underset{i \in [d], a\in\{1,-1\}\}}{\min}\ \dist(x,\mu_{i,a})\right)$,  and every point has distance of $\eps$ to the center, implying that the optimal cost is $\eps$. Now consider any alternative clustering, there must exist two points located at different $\eps$-balls being assigned to the same cluster. We show that only the cost contributed by this particular pair will introduce a significant loss.

Denote an $\eps$-ball as $B_i^a\subseteq X$ for every $i\in[d]$ and $a\in\{-1,1\}$, which is a set of $\{ a\cdot \vec{e}_i + \eps\cdot b\cdot  \vec{e}_j:\forall j\in[d],\forall b\in\{-1,1\}\}$. Suppose for another clustering assignment $\Tilde{C}$, we have point $p \in B_i^a$ and $q \in B_j^b$, it follows that $\dist(p,q) \geq \sqrt{2}/2-\eps$. For $k$-means objective, it certainly holds that $\cost(\tilde{C}) \geq \dist^2(p,q)$ (Similarly, $\cost(\tilde{C}) \geq \dist(p,q)$ for $k$-median and $\cost(\tilde{C}) \geq \dist(p,q)/2$ for $k$-center). Now, we show that there exists $\eps$ such that $\cost(\Tilde{C}) \geq p(|X|) \cdot \cost(C)$ for all three objectives as follows.

* $k$-means: $\cost(\Tilde{C}) \geq \frac{(\sqrt{2}/2-\eps)^2}{\eps^2|X|} \cdot \cost(C)$, where $\cost(C) = \eps^2|X|$. Hence, we can set $\eps$ to be any value in $(0, \frac{1}{\sqrt{2|X|\cdot p(|X|)-2}})$.

* $k$-median: $\cost(\Tilde{C}) \geq\frac{\sqrt{2}/2-\eps}{\eps|X|} \cdot \cost(C)$, where $\cost(C) = \eps|X|$. Hence, we can set $\eps$ to be any value in $(0, \frac{\sqrt{2}}{2|X|\cdot p(|X|) + 2})$.

* $k$-center: $\cost(\Tilde{C}) \geq\frac{\sqrt{2}/2-\eps}{2\eps} \cdot \cost(C)$, where $\cost(C) = \eps$. Hence, we can set $\eps$ to be any value in $ (0, \frac{\sqrt{2}}{4p(|X|)+2})$.

The above results already imply that $C$ is the optimal clustering.

Next, we explicitly construct the decision tree of depth $k-1$ that outputs the optimal clustering, thus concluding the correctness of <Ref>.

There exists a decision tree of depth $k-1$ which outputs the optimal clustering for the point-set $X$ w.r.t. $k$-means/$k$-median/$k$-center objective.

Without loss of generality, we may assume that $k$ is even. The decision tree makes the following $k-1$-length sequence of hyperplanes, where $x_r=\theta$ indicates the hyperplane cut is on the $r$-th coordinate and at value $\theta$.

For $1 \leq i \leq k-1$, we describe the $i$-th level of the decision tree (the root is at level $1$). Each level has one hyperplane cut, when $i$ is odd, the cut threshold is $x_i=\nicefrac{1}{2}$. Any point with the $i$-th coordinate larger than this is classified into the cluster with center $e_i$ (this is a leaf), and if the $i$-th coordinate of a point is smaller than this threshold, it moves to the next level of the decision tree. If $i$ is even, the node at that level considers the threshold at $x_i=-\nicefrac{1}{2}$. Any point with the $i$-th coordinate smaller than this is classified into the cluster with center $e_i$, and if the $i$-th coordinate of a point is larger than this threshold, it moves to the next level of the decision tree (if $i=k-1$, this is the final level of the decision tree and it is just classified to the cluster with center $-e_k$). Every node in this decision tree has two children, one of which is a leaf except the last level. Note that the leaf represents a subspace that contains an $\eps$-ball as constructed, thus the decision tree induces the optimal clustering for all objectives.

Now, to prove the price of depth reduction in <Ref>, it only remains to show that any decision tree of depth less than $k-1$ yields a clustering $\tilde{C} \neq C$, as claimed by <Ref>.

Every decision tree of depth less than $k-1$ outputs a clustering which misclassifies (w.r.t. the clustering $C$ in Lemma <ref>) at least one point.

We say that a node $v$ in the decision tree is trivial for the point set $X$, if the node has a child, which contains exactly the same points as $v$. In other words, a trivial node does not partition any points in the remaining point-set into a cluster. We can assume that the minimum depth decision tree does not contain any trivial nodes because we can contract that node without changing the final classification of $X$, and the depth can only decrease as a result of this contraction. Hence, without loss of generality, we can assume that every node in the tree is non-trivial.

Consider any decision tree $\tree$ of depth at most $k-2$ with $k$ leaves that induces an explainable clustering for $X$. There must exist at least two nodes in $\tree$ with two leaf children, by the pigeon-hole principle. We argue that such decision tree inevitably misclassifies at least one point. For any cluster $C_{i,a}$ with a hyperplane cut $x_i=\theta$, if the threshold value $\theta > 1+ \eps$ or $\theta < -1 -\eps$, then there exists a trivial node in $\tree$. If $-\eps \leq \theta \leq \eps$, then at least one point is misclassified since it cuts through other $\eps$-balls on the orthogonal coordinate. Therefore to produce the optimal clustering, every threshold value of hyperplane cuts satisfies $\theta \in (-1+\eps, -\eps) \cup (\eps, 1-\eps)$. Notice that only one cluster can be separated from the remaining point-set by cuts of this type, with the only exception on the last cut.  Therefore every node has one leaf child and the last node in the decision tree has two leaf children. If there are two such nodes, some hyperplane cut must have threshold in $(-\eps, \eps)$, leading to misclassified points. A demonstration of this argument with the point-set $X$ in two dimensions is shown in <Ref>.

An illustration of the high-dimensional point-set $X$ in 2D with axis-parallel cuts. On the left, (a) shows that with threshold $\theta \in (-1+\eps, -\eps) \cup (\eps, 1-\eps)$, the optimal clustering of the four $\eps$-balls can be induced by a 3-depth decision tree. On the right, (b) shows that any shallower decision tree has a cut with threshold $-\eps \leq \theta \leq \eps$, thus inevitably output a clustering with at least one misclassified point.

We have shown in <Ref> that any alternative clustering $\Tilde{C}$ that misclassifies one point must have $\cost(\Tilde{C}) \geq p(|X|) \cdot \cost(C)$, therefore completing the proof.

§ IMPOSSIBILITY OF DEPTH REDUCTION IN THE PLANE FOR $K$-MEANS AND $K$-MEDIAN

In this section, we prove a strong lower bound on the price of depth reduction for $k$-means and $k$-median in two dimensions. As in <Ref>, we construct a point-set $X \subseteq \mathbb{R}^2$, for which the optimal clustering can be explained by a decision tree of depth $k-1$ whose price of explanation is 1. However, we show that, the low-dimensionality does not help reduce the price of depth reduction. Formally, we prove the following theorem.

For every $k\geq 3$, and every polynomial function $p:\mathbb{N}\to\mathbb{N}$, there exists a point-set $X \subset \mathbb{R}^2$ (which can be represented in $|X|^{O(1)}$ bits) such that the following properties hold for $k$-means/$k$-median objectives:

Correctness: There exists a decision tree of depth $k-1$ such that the price of explainability is 1.

Price of depth reduction: For every $h<k-1$, every decision tree of depth $h$ yields a clustering whose cost is at least $p(|X|)$ times the optimum. In other words, $\Depth(X, k-2) \geq p(|X|)$.

The proofs of the above theorem for the $k$-means and $k$-median objectives are very similar. Briefly, the underlying idea is to construct a point-set whose clusters are positioned such that the axis-parallel (either $x$ or $y$-axis) interval between any two clusters except one pair are blocked by a new cluster. Since the partition of clusters must be parallel to either $x$ or $y$-axis, we have that any cut line going through that interval will separate the points in the block cluster, and assign at least one point incorrectly. Therefore, to produce a perfect clustering, the decision tree must follow an `onion-peeling' approach, that is to output one cluster at each partition of the remaining space, leading to a decision tree of depth $k-1$. To get a lower bound on the price of depth reduction, it is imperative that the clusters are geometrically unbalanced, and we choose the distances between the clusters and the number of points in each cluster carefully.

§.§ Point-set Construction and Optimal Clustering

We now describe the point-set that will be used to prove the lower bound on the price of depth reduction.
We describe the point-set using weights as it simplifies the analysis. It is trivial to get rid of the weights by simply replacing a point $p$ having weight $w$, with $w$ copies of the unweighted point $p$.

Informally, the point-set is constructed by  successively adding sets of points $C_i$ for $1 \leq i \leq k$ to it. Later, we will prove that the optimum $k$-means/$k$-median clustering is given by the partitioning $C:=(C_1, C_2, \ldots, C_k)$. We parameterize the  construction of the point-set through an increasing sequence $\{h_i\}_{i=1}^k$ and a decreasing sequence $\{w_i\}_{i=1}^k$ of integers, that fix the positions and the weights of the points respectively. Later we instantiate these parameters for a specific setting.

Weighted point-set $X(w,h)$:

Parameters: Two sequences of positive integers, $\{w_i\}_{i=1}^{k}$ and  $\{h_i\}_{i=1}^{k}$

Initialize the set $C_1$ having two copies of the same point, i.e.,  $p_1^1=p_1^2=(0,0)$ each with weight $w_1$, and another cluster $C_2$ having two copies of the same point, i.e., $p_2^1=p_2^2=(h_2,0)$ with weight $w_2$.  For $i = 3,4,\ldots, k$, add the sets $C_i$ as follows.

* If $i$ is odd, add two points with the same weight $w_i$,  where $p_i^1 = \left(\left(p_{i-2}^{1}\right)_x-1, \left(p_{i-2}^{1}\right)_y+h_i\right), p_i^2 = \left(\left(p_{i-1}^2\right)_x+1,\left(p_{i-2}^{2}\right)_y+h_i\right)$ (we clarify that $(p_i^j)_x$ and $(p_i^j)_y$ denote the $x$ and $y$ coordinates of the point $p_i^j$ respectively).

* If $i$ is even, add two points with the same weight $w_i$,  where $p_i^1 = \left(\left(p_{i-2}^{1}\right)_x+h_i, \left(p_{i-2}^{1}\right)_y-1\right), p_i^2 = \left(\left(p_{i-2}^{2}\right)_x+h_i, \left(p_{i-1}^2\right)_y+1\right)$.

In <Ref>, we have an illustration of $X(w,h)$. In addition, we have shown the partition of the space using axis parallel lines (coming from a decision tree of depth $k-1$), which recovers the clustering $C$. We remark that in <Ref>, $k$ is odd and $h_k$ is the distance between clusters $C_k$ and $C_{k-2}$, which is not shown in the figure, but similar as $h_5$ is the distance from $C_3$ to $C_5$.

We make the following observations about the point-set $X(w,h)$:

* Every set $C_i$ has two points, both with the same weight and there are $2k$ points in total.

* The straight line connecting the two points in the same cluster is either parallel to $x$-axis (if $i$ is odd) or $y$-axis (if $i$ is even).

* For any $r<i$ when $i,r$ are odd, we have $(p_i^1)_x < (p_r^1)_x$ and $(p_i^2)_x > (p_r^2)_x$. Similarly, when $r < i$ and $i,r$ are even, $(p_i^1)_y <(p_r^1)_y$ and $(p_i^2)_y > (p_r^2)_y$. Therefore, the set $C_i$ `blocks' any possible cut within the interval of the two points on the $x$ axis if $i$ is even or the $y$ axis if odd. This forbids any partition that gives a low-depth decision tree to classify the point-set into exactly $C_1, C_2, \dots, C_k$, which is the key property to complete the proof.

Remarkably, our construction imposes an exponentially increasing interval between the latest added cluster $C_i$ and previous clusters. However, this does not result in a numerically egregious point set. As shown in <Ref>, together with the specification of parameters $w, h$, $X(w,h)$ can be represented using polynomial space.

We give the complete proof of <Ref> in the next section.

§.§ Proof of <Ref>

We start with showing that the sets $C_i$ attain the optimum for both clustering objectives with proper choices of the sequences $\{w_i\}_{i=1}^k,\{h_i\}_{i=1}^k$. Further, any alternative clustering explanations can introduce a significant loss on the objective.

We can choose the sequences $\{w_i\}_{i=1}^k,\{h_i\}_{i=1}^k$  such that the optimal clustering for $X(w,h)$ w.r.t. $k$-means/$k$-median objective is given by the set of clusters $C := (C_1,C_2, \ldots,C_{k})$ as defined. Furthermore, for any polynomial function p: $\mathbb{N} \rightarrow \mathbb{N}$, any other choice of explainable clustering $\Tilde{C} \neq C$ has $k$-means/$k$-median cost at least $p(|X|)$ times the optimum.

Consider an alternative clustering $\tilde{C}:=(\tilde C_1, \ldots, \tilde C_k)$ of the weighted point-set $X$. We now specify the parameters that lead to $\cost(\Tilde{C})  \geq p(|X(w,h)|) \cdot \cost(C))$.

Let $h_i=\left( 4\sqrt{k \cdot p(2k)} \right)^i$ and $w_i= \nicefrac{h_k^2}{h_{i-1}^2}$ for $i \geq 3$ and $w_1=w_2=\nicefrac{h_k^2}{h_2^2}$. This choice of parameters implies that the $k$-means cost of each cluster $C_i$ are approximately equal. This is because the distance between the two points in the cluster $C_{2i+1}$ is $h_2+h_4+ \dots + h_{2i}+2i$ and the distance between two points in the cluster $C_{2i}$ is $h_3+h_5+\dots+h_{2i-1}+2i$. Hence, we have $h_i \geq \sum_{j \leq i}h_i$, $\frac{w_i h_{i-1}^2}{2}\leq \cost(C_i) \leq 4 w_i h_{i-1}^2$, for every $i \in [k]$. This implies that

$$\forall{i\in[k]},\ \ \  \frac{h_k^2}{2} \leq \cost(C_i) \leq 4 h_k^2. $$

As $\Tilde{C} \neq C$, there exist $i,j,j' \in [k]$, with $j > j'$ and $a,b \in \{1,2\} $ such that $p_j^a, p_{j'}^b \in \Tilde{C}_i$. Let $\Tilde{\mu}_i$ be the center of $\Tilde{C}_i$. As the distance between $p_j^a$ and $p_{j'}^b$ is at least $h_j$, this implies that either $\dist(p_{j}^a, \Tilde{\mu}_i) \geq h_j/2$ or $\dist(p_{j'}^b, \Tilde{\mu}_i) \geq h_j/2$. As the point $p_j^a$ has a larger weight than the point $p_{j'}^b$, we can lower bound the cost contributed by the cluster $\Tilde{C}_i$ by

\begin{align*} \cost(\Tilde{C}_i) \geq \frac{w_jh_j^2}{4}=\frac{w_jh_{j-1}^2}{4}\frac{h_j^2}{h_{j-1}^2} &\geq \frac{\cost(C)}{16k} \frac{h_j^2}{h_{j-1}^2}=k^2 p(2k)^3 \cost(C) \\ & \geq p(2k) \cost(C) = p(|X|) \cost(C) \end{align*}

The analysis of $k$-median is almost the same as $k$-means except that the sequence $\{h_i\}_{i=1}^k$ is defined by $h_i=\left(4 k^3 \cdot p(k)^3 \right)^i$, and the sequence $\{w_i\}_{i=1}^k$ is $w_i= \frac{h_k}{h_i}$.

With the specification of $h, w$ in <Ref>, we show the size of the point-set can be represented using bits
polynomial in $|X|$.

The point-set $X(w,h)$ can be stored using $O(|X|^{O(1)})$ bits.

The $x$-coordinates for every point in this point-set are integral and upper bounded by $k+\sum_{i=1}^{\lfloor k/2 \rfloor}h_{2i}$. Similarly, $y$-coordinates are upper bounded by $k+\sum_{i=1}^{\lfloor k/2 \rfloor}h_{2i+1}$. Recall that $\{h_i\}_{i=1}^k$ is an increasing sequence and $\{w_i\}_{i=1}^k$ is decreasing. Hence, each point in the point-set can be stored in space $O(\log h_k)$. Further, each weight can be stored in space $O( \log w_1)$ (the weights are scaled to ensure integrality). Hence, the entire point-set can be stored in space $O(k(\log h_k+\log w_1))$. As become evident, both $h_k$ and $w_1$ are $O(k^k)$. Recall $|X| = 2k$, hence $X(w,h)$ requires at most $O(|X|^{O(1)})$ bits to represent.

Next, we show that for a weighted point-set $X(w,h)$ described above, a $k-1$-depth decision tree gives the optimal clustering, which concludes the correctness of <Ref>.

There exists a decision tree of depth $k-1$ which outputs the optimal clustering for the weighted point-set $X$ w.r.t. $k$-means/$k$-median objective.

We describe a decision tree of depth $k-1$ to output the clustering $C=(C_1, \ldots, C_k)$. It has depth $k-1$, with there being a leaf at every level of the decision tree. At the $i$-th level of the decision tree, if $k-i+1$ is even, the cut is along the $x$-axis with threshold at $x=(p_{k-i+1}^1)_x-\nicefrac{1}{2}$. For any point, if the $x$-coordinate of that point is larger than this threshold, it is classified to the cluster $C_{k-i+1}$. Otherwise, if $i \neq k-1$ it proceeds to the next level of the tree, and if $i=k-1$, it is classified to the cluster $C_1$. If $k-i+1$ is odd, the cut is along the $y$-axis with threshold $y=(p_{k-i+1}^1)_y-\nicefrac{1}{2}$. If the $y$-coordinate of a point is larger than this threshold, it is classified to the cluster $C_{k-i+1}$. Otherwise, if $i \neq k-1$ it proceeds to the next level of the tree, and if $i=k-1$, it is classified to the cluster $C_1$.

We now show that this particular clustering cannot be induced by any decision tree of lower depth. And any shallower decision tree yields another clustering.

Every decision tree of depth less than $k-1$ outputs a clustering which misclassifies (w.r.t. the clustering $C$) at least one point.

We assume that every node in the decision tree is non-trivial (see the definition of `non-trivial' in the proof of <Ref>). We now apply induction on $k$. If there are only two points in the point-set, there is only one way to correctly classify them and that uses a decision tree of depth $1$. This proves the base case.

Let $k$ be odd. The two points in the cluster $C_k$: $p_k^1 = \left(\left(p_{k-2}^{1}\right)_x-1, \left(p_{k-2}^{1}\right)_y+h_i\right)$ and $p_k^2 = \left(\left(p_{k-1}^2\right)_x+1,\left(p_{k-2}^{2}\right)_y+h_k\right)$ are to the left and to the right of every point in $C_j$, for every $j < k$.  We first consider the case that the first threshold (starting from the root of the decision tree) is along the $x$-axis. Any decision tree that outputs the clustering $C = (C_1, \ldots, C_k)$ must classify $p_k^1$ and $p_k^2$ in the same cluster. The only possible cuts along the $x$-axis that satisfy this property are cuts with threshold larger than the $x$-coordinate of $p_k^2$ or cuts with a threshold lesser than the $x$-coordinate of $p_k^1$. In both these cases, the second level of the decision tree has two nodes, but all the points in the point set get classified into one of them, which would make it trivial. Hence, the first threshold cut must be along the $y$-axis.

Now, we consider the case that the first threshold cut is along the $y$-axis. In order to output the clustering $C$, the cut would have to have $y$-coordinate less than $\left(p_{k-1}^1\right)_y$ or greater than $\left(p_{k-1}^2\right)_y$. Otherwise, the cut would classify $p_{k-1}^1$ and $p_{k-1}^2$ into different clusters. If the threshold has $y$-coordinate greater than $\left(p_k^1\right)_y$ or less than $\left(p_{k-1}^1\right)_y$, the cut would be trivial as the second level of the decision tree would have two nodes, but all the points in the point set would get classified into one of them, which would make it trivial. Hence, the threshold lies between $\left(p_k^1\right)_y$ and $\left(p_{k-1}^2\right)_y$. This implies that the  second level of the decision tree contains two nodes, and all the points in the set $C_k$ get classified into one of them. As the decision tree must output the clustering $\Tilde{C}$ on the given point set and is non trivial, that node must be a leaf. All the remaining points in the point set (which is another point set in the same family with parameter $k-1$) go to the other node in the second level, and the inductive hypothesis implies subtree rooted at this node must have depth at least $k-2$, which implies that the decision tree we are considering must have depth $k-1$.

The proof proceeds similarly when $k$ is even, except that the only possible non trivial cuts in the first level would be along the $x$-axis with thresholds between $\left(p_{k}^1\right)_x$ and $\left(p_{k-1}^2\right)_x$.

This completes the proof of Theorem <ref>. With the specification of $h,w$, <Ref> shows that the point-set can be represented using $|X|^{O(1)}$ bits. The correctness is implied by <Ref>, the price of depth reduction lower bound is shown together by <Ref> and <Ref>.

§ LOWER BOUND ON PRICE OF DEPTH REDUCTION IN THE PLANE FOR $K$-CENTER

In this section, we prove a lower bound on the price of depth reduction for the $k$-center objective. Specifically, we construct a point-set $X \subseteq \mathbb{R}^2$, for which the optimal clustering can be explained by a decision tree of depth $k-1$ whose price of explanation is 1. Furthermore, we show that the price of depth reduction is at least $2-\varepsilon$, for any small $\varepsilon>0$.  Formally, we state our result as follows:

For every $k\geq 3$, and every $\varepsilon>0$, there exists a point-set $X \subset \mathbb{R}^2$ (which can be represented in $|X|^{O(1)}$ bits) such that the following properties hold for $k$-center objective:

Correctness: There exists a decision tree of depth $k-1$ such that the price of explainability is 1.

Price of depth reduction: For every $h<k-1$, every decision tree of depth $h$ yields a clustering whose cost is at least $(2-\varepsilon)$ times the optimum. In other words, $\Depth(X, k-2) \geq 2-\varepsilon$.

§.§ Point-Set construction

The construction below is similar in many aspects to the  point-set constructed in <Ref>. One major difference is that each cluster has 4 points, and we use the notation of $p_i^a$ where $i \in [k], a\in[4]$ to indicate the $a$-th point in the $i$-th cluster. Also, the points are not weighted here. Again, as in Section <ref>, we define the point-set through an underlying clustering $C:=(C_1,\ldots ,C_k)$.

Point-set $X$ for $k$-center

Initialize the first two clusters $C_1, C_2$ symmetrically across the $y$-axis, each containing four points. In $C_1$, the four points are located at $p_1^1 = (-1,0), p_1^2 = (-1.5,0.5), p_1^3= (-1,1), p_1^4 = (-0.5,0.5)$. In $C_2$, the four points are located at $p_2^1 = (1,0), p_2^2 = (0.5,0.5), p_2^3= (1,1), p_2^4 = (1.5,0.5)$.

Construct $C_3$ with four points, where $(p_3^a)_x = (p_1^a)_x+1$ and $(p_3^a)_y = (p_1^a)_y+2$ for $a \in [4]$.

Construct $C_4$ with four points, where $(p_4^a)_x = (p_2^a)_x+2$ and $(p_4^a)_y = (p_2^a)_y+1$ for $a \in [4]$.

For $i = 5, \ldots, k$, add cluster $C_i$ containing four points iteratively, where $(p_i^a)_x = (p_{i-2}^a)_x+2$ and $(p_i^a)_y = (p_{i-2}^a)_y+2$ for $a \in [4]$.

From the construction above, it is easy to see that the $k$-center cost of $X$ is at most $\nicefrac{1}{2}$ (as given by the clustering $C$). Further, it only takes $\tilde{O}(|X|)$ bits to store the whole point-set.

In <Ref>, we have an illustration of point-set $X$. In addition, we have shown the partition of the space using axis parallel lines (coming from a decision tree of depth $k-1$), which recovers the clustering $C$.

§.§ Proof of Theorem <ref>

We start with the correctness proof in <Ref>. The price of depth reduction can be concluded by <Ref> with <Ref>.

There exists a decision tree of depth $k-1$ which outputs the optimal clustering for point-set $X$ w.r.t. the $k$-center objective.

Consider the following sequence of  $k-1$ threshold cuts. For $i=k,k-1,\ldots,2$:

* If $i$ is even, create a cut along $x=i-1/2$.

* If $i$ is odd, create a cut along $y=i-1/2$.

We can see that the first cut partitions the first cluster away from the rest of the point set entirely. This applies to all the other cuts as well. Hence, the above sequence transforms to a decision tree of depth $k-1$ with a leaf in every level and outputs an explainable clustering identical to the optimal clustering.

Every decision tree of depth less than $k-1$ outputs a clustering which misclassifies (w.r.t. the optimal clustering $C$) at least one point.

The proof of this lemma is similar to the proof of Lemma <ref>. We prove the base case for $3$ clusters and show that the only possible cuts in the first level of the decision tree are those which separate out the cluster $C_k$ from the remaining points. We can then use induction on $k$ to show that any decision tree that does not misclassify any point has depth $k-1$

Consider any other choice of explainable clustering $\Tilde{C} \neq C$. The $k$-center objective of $\Tilde{C}$ is at least $1$.

Consider any clustering $\Tilde{C} \neq C$ with $k$-center cost less than $1$. Firstly, for all $i \geq 5$, the distance between points in the cluster $C_i$ and points in any other cluster is at least $2$. Hence, if any cluster contains a point from a cluster $C_i$, where $i \geq 5$ and a point from a cluster $C_j$, where $j \neq i$, the radius of the circle containing both these points is at least $2$, means that the center of the cluster these two points are assigned two must be distance at least $1$ from one of them, which implies that the $k$-center cost of this clustering must be at least $1$. Hence, the clustering $\Tilde{C}$ must either split some of these clusters into multiple clusters, or leave them intact.

Let us first consider the case that $\Tilde{C}$ splits at least one of these clusters. As there are only $k$ clusters in total, that means that the points in the first $4$ clusters have to be divided into at most $3$ clusters. However, consider the points $p_1^1, p_2^1,p_3^1, p_4^1$. The pairwise distances between each of these points is at least $2$, and hence, for the $k$-center cost to be less than $1$, they all have to be in different clusters which is not possible as there are only $3$ clusters to divide them into.

We now consider the case that $\Tilde{C}$ leaves all the clusters $C_i$ for $i \geq 5$ intact. In this case, it has to induce a different clustering among the points in the first $4$ clusters. As in the previous case, the points $p_1^1, p_2^1,p_3^1, p_4^1$ have to be in separate clusters because their pariwise distances are larger than $2$.

Consider the point $p_4^3, p_4^3$ and $p_4^4$. They are at a distance more than $2$ from every one of these point apart from $p_4^1$, and hence have to be assigned to the cluster containing $p_4^1$. Note that the point $p_4^4$ is at a distance greater than $2$ from every point outside $C_4$. This implies that $\Tilde{C}$ must preserve the cluster $C_4$.

Next we prove that $\Tilde{C}$ preserves the cluster $C_3$. The point $p_3^3$ has to be assigned to the cluster containing $p_3^1$, and it is at a distance of at least $2$ from every point outside $C_3$. This also implies that the cluster containing $p_3^1$ can only contain points from $C_3$. Note that the points $p_3^2$ and $p_3^4$ are at distances greater than $2$ from $p_1^1$ and $p_2^1$ which implies that $\Tilde{C}$ must preserve the cluster $C_3$.

We can now show that the points $p_1^2$ and $p_1^3$ cannot be assigned to the cluster containing $p_2^1$ and hence must be assigned to the cluster containing $p_1^1$.  This implies that $p_2^4$, $p_2^3$ and $p_2^2$ must be assigned to the cluster containing $p_2^1$. Finally this also implies that $p_1^4$ is assigned to the cluster contiaining $p_1^1$. Hence, $\Tilde{C}$ must preserve the clusters $C_1$ and $C_2$ as well.

§ DISCUSSION AND OPEN PROBLEMS

In this paper, we introduced the notion of price of depth reduction, and showed that even in the plane, there is a dataset for which it is unbounded for the $k$-means and $k$-median objectives. However, one may wonder if our lower bound construction is too pathological. To address this concern, we now informally argue that our impossibility result gives a characterization of every dataset w.r.t. its optimal decision tree for explainable clustering.

We (informally) claim that our paper gives a complete characterization of the structure of datasets w.r.t. their decision tree depth. Call a rooted decision tree “totally skewed” if it's depth is 1 less than the number of leaves in the tree. We note that in every decision tree, we can identify non-leaf nodes, say
$v_1,\ldots ,v_t$ (for the smallest value of $t$), with the following two guarantees: (i) Let $L_i$
be the subset of leaves contained in the subtree rooted at $v_i$. Then the
$L_i$s form partition of the set of leaves (i.e., point-set) (ii) Each subtree rooted at
$v_i$ is either a complete binary tree or a totally skewed tree. This is a simple graph-theoretic claim and even admits an algorithmic proof.

We also note that if the optimal explanation for a dataset is a totally skewed tree then the dataset is "isomorphic" to our seemingly pathological dataset given in <Ref>. To see this, consider all the cuts except the first cut. If the last (closest to the root) cluster didn’t intersect the second cut, we can use all the cuts except the first and add an additional cut somewhere else in the subtree to separate the last cluster, thus getting a smaller depth tree. So, the second cut intersects the last cluster. This means that the last cluster has to block the gap between some previous clusters. We can repeat this argument to show that the clusters are added in layers blocking the space between previous clusters.

Putting these two observations together, if we only have access to the optimal explanation of a dataset, then we apply the decomposition mentioned above to obtain the subtrees, and depending on whether the subtree is complete  or totally skewed, we can infer the structure of the clusters in space (using our construction in <Ref>) without looking at the dataset.
In other words, given the optimal decision tree of the
$k$-clustering of a dataset, by using the above partitioning we can identify local “pockets” where the tree is complete  or totally skewed. From this we can visualize the pockets as either having very good hyperplane separators or being isomorphic to the construction in <Ref>. Another inference one can draw is that the pocket of clusters corresponding to the totally skewed subtree is highly unbalanced (more about this later). So it is entirely possible that for any dataset if it admits roughly balanced clusters then it can be approximated by low depth decision tree, and we leave this as a direction to explore for future research.

Additionally, we believe that the algorithm given in [12] yields a low depth decision tree (with close to the optimal clustering cost), if the dataset is in fixed dimensions and admits a low depth decision tree (with optimal clustering cost). In fact, if we look at our construction in <Ref> and make the clusters balanced (while preserving the distances), then it is easy to note that the cost of the clustering is dominated by the “outermost” clusters. Thus, as long as the explanations preserves the outermost clusters, the rest of the dataset can be partitioned in any way desired (to lower the depth), and the increase in the clustering cost would be negligible.

However, for high dimensions (such as
$d=\Omega(k)$), our construction from <Ref> is balanced, and in fact quite natural. To see this, assume a generative model coming from a mixture of
$k$ Gaussians, where we first draw $k$
independent random points from a Gaussian distribution and then generate the entire dataset by using these $k$
points as the means of the $k$
many Gaussian distributions. With high probability these $k$
points (centers) will be nearly orthogonal, and therefore the dataset will be morally like our construction in <Ref>, and thus admit no low depth explanation. Of course, one needs to be careful in the analysis as the claim relies on the radius of each cluster (variance of the Gaussian) and how "rotated" the $k$
centers are from the standard basis. We leave this analysis and computation for future research.

Finally, we dedicate the rest of the section to highlight a couple of open problems.

Open Problem 1. Our  dataset construction for the price of depth reduction for the $k$-center objective in the plane, only gave a lower bound of (slightly less than) two. We believe that it might not be possible to improve our lower bound any further and leave it as  an important open problem to find an  algorithm (if it exists) that provides a shallow decision tree explanation for all datasets in the plane and whose price of depth reduction is upper bounded by 2 (or at least by some constant independent of $k$).

Open Problem 2. We think that an intriguing direction for future research is to explore bicriteria approximation of price of depth reduction.
Elaborating, we wonder  if it is possible to obtain a tradeoff between the number of leaves (clusters) in the decision tree and the price of depth reduction. This suggested research direction is a natural extension of  [29], where the authors showed a near optimal tradeoff between the number of leaves in the decision tree and the price of explanation.

§.§.§ Acknowledgements

We thank Vincent Cohen-Addad for some preliminary discussions.

[1]
Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward.
Better guarantees for k-means and euclidean k-median by primal-dual
SIAM J. Comput., 49(4), 2020.

[2]
Sayan Bandyapadhyay, Fedor Fomin, Petr A Golovach, William Lochet, Nidhi
Purohit, and Kirill Simonov.
How to find a good explanation for clustering?
In Proceedings of the AAAI Conference on Artificial
Intelligence, volume 36, pages 3904–3912, 2022.

[3]
Vincent Cohen-Addad, Philip N. Klein, and Claire Mathieu.
Local search yields approximation schemes for k-means and k-median in
euclidean and minor-free metrics.
In IEEE 57th Annual Symposium on Foundations of Computer
Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New
Jersey, USA, pages 353–364, 2016.

[4]
Vincent Cohen-Addad, Hossein Esfandiari, Vahab S. Mirrokni, and Shyam
Improved approximations for euclidean k-means and
k-median, via nested quasi-independent sets.
In Stefano Leonardi and Anupam Gupta, editors, STOC '22: 54th
Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20
- 24, 2022, pages 1621–1628. ACM, 2022.

[5]
Vincent Cohen-Addad, Andreas Emil Feldmann, and David Saulpic.
Near-linear time approximation schemes for clustering in doubling
CoRR, abs/1812.08664, 2018.

[6]
Moses Charikar and Lunjia Hu.
Near-optimal explainable k-means for all dimensions.
In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA), pages 2580–2606. SIAM, 2022.

[7]
Vincent Cohen-Addad and Karthik C. S.
Inapproximability of clustering in $l_p$-metrics.
In 2019 IEEE 60th Annual Symposium on Foundations of Computer
Science, pages 519–539, 2019.

[8]
Vincent Cohen-Addad, Karthik C. S., and Euiwoong Lee.
On approximability of clustering problems without candidate centers.
In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM
Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10
- 13, 2021, pages 2635–2648. SIAM, 2021.

[9]
Vincent Cohen-Addad, Karthik C. S., and Euiwoong Lee.
Johnson coverage hypothesis: Inapproximability of k-means and
k-median in lp-metrics.
In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings
of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual
Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 1493–1530.
SIAM, 2022.

[10]
Vincent Cohen-Addad.
A fast approximation scheme for low-dimensional k-means.
In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium
on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10,
2018, pages 430–440, 2018.

[11]
Sanjoy Dasgupta, Nave Frost, Michal Moshkovitz, and Cyrus Rashtchian.
Explainable k-means and k-medians clustering.
In International conference on machine learning, pages
7055–7065. PMLR, 2020.

[12]
Hossein Esfandiari, Vahab Mirrokni, and Shyam Narayanan.
Almost tight approximation algorithms for explainable clustering.
In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA), pages 2641–2663. SIAM, 2022.

[13]
Tomás Feder and Daniel H. Greene.
Optimal algorithms for approximate clustering.
In Janos Simon, editor, Proceedings of the 20th Annual ACM
Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA,
pages 434–444. ACM, 1988.

[14]
Nave Frost, Michal Moshkovitz, and Cyrus Rashtchian.
Exkmc: Expanding explainable k-means clustering.
CoRR, abs/2006.02399, 2020.

[15]
Zachary Friggstad, Mohsen Rezapour, and Mohammad R. Salavatipour.
Local search yields a PTAS for k-means in doubling metrics.
In IEEE 57th Annual Symposium on Foundations of Computer
Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New
Jersey, USA, pages 365–374, 2016.

[16]
Magzhan Gabidolla and Miguel Á Carreira-Perpiñán.
Optimal interpretable clustering using oblique decision trees.
In Proceedings of the 28th ACM SIGKDD Conference on Knowledge
Discovery and Data Mining, pages 400–410, 2022.

[17]
Buddhima Gamlath, Xinrui Jia, Adam Polak, and Ola Svensson.
Nearly-tight and oblivious algorithms for explainable clustering.
Advances in Neural Information Processing Systems,
34:28929–28939, 2021.

[18]
Teofilo F. Gonzalez.
Clustering to minimize the maximum intercluster distance.
Theor. Comput. Sci., 38:293–306, 1985.

[19]
Anupam Gupta, Madhusudhan Reddy Pittu, Ola Svensson, and Rachel Yuan.
The price of explainability for clustering, 2023.

[20]
Dorit S. Hochbaum and David B. Shmoys.
A unified approach to approximation algorithms for bottleneck
J. ACM, 33(3):533–550, 1986.

[21]
Mario Köppen.
The curse of dimensionality.
In 5th online world conference on soft computing in industrial
applications (WSC5), volume 1, pages 4–8, 2000.

[22]
Stavros G. Kolliopoulos and Satish Rao.
A nearly linear-time approximation scheme for the euclidean k-median
SIAM J. Comput., 37(3):757–782, June 2007.

[23]
Eduardo Sany Laber.
The computational complexity of some explainable clustering problems.
arXiv preprint arXiv:2208.09643, 2022.

[24]
Connor Lawless and Oktay Gunluk.
Cluster explanation via polyhedral descriptions.
arXiv preprint arXiv:2210.08798, 2022.

[25]
Eduardo S Laber and Lucas Murtinho.
On the price of explainability for some clustering problems.
In International Conference on Machine Learning, pages
5915–5925. PMLR, 2021.

[26]
Eduardo Laber, Lucas Murtinho, and Felipe Oliveira.
Shallow decision trees for explainable k-means clustering.
Pattern Recognition, 137:109239, 2023.

[27]
Christoph Molnar.
Interpretable machine learning.
Lulu. com, 2020.

[28]
Konstantin Makarychev and Liren Shan.
Near-optimal algorithms for explainable k-medians and k-means.
In Marina Meila and Tong Zhang, editors, Proceedings of the 38th
International Conference on Machine Learning, ICML 2021, 18-24 July 2021,
Virtual Event, volume 139 of Proceedings of Machine Learning Research,
pages 7358–7367. PMLR, 2021.

[29]
Konstantin Makarychev and Liren Shan.
Explainable k-means: don’t be greedy, plant bigger trees!
In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory
of Computing, pages 1629–1642, 2022.

[30]
Konstantin Makarychev and Liren Shan.
Random cuts are optimal for explainable k-medians, 2023.

[31]
W James Murdoch, Chandan Singh, Karl Kumbier, Reza Abbasi-Asl, and Bin Yu.
Definitions, methods, and applications in interpretable machine
Proceedings of the National Academy of Sciences,
116(44):22071–22080, 2019.

[32]
Rok Piltaver, Mitja Luštrek, Matjaž Gams, and Sanda Martinčić-Ipšić.
What makes classification trees comprehensible?
Expert Systems with Applications, 62:333–346, 2016.

[33]
János Pach and Gábor Tardos.
Cutting glass.
In Proceedings of the sixteenth annual symposium on
Computational geometry, pages 360–369, 2000.

[34]
C Robert Taylor.
Dynamic programming and the curses of dimensionality.
In Applications of dynamic programming to agricultural decision
problems, pages 1–10. CRC Press, 2019.

[35]
Vijay V. Vazirani.
Approximation algorithms.
Springer, 2001.

[36]
Michel Verleysen and Damien François.
The curse of dimensionality in data mining and time series
In International work-conference on artificial neural networks,
pages 758–770. Springer, 2005.