* Proposition A.2. If $[\hat{\kappa}_{1}]\\!-\\![\hat{\kappa}_{2}]\\!\succeq\\!0$, then we have that $C_{\alpha}([\hat{\kappa}_{1}]\|[\hat{\kappa}_{2}])\\!\geq\\!0$. If, however, $[\hat{\kappa}_{1}]\\!-\\![\hat{\kappa}_{2}]\\!\preceq\\!0$, then $C_{\alpha}([\hat{\kappa}_{1}]\|[\hat{\kappa}_{2}])\\!\leq\\!0$. The same results hold in the mirrored and tripartite cases.

Invariance. We can also demonstrate that the matrix-based $\alpha$-cross-
entropies are conserved under unitary transformations; they hence preserve
inner products.

  * Proposition A.3. We have $C_{\alpha}([\hat{\kappa}_{1}]\|[\hat{\kappa}_{2}])\\!=\\!C_{\alpha}(U[\hat{\kappa}_{1}]U^{*}\|U[\hat{\kappa}_{2}]U^{*})$ for any unitary operator $U\\!\\!\in\\!\mathbb{R}^{n\times n}$. The same results hold in the mirrored and tripartite cases.

The non-mirrored $\alpha$-cross-entropies also satisfy
$C_{\alpha}([\hat{\kappa}_{1}]\|[\hat{\kappa}_{2}])\\!=\\!C_{\alpha}(V[\hat{\kappa}_{1}]V^{*}\|V[\hat{\kappa}_{2}]V^{*})$
for any isometry matrix
$V\\!\\!\in\\!\mathbb{R}^{n\times n}$; again the same result holds in the
mirrored and tripartite cases. Isometry invariance naturally implies
unitary invariance. Without isometry invariance, uniformly translating the
arguments, for instance, would alter the cross-entropies, thereby complicating
ensuing inferences.

Scaling the arguments can induce a change in the divergence, as we would
expect.

  * Proposition A.4. For $\rho_{1},\rho_{2}\\!\in\\!\mathbb{R}_{+}$, and $\alpha\\!\in\\!\mathbb{R}_{+}\\!\backslash\\{1\\}$, $C_{\alpha}(\rho_{1}[\hat{\kappa}_{1}]\|\rho_{2}[\hat{\kappa}_{2}])\\!=\\!C_{\alpha}([\hat{\kappa}_{1}]\|[\hat{\kappa}_{2}])\\!+\\!\textnormal{log}(\rho_{1}/\rho_{2})$. The
same result hold in the mirrored case. It similarly holds in the tripartite
case for both square and non-square univariate Gram matrices.

Additivity. Additivity for tensor products is also well respected.

  * Proposition A.5. Let $[\hat{\kappa}_{3}],[\hat{\kappa}_{4}]\\!\in\\!\mathbb{R}_{0,+}^{n\times n}$, be normalized, univariate Gram matrices. We have that
$C_{\alpha}^{\prime}([\hat{\kappa}_{1}]\\!\otimes[\hat{\kappa}_{3}]\|[\hat{\kappa}_{2}]\otimes[\hat{\kappa}_{4}])\\!=\\!C_{\alpha}([\hat{\kappa}_{1}]\|[\hat{\kappa}_{2}])\\!+\\!C_{\alpha}([\hat{\kappa}_{3}]\|[\hat{\kappa}_{4}])$
with the additional constraint that
$\textnormal{supp}([\hat{\kappa}_{4}])\\!\subseteq\\!\textnormal{supp}([\hat{\kappa}_{3}])$.
The same result holds in the mirrored case. It does too for the tripartite
case for both square and non-square univariate Gram matrices.

This result can be extended to both finite and countable additivity.

Tensor summation of matrix arguments yields a generalized mean.

  * Proposition A.6. Let $[\hat{\kappa}_{3}],[\hat{\kappa}_{4}]\\!\in\\!\mathbb{R}_{0,+}^{n\times n}$, be univariate, normalized Gram matrices. There exists a continuous, strictly monotonic function $g$ where, for $\alpha\\!\in\\!\mathbb{R}_{+}\\!\backslash\\{1\\}$,

$C_{\alpha}([\hat{\kappa}_{1}]\oplus[\hat{\kappa}_{3}]\|[\hat{\kappa}_{2}]\oplus[\hat{\kappa}_{4}])\\!=\\!g^{-1}\Bigg{(}\frac{\textnormal{tr}([\hat{\kappa}_{1}])}{\textnormal{tr}([\hat{\kappa}_{1}]\\!+\\![\hat{\kappa}_{2}])}\Bigg{(}\\!g(C_{\alpha}([\hat{\kappa}_{1}]\|[\hat{\kappa}_{2}]))+g(C_{\alpha}([\hat{\kappa}_{3}]\|[\hat{\kappa}_{4}]))\\!\Bigg{)}\\!\\!\Bigg{)},$

with the additional constraint that
$\textnormal{supp}([\hat{\kappa}_{4}])\\!\subseteq\\!\textnormal{supp}([\hat{\kappa}_{3}])$.
The same result holds in the mirrored case. It does too for the tripartite
case for both square and non-square matrices.

Continuity. The matrix-based $\alpha$-cross-entropies are additionally
continuous in most instances.

  * Proposition A.7. We have that, for $[\hat{\kappa}_{1}]\\!\neq\\![0]_{n\times n}$, $C_{\alpha}([\hat{\kappa}_{1}]\|[\hat{\kappa}_{2}])$ is continuous in $[\hat{\kappa}_{1}],[\hat{\kappa}_{2}]$ for $\alpha\\!\in\\!\mathbb{R}_{+}\\!\backslash\\{1\\}$.
The same result holds for the tripartite case. It does too for the mirrored
case, except that
$\alpha\\!\in\\!\mathbb{R}_{\frac{1}{2},+}\\!\backslash\\{1\\}$.

Observe that the ordering of the operators is relevant for continuity for the
bipartite measures. Point discontinuities can arise due to a division by zero
if the operators are swapped and hence one of them does not satisfy the set-
ordering property.

As a consequence of continuity everywhere, the derivatives of the matrix-based
$\alpha$-cross-entropies can be shown to exist everywhere, for appropriate
parameter values.

Convexity and Concavity. We can also quantify the curvature of the
$\alpha$-cross-entropies.

  * Proposition A.8. Assume $[\hat{\kappa}_{1}]\\!\neq\\![\hat{\kappa}_{2}]$, we have that:

    * (i) The function $([\hat{\kappa}_{1}],[\hat{\kappa}_{2}])\\!\mapsto\\!\textnormal{tr}([\hat{\kappa}_{1}]^{\alpha}[\hat{\kappa}_{2}]^{1-\alpha})$ is jointly concave for $\alpha\\!\in\\!\mathbb{R}_{0,1}$ and jointly convex for
$\alpha\\!\in\\!\mathbb{R}_{1,2}\backslash\\{1\\}$. This implies that the non-
mirrored, matrix-based Rényi’s cross-entropy is both jointly
concave and convex, respectively, over the same parameter-value ranges.

    * (ii) The function $([\hat{\kappa}_{1}],[\hat{\kappa}_{2}])\\!\mapsto\\!(\textnormal{tr}([\hat{\kappa}_{2}]^{(1-\alpha)/2\alpha}[\hat{\kappa}_{1}][\hat{\kappa}_{2}]^{(1-\alpha)/2\alpha}))^{\alpha}$ is jointly concave for $\alpha\\!\in\\!\mathbb{R}_{\frac{1}{2},1}\backslash\\{1\\}$
and jointly convex for $\alpha\\!\in\\!\mathbb{R}_{1,+}\\!\backslash\\{1\\}$.
This implies that the mirrored, matrix-based Rényi’s cross-entropy is
both jointly concave and convex, respectively, over the same parameter-value
ranges.

    * (iii) The function $([\hat{\kappa}_{1}],[\hat{\kappa}_{1,2}],[\hat{\kappa}_{2}])\\!\mapsto\\!\mathbb{E}_{(s,s^{\prime})\sim p_{\mathcal{S}}}[[\hat{\kappa}_{1}]]\\!+\\!\mathbb{E}_{(a,a^{\prime})\sim p_{\mathcal{A}}}[[\hat{\kappa}_{2}]]\\!-\\!2\mathbb{E}_{(s,a)\sim\rho_{\mathcal{S}\times\mathcal{A}}}[[\hat{\kappa}_{1,2}]]$ is jointly
convex. As well, the function
$[\hat{\kappa}_{1}]\\!\mapsto\\!\textnormal{tr}([\hat{\kappa}_{1}]^{\alpha})$
is Schur-concave for $\alpha\\!\in\\!\mathbb{R}_{+}\\!\backslash\\{1\\}$. The
tripartite, matrix-based cross-entropy is thus jointly convex for
$\alpha\\!\in\\!\mathbb{R}_{+}\\!\backslash\\{1\\}$.

Data-Processing Inequality. We also obtain a data-processing inequality for
divergences. This inequality states that, for random variables forming a
Markov chain, processing the random variables cannot increase the matrix-based
Rényi’s cross-entropies. That is, any transformation within a particular class
cannot increase the distinguishability of the samples.

  * Proposition A.9. Let $\theta$ be a completely positive, trace-preserving map between two Hilbert spaces. We have that $C_{\alpha}([\hat{\kappa}_{1}]\|[\hat{\kappa}_{2}])\\!\geq\\!C_{\alpha}(\theta([\hat{\kappa}_{1}])\|\theta([\hat{\kappa}_{2}]))$ for $\alpha\\!\in\\!\mathbb{R}_{0,2}\backslash\\{0\\}$. Likewise, for the mirrored case, we have that
$C_{\alpha}^{\prime}([\hat{\kappa}_{1}]\|[\hat{\kappa}_{2}])\\!\geq\\!C_{\alpha}^{\prime}(\theta([\hat{\kappa}_{1}])\|\theta([\hat{\kappa}_{2}]))$
for $\alpha\\!\in\\!\mathbb{R}_{+}\\!\backslash[0,\frac{1}{2})$.

For the mirrored case, an additional parameter $\beta\\!\in\\!\mathbb{R}_{+}$
can be included in the cross-entropy expression to increase the coverage of
the data-processing inequality to
$\alpha\\!\in\\!\mathbb{R}_{0,+}\\!\backslash\\{1\\}$.

  * Proposition A.10. Let

$C^{\prime}_{\alpha,\beta}([\hat{\kappa}_{1}]\|[\hat{\kappa}_{2}])\\!=\\!\frac{1}{\alpha\\!-\\!1}\textnormal{log}\Bigg{(}\\!\textnormal{tr}\Bigg{(}\\![\hat{\kappa}_{2}]^{\frac{1-\alpha}{2\beta}}[\hat{\kappa}_{1}]^{\frac{\alpha}{\beta}}[\hat{\kappa}_{2}]^{\frac{1-\alpha}{2\beta}}\\!\Bigg{)}^{\\!\\!\beta}\,\Bigg{)}\\!-\\!\frac{1}{\alpha\\!-\\!1}\textnormal{log}\Bigg{(}\\!\textnormal{tr}(\kappa_{1})\\!\Bigg{)}.$

We have that
$C^{\prime}_{\alpha,\beta}([\hat{\kappa}_{1}]\|[\hat{\kappa}_{2}])\\!\geq\\!C^{\prime}_{\alpha,\beta}(\theta([\hat{\kappa}_{1}])\|\theta([\hat{\kappa}_{2}]))$
for (i) $\alpha\\!\in\\!\mathbb{R}_{0,1}\backslash\\{0,1\\}$ with
$\beta\\!\geq\\!\textnormal{max}(\alpha,1\\!-\\!\alpha)$,
(ii) $\alpha\\!\in\\!\mathbb{R}_{1,2}\backslash\\{1\\}$ with $\beta\\!=\\!1$
or $\beta\\!=\\!\alpha/2$, and (iii)
$\alpha\\!\in\\!\mathbb{R}_{1,+}\\!\backslash\\{1\\}$ with
$\beta\\!=\\!\alpha$.

Such a functional also satisfies many of the other properties listed in this
appendix and thus can be used in lieu of the mirrored matrix-based cross-
entropy.

Monotonicity. The matrix-based cross-entropies are monotonically increasing
with respect to $\alpha$, just as with the classical case. Such a property is
apparent from the general-mean property. That is, as $\alpha$ rises,
increasing preference is given to contributions with a high log-likelihood
ratio.

  * Proposition A.11. Assume that $[\hat{\kappa}_{1}]\\!\neq\\![0]_{n\times n}$, we have, for $\alpha\\!\in\\!\mathbb{R}_{+}\\!\backslash\\{1\\}$, that $C_{\alpha}([\hat{\kappa}_{1}]\|[\hat{\kappa}_{2}])$, $C_{\alpha}^{\prime}([\hat{\kappa}_{1}]\|[\hat{\kappa}_{2}])$, and $C_{\alpha}^{\prime\prime}([\hat{\kappa}_{1}]\|[\hat{\kappa}_{1,2}]\|[\hat{\kappa}_{2}])$ are monotonically increasing in $\alpha$.

Monotonicity occurs regardless of if the operators are commutative or non-
commutative. The latter is important for practical situations, as the Gram
matrices will not always be simultaneously diagonalizable.

Induced Entropies. The matrix-based cross-entropies can be seen as a parent
quantity to corresponding matrix-based Rényi’s entropies,
$S_{\alpha}([\hat{\kappa}_{1}])\\!=\\!\textnormal{log}(\textnormal{tr}([\hat{\kappa}_{1}])^{\alpha})/(\alpha\\!-\\!1)$,
that our lab introduced [9]. Our matrix-based Rényi’s
entropies were proven to satisfy standard properties of classical Rényi
$\alpha$-entropies.

  * Proposition A.12. For $\alpha\\!\in\\!\mathbb{R}_{+}\\!\backslash\\{1\\}$, we have that $S_{\alpha}([\hat{\kappa}_{1}])$ is equal to $C_{\alpha}([\hat{\kappa}_{1}]\|\textnormal{id}_{n\times n})$ and $C_{\alpha,1}^{\prime}([\hat{\kappa}_{1}]\|\textnormal{id}_{n\times n})$, where $\textnormal{id}_{n\times n}$ is the identity matrix. Moreover, it is equal to $C_{\alpha}^{\prime\prime}([\hat{\kappa}_{1}]\|[0]_{n\times n}\|[\hat{\kappa}_{1}])$.

This result does not extend to the mirrored cross-entropy for the case of a
single-parameter.

We can view either divergence as a distance measure. The corresponding matrix-
based Rényi’s entropy can thus be understood as
$S_{\alpha}([\hat{\kappa}_{1}])\\!=\\!\textnormal{log}(n)\\!-\\!C_{\alpha}([\hat{\kappa}_{1}]\|\textnormal{id}_{n\times
n}/n)$, that is, the difference between the maximal possible entropy and how
far away the Gram matrix is from the normalized identity matrix.

The set of positive semi-definite matrices, which includes Gram matrices, is
closed under the Hadamard product. This property can be employed to extend the
matrix-based divergences from a single-variable entropy to a joint-entropy
representation that is given by
$S_{\alpha}([\hat{\kappa}_{1}],[\hat{\kappa}_{2}])\\!=\\!S_{\alpha}([\hat{\kappa}_{1}]\circ[\hat{\kappa}_{2}]/\textnormal{tr}([\hat{\kappa}_{1}]\circ[\hat{\kappa}_{2}]))$.

  * Proposition A.13. Let $\alpha\\!\in\\!\mathbb{R}_{+}\\!\backslash\\{1\\}$. We have that $S_{\alpha}([\hat{\kappa}_{1}],[\hat{\kappa}_{2}])\\!=\\!\textnormal{log}(n)\\!-\\!C_{\alpha}([\hat{\kappa}_{1}]\circ[\hat{\kappa}_{2}]\|[\hat{\kappa}_{2}]\textnormal{id}_{n\times n})\hskip 0.42677pt+$
$C_{\alpha}([\hat{\kappa}_{1}]\|\textnormal{id}_{n\times n})$. Similar results
hold in the two-parameter non-mirrored case. Likewise, only for univariate
Gram matrices that are square,
$S_{\alpha}([\hat{\kappa}_{1}],[\hat{\kappa}_{2}])\\!=\\!C_{\alpha}^{\prime\prime}([\hat{\kappa}_{1}]\circ[\hat{\kappa}_{2}]/\textnormal{tr}([\hat{\kappa}_{1}]\circ[\hat{\kappa}_{1}])\|[0]_{n\times
n}\|[\hat{\kappa}_{1}]\circ[\hat{\kappa}_{2}]/\textnormal{tr}([\hat{\kappa}_{1}]\circ[\hat{\kappa}_{1}]))$.

We can interpret the Hadamard product as computing a product kernel. It is
specifying a measure of entropy of a random element defined by a pair of
random variables.

We can also use this divergence to specify a matrix-based conditional entropy.
There is, however, no general consensus for a definition of a Rényi
conditional $\alpha$-entropy. Here, we take inspiration from Shannon’s
definition and consider a version,
$S_{\alpha}(\kappa_{1}|\kappa_{2})\\!=\\!S_{\alpha}(\kappa_{1},\kappa_{2})\\!-\\!S_{\alpha}(\kappa_{2})$,
that specifies the uncertainty about one random variable after observing
another and taking into account the joint entropy.

  * Proposition A.14. Let $\alpha\\!\in\\!\mathbb{R}_{+}\\!\backslash\\{1\\}$. We have that $S_{\alpha}([\hat{\kappa}_{1}]|[\hat{\kappa}_{2}])\\!=\\!\textnormal{log}(n)\\!-\\!C_{\alpha}([\hat{\kappa}_{1}]\circ[\hat{\kappa}_{2}]\|[\hat{\kappa}_{2}]\textnormal{id}_{n\times n})\hskip 0.56917pt+$
$C_{\alpha}([\hat{\kappa}_{1}]\|\textnormal{id}_{n\times
n})\\!-\\!C_{\alpha}([\hat{\kappa}_{2}]\|\textnormal{id}_{n\times n})$.
Similar results hold in the two-parameter mirrored and tripartite cases.
For the tripartite measure, the univariate Gram matrices must be square.

Likewise, we can define a matrix-based Rényi’s $\alpha$-mutual-information, as
in [9], using the notions of the matrix-based Rényi’s $\alpha$-marginal and
$\alpha$-conditional entropies.

Both the matrix-based joint and conditional $\alpha$-entropies derived from
our matrix-based $\alpha$-cross-entropies can be extended to arbitrary numbers
of matrices [10]. The matrix-based Rényi’s $\alpha$-mutual-information can
too, as a consequence.

## A.2. Matrix-based Rényi’s $\alpha$-Divergence Bounds

It can be shown that the unit-$\alpha$ case of the bipartite, mirrored
$\alpha$-cross-entropy is related to a Umegaki relative entropy with an
additional weighting factor.

  * Proposition A.15. We have that

$\textnormal{lim}_{\alpha\to
1}C^{\prime}_{\alpha}([\hat{\kappa}_{1}]\|[\hat{\kappa}_{2}])\\!=\\!\frac{1}{\textnormal{tr}([\hat{\kappa}_{1}])}\textnormal{tr}\Bigg{(}\\![\hat{\kappa}_{1}](\textnormal{log}([\hat{\kappa}_{1}])\\!-\\!\textnormal{log}([\hat{\kappa}_{2}]))\\!\Bigg{)},$

and $C^{\prime}_{1}([\hat{\kappa}_{1}]\|[\hat{\kappa}_{2}])\\!=\\!\infty$
otherwise.

This link permits establishing an upper bound in terms of the trace distance.
We can also obtain a tighter bound via spectral properties of the univariate
Gram matrices.

  * Proposition A.16. We have that

    * (i) Trace-distance bound: Let $\lambda_{\kappa_{1}}\\!\\!\in\\!\mathbb{R}_{+}$ and $\lambda_{\kappa_{2}}\\!\\!\in\\!\mathbb{R}_{+}$ be the minimal non-zero eigenvalues of the kernel matrices $[\hat{\kappa}_{1}]$ and $[\hat{\kappa}_{2}]$, respectively. Let $\alpha\\!\to\\!1$, then

$\textnormal{tr}\Bigg{(}\\![\hat{\kappa}_{1}](\textnormal{log}([\hat{\kappa}_{1}])\\!-\\!\textnormal{log}([\hat{\kappa}_{2}]))\\!\Bigg{)}\\!\leq\\!\Bigg{(}\\!(\lambda_{\kappa_{2}}\\!+\\!\omega_{\kappa_{1},\kappa_{2}}/2)\textnormal{log}(1\\!+\\!\omega_{\kappa_{1},\kappa_{2}}/2\lambda_{\kappa_{2}})\\!-\\!\lambda_{\kappa_{1}}\textnormal{log}(1\\!+\\!\omega_{\kappa_{1},\kappa_{2}}/2\lambda_{\kappa_{1}})\\!\Bigg{)},$

where $\omega_{\kappa_{1},\kappa_{2}}\\!\in\\!\mathbb{R}_{0,+}$ is the
$\ell_{1}$-matrix-distance between $[\hat{\kappa}_{1}]$ and
$[\hat{\kappa}_{2}]$.

    * (ii) Tighter trace-distance bound: Let $\lambda_{\kappa_{1}}\\!\\!\in\\!\mathbb{R}_{+}$ and $\lambda_{\kappa_{2}}\\!\\!\in\\!\mathbb{R}_{+}$ be the minimal non-zero eigenvalues of the Gram matrices $[\hat{\kappa}_{1}]$ and $[\hat{\kappa}_{2}]$, respectively. Let $\lambda_{\kappa_{1}}^{+}\\!\\!\in\\!\mathbb{R}_{+}$ be the largest eigenvalue of $[\hat{\kappa}_{1}]$. Let $\alpha\\!\to\\!1$, then

$\textnormal{tr}\Bigg{(}\\![\hat{\kappa}_{1}](\textnormal{log}([\hat{\kappa}_{1}])\\!-\\!\textnormal{log}([\hat{\kappa}_{2}]))\\!\Bigg{)}\\!\leq\\!\Bigg{(}\frac{\omega_{\kappa_{1},\kappa_{2}}\lambda_{\kappa_{1}}^{+}}{\lambda_{\kappa_{1}}\\!-\\!\lambda_{\kappa_{2}}}(\textnormal{log}(\lambda_{\kappa_{1}})\\!-\\!\textnormal{log}(\lambda_{\kappa_{2}}))\Bigg{)},$

which is non-strictly bounded above by
$\lambda_{\kappa_{1}}^{+}\omega_{\kappa_{1},\kappa_{2}}/\textnormal{min}(\lambda_{\kappa_{1}},\lambda_{\kappa_{2}})$.

These inequalities provide easy tests of the maximal cross-entropies that will
be encountered when coupled with spectral-radius bounds.

Both bipartite matrix-based Rényi’s cross-entropies can be related to each
other. From the Araki-Lieb-Thirring inequality, we have that
$\textnormal{tr}([\hat{\kappa}_{1}]^{\alpha}[\hat{\kappa}_{2}]^{\alpha}[\hat{\kappa}_{1}]^{\alpha})\\!\leq\\!\textnormal{tr}([\hat{\kappa}_{1}][\hat{\kappa}_{2}][\hat{\kappa}_{1}])^{\alpha}$
and
$\textnormal{tr}([\hat{\kappa}_{1}][\hat{\kappa}_{2}][\hat{\kappa}_{1}])^{\alpha}\\!\leq\\!(\|[\hat{\kappa}_{2}]\|^{\alpha}\textnormal{tr}([\hat{\kappa}_{1}]^{2\alpha}))^{1-\alpha}$,
for $\alpha\\!\in\\!\mathbb{R}_{0,1}\\!\backslash\\{0,1\\}$. These
inequalities hold in the opposite direction for
$\alpha\\!\in\\!\mathbb{R}_{1,+}\\!\backslash\\{1\\}$. Thus,

$\textnormal{tr}([\hat{\kappa}_{1}]^{\alpha}[\hat{\kappa}_{2}]^{1-\alpha})\leq\|[\hat{\kappa}_{2}]\|^{(1-\alpha)^{2}}\Bigg{(}\\!(\textnormal{tr}([\hat{\kappa}_{1}]^{\alpha}))^{1-\alpha}(\textnormal{tr}([\hat{\kappa}_{1}]^{\alpha}[\hat{\kappa}_{2}]^{1-\alpha}))^{\alpha}\\!\Bigg{)},$

which gives rise to the following claim.

  * Proposition A.17. For $\alpha\\!\in\\!\mathbb{R}_{+}\\!\backslash\\{1\\}$, $C_{\alpha}([\hat{\kappa}_{1}]\|[\hat{\kappa}_{2}])\\!\geq\\!C_{\alpha}^{\prime}([\hat{\kappa}_{1}]\|[\hat{\kappa}_{2}])$.

From this, we can see that the magnitudes from the mirrored Rényi’s
$\alpha$-cross-entropy may be more conservative than those from the non-
mirrored version.

## Appendix B

Symbol |  Description
---|---
$\mathbb{E}$ |  Expected value
$\mathbb{R}$ |  Real numbers
$\mathbb{R}_{+}$ |  Positive real numbers
$\mathbb{R}_{0,+}$ |  Non-negative real numbers
$\mathbb{R}_{a,b}$ |  Real numbers in the range $[a,b]$
$\mathbb{R}_{a,b}\backslash\\{c\\}$ |  Real numbers in the range $[a,b]$ excluding the set $c$
$\mathbb{N}_{a,b}$ |  Natural numbers in the range $[a,b]$
$\mathbb{L}_{2}$ |  Square-integrable functions
$\mathcal{S},\mathcal{A}$ |  Topological sample spaces
$\mathcal{M}_{+}^{1}(\mathcal{S})$ |  Space of probability measures on $\mathcal{S}$
$\mathcal{M}_{+}^{1}(\mathcal{S}\\!\times\\!\mathcal{A})$ |  Space of probability measures on $\mathcal{S}\\!\times\\!\mathcal{A}$
$\mathcal{H}_{\kappa^{\prime}}$ |  Reproducing-kernel Hilbert space for $\kappa^{\prime}$
$\mathcal{H}_{\kappa_{1}^{\prime}},\mathcal{H}_{\kappa_{2}^{\prime}}$ |  Reproducing-kernel Hilbert spaces for $\kappa_{1}^{\prime},\kappa_{2}^{\prime}$
$\mathcal{H}_{\kappa_{1}^{\prime}}\\!\otimes\\!\mathcal{H}_{\kappa_{2}^{\prime}}$ |  Tensor-product reproducing-kernel Hilbert space
$\kappa^{\prime},\kappa_{1}^{\prime},\kappa_{2}^{\prime}$ |  Reproducing kernels
$p_{\mathcal{S}},q_{\mathcal{S}},p_{\mathcal{A}}$ |  Marginal probability measures
$\rho_{\mathcal{S}\times\mathcal{A}}$ |  Joint probability measure
$\varphi,\psi$ |  Measurable functions
$\varphi^{\otimes}$ |  Measurable function for tensor-product spaces
$\mu_{p_{\mathcal{S}}}$ |  Univariate mean element
$\mu_{\rho_{\mathcal{S}\times\mathcal{A}}}$ |  Bivariate mean element
$s,s^{\prime},a,a^{\prime}$ |  Topological-space elements
$f,g$ |  Hilbert-space functions
$h,r$ |  Hilbert-space dimensionality
$\eta_{j},\vartheta_{k}$ |  Basis component for $\mathcal{H}_{\kappa^{\prime}_{1}},\mathcal{H}_{\kappa^{\prime}_{2}}$
$\pi_{q}$ |  Basis component for $\mathcal{H}_{\kappa^{\prime}_{1}}\\!\otimes\\!\mathcal{H}_{\kappa^{\prime}_{2}}$
$\kappa,\kappa_{1},\kappa_{2}$ |  Univariate Gram operators
$\hat{\kappa},\hat{\kappa}_{1},\hat{\kappa}_{2}$ |  Approximate univariate Gram operators
$[\hat{\kappa}],[\hat{\kappa}_{1}],[\hat{\kappa}_{2}]$ |  Univariate Gram matrices
$\gamma$ |  Bivariate Gram operator
$\hat{\gamma}$ |  Approximate bivariate Gram operator
$[\hat{\gamma}]$ |  Bivariate Gram matrix
$\lambda$ |  Joint, bivariate Gram operator
$\hat{\lambda}$ |  Approximate joint, bivariate Gram operator
$[\hat{\lambda}],[\hat{\kappa}_{1,2}]$ |  Joint, bivariate Gram matrices
$\mathcal{K}$ |  Multilinear form specified by $\kappa$
$\mathcal{G}$ |  Multilinear form specified by $\gamma$
$\mathcal{L}$ |  Multilinear form specified by $\lambda$
$\tau_{i}$ |  Gram operator eigenvalue
$\beta_{i}$ |  Gram operator eigenvector
$\theta$ |  Completely positive, trace-preserving mapping
$n,m$ |  Number of samples
$i,j,k,q$ |  Indexes
$c_{1},c_{2},c_{3},c_{4},c_{5}$ |  Real-valued constants
$\textnormal{supp}(\kappa)$ |  Support of $\kappa$
$\textnormal{tr}(\cdot)$ |  Trace
$\langle\cdot,\cdot\rangle_{\mathcal{H}_{\kappa^{\prime}}}$ |  Inner product for $\mathcal{H}_{\kappa^{\prime}}$
$\|\cdot\|_{\mathcal{H}_{\kappa^{\prime}}}$ |  Norm for $\mathcal{H}_{\kappa^{\prime}}$
$H_{\alpha}(\cdot\|\cdot)$ |  Rényi’s $\alpha$-order cross-entropy
$C_{\alpha}(\cdot\|\cdot)$ |  Bipartite, non-mirrored Rényi’s $\alpha$-order cross-entropy
$C_{\alpha}^{\prime}(\cdot\|\cdot)$ |  Bipartite, mirrored Rényi’s $\alpha$-order cross-entropy
$C_{\alpha,\beta}^{\prime}(\cdot\|\cdot)$ |  Bipartite, mirrored Rényi’s $\alpha$-$\beta$-order cross-entropy
$C_{\alpha}^{\prime\prime}(\cdot\|\cdot\|\cdot)$ |  Tripartite Rényi’s $\alpha$-order cross-entropy


# Three-dimensional matching is NP-Hard

Shrinu Kushagra111Email<EMAIL_ADDRESS>The results in this note first
appeared in [Kushagra et al., 2019] where the reduction was used to prove
query lower bounds for a clustering problem.

###### Abstract

The standard proof of NP-Hardness of 3DM provides a power-$4$ reduction of
3SAT to 3DM. In this note, we provide a linear-time reduction. Under the
exponential time hypothesis, this reduction improves the runtime lower bound
from $2^{o(\sqrt[4]{m})}$ (under the standard reduction) to $2^{o(m)}$.

Keywords: 3DM, 3SAT, ETH, X3C, NP-Hard

##  1 Introduction

In this note, we first establish the hardness of the following decision
problem.

######  Definition 1 (3DM).

.

Input: Sets $W,X$ and $Y$ and a set of matches $M\subseteq W\times X\times Y$
of size $m$.

Output: YES if there exists $M^{\prime}\subseteq M$ such that each element of
$W,X,Y$ appears exactly once in $M^{\prime}$. NO otherwise.

To prove that 3DM is NP-Hard, we reduce an instance of 3SAT to the given
problem. Next, we define the 3SAT decision problem.

######  Definition 2 (3-SAT).

.

Input: A boolean formulae $\phi$ in 3CNF form with $n$ literals and $m$
clauses.

Output: YES if $\phi$ is satisfiable, NO otherwise.

Given an instance of 3SAT with $n$ literals and $m$ clauses, [Garey and
Johnson, 1979] construct a graph with $\Theta(nm)$ vertices and
$\Theta(n^{2}m^{2})$ edges. Thus, this is a power-$4$ reduction. In this note,
we use a similar but a more efficient gadget and provide a linear time
reduction of the 3SAT instance to the given problem.

##  2 Hardness of 3DM

######  Theorem 3.

Three-dimensional matching is an NP-Hard problem.

Figure 1: Part of graph $G$ constructed for the literal $x_{1}$. The figure is
an illustration for when $x_{1}$ is part of four different clauses. The
triangles (or hyper-edge) $(a_{i},b_{i},c_{i})$ capture the case when $x_{1}$
is true and the other triangle $(b_{i},c_{i}^{\prime},a_{i+1})$ captures the
case when $x_{1}$ is false. Assuming that a clause
$C_{j}=\\{x_{1},x_{2},x_{3}\\}$, the hyper-edges containing
$tf_{i},tf_{i}^{\prime}$ and $t_{1},t_{1}^{\prime}$ capture different
settings. The hyper-edges containing $t_{1},t_{1}^{\prime}$ ensure that
atleast one of the literals in the clause is true. The other two ensure that
two variables can take either true or false values.

Our reduction is described in Fig. 1. For each literal $x_{i}$, let $m_{i}$ be
the number of clauses in which the the literal is present. We construct a
“truth-setting” component containing $2m_{i}$ hyper-edges (or triangles). We
add the following hyper-edges to $M$.

$\displaystyle\\{(a_{k}[i],b_{k}[i],c_{k}[i]):1\leq k\leq m_{i}\\}$
$\displaystyle\cup\\{(a_{k+1}[i],b_{k}[i],c_{k}^{\prime}[i]):1\leq k\leq
m_{i}\\}$

Note that one of $(a_{k},b_{k},c_{k})$ or $(a_{k+1},b_{k},c_{k}^{\prime})$
have to be selected in a matching $M^{\prime}$. If the former is selected,
that corresponds to the variable $x_{i}$ being assigned true, the latter
corresponds to false. This part is the same as the standard construction.

For every clause $C_{j}=\\{x_{1},x_{2},x_{3}\\}$ we add three types of hyper-
edges. The first type ensures that atleast one of the literals is true.

$\\{(c_{k}[i],t_{1}[j],t_{1}^{\prime}[j]):x_{i}^{\prime}\in
C_{j}\\}\cup\\{(c_{k}^{\prime}[i],t_{1}[j],t_{1}^{\prime}[j]):x_{i}\in
C_{j}\\}$

The other two types of hyper-edges (conected to the $tf_{i}$’s) say that two
of the literals can be either true or false. Hence, we connect them to both
$c_{k}$ and $c_{k}^{\prime}$

$\displaystyle\\{(c_{k}[i],tf_{1}[j],tf_{1}^{\prime}[j]):x_{i}^{\prime}\text{
or }x_{i}\in C_{j}\\}$
$\displaystyle\cup\\{(c_{k}[i],tf_{2}[j],tf_{2}^{\prime}[j]):x_{i}\text{ or
}x_{i}^{\prime}\in C_{j}\\}$
$\displaystyle\cup\\{(c_{k}^{\prime}[i],tf_{1}[j],tf_{1}^{\prime}[j]):x_{i}^{\prime}\text{
or }x_{i}\in C_{j}\\}$
$\displaystyle\cup\\{(c_{k}^{\prime}[i],tf_{2}[j],tf_{2}^{\prime}[j]):x_{i}\text{
or }x_{i}^{\prime}\in C_{j}\\}$

Note that in the construction $k$ refers to the index of the clause $C_{j}$ in
the truth-setting component corresponding to the literal $x_{i}$. Using the
above construction, we get that

$\displaystyle W=\\{c_{k}[i],c_{k}^{\prime}[i]\\}$ $\displaystyle
X=\\{a_{k}[i]\\}\cup\\{t_{1}[j],tf_{1}[j],tf_{2}[j]\\}$ $\displaystyle
Y=\\{b_{k}[i]\\}\cup\\{t_{1}^{\prime}[j],tf_{1}^{\prime}[j],tf_{2}^{\prime}[j]\\}$

Hence, we see that $|W|=2\sum_{i}m_{i}=6m$. Now,
$|X|=|Y|=\sum_{i}m_{i}+3m=6m$. And, we have that $|M|=2\sum_{i}m_{i}+15m=21m$.
Thus, we see that this construction is linear in the number of clauses.

Now, if the 3-SAT formula $\phi$ is satisfiable then there exists a matching
$M^{\prime}$ for the 3DM problem. If a variable $x_{i}=T$ in the assignment
then add $(c_{k}[i],a_{k}[i],b_{k}[i])$ to $M^{\prime}$ else add
$(c_{k}^{\prime}[i],a_{k+1}[i],b_{k}[i])$. For every clause $C_{j}$, let
$x_{i}$ (or $x_{i}^{\prime}$) be the variable which is set to true in that
clause. Add $(c_{k}^{\prime}[i],t_{1}[j],t_{1}^{\prime}[j])$ (or
$(c_{k}[i],t_{1}[j],t_{1}^{\prime}[j])$) to $M^{\prime}$. For the remaining
two clauses, add the hyper-edges containing $tf_{1}[j]$ and $tf_{2}[j]$
depending upon their assignments. Clearly, $M^{\prime}$ is a matching.

Now, the proof for the other direction is similar. If there exists a matching,
then one of $(a_{k},b_{k},c_{k})$ or $(a_{k+1},b_{k},c_{k}^{\prime})$ have to
be selected in a matching $M^{\prime}$. This defines a truth assignment of the
variables. Now, the construction of the clause hyper-edges ensures that every
clause is satisfiable.

##  3 Exponential Time Hypothesis for 3DM

Before we start the discussion in the section, lets review the definition of
the exponential time hypothesis.

Exponential Time Hypothesis (ETH)
There does not exist an algorithm which decides 3-SAT and runs in $2^{o(m)}$
time.

If the exponential hypothesis is true, the standard reduction of 3-SAT to 3DM
[Garey and Johnson, 1979] implies that any algorithm for 3DM runs in
$2^{o(m^{1/4})}$. However, using the reduction in Section 2, we get a more
tighter dependence on $m$ stated as a theorem below.

######  Theorem 4.

If the exponential time hypothesis holds then there does not exist an
algorithm which decides the three-dimensional matching problem (3DM) and runs
in time $2^{o(m)}$.

###### Proof.

For the sake on contradiction, suppose that such an algorithm $\mathcal{A}$
exists. Then, using the reduction from Section 2 and $\mathcal{A}$, we get an
algorithm for 3SAT that runs in $2^{o(m)}$ time which contradicts the ET
hypothesis. ∎

An immediate corollary of this result applies to another popular problem Exact
Cover by 3-sets.

######  Definition 5 (X3C).

.

Input: $U=\\{x_{1},\ldots,x_{3q}\\}$. A collections of subsets
$S=\\{S_{1},\ldots,S_{m}\\}$ such that each $S_{i}\subset U$ and contains
exactly three elements.

Output: YES if there exist $S^{\prime}\subseteq S$ such that each element of
$U$ occurs exactly once in $S^{\prime}$, NO otherwise.

######  Corollary 6.

If the exponential time hypothesis holds then there does not exist an
algorithm which decides exact cover by 3-sets problem (X3C) and runs in time
$2^{o(m)}$.

###### Proof.

The proof follows from the trivial reduction of 3DM to X3C where $U=W\cup
X\cup Y$ and $S=M$. ∎

## References

  * [Garey and Johnson, 1979] Garey, M. R. and Johnson, D. S. (1979).  Computers and intractability, volume 174.  freeman San Francisco.
  * [Kushagra et al., 2019] Kushagra, S., Ben-David, S., and Ilyas, I. F. (2019).  Semi-supervised clustering for de-duplication.  In The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019, 16-18 April 2019, Naha, Okinawa, Japan, pages 1659–1667.


# To Infinity and Beyond! Accessibility is the Future for Kid’ Search Engines

Ashlee Milton<EMAIL_ADDRESS>PIReT - Dept. of Computer
Science, Boise State UniversityBoiseUSA83725 ,  Garrett Allen
<EMAIL_ADDRESS>PIReT - Dept. of Computer Science, Boise State
UniversityBoiseUSA83725 and  Maria Soledad Pera  0000-0002-2008-9204
<EMAIL_ADDRESS>PIReT - Dept. of Computer Science, Boise State
UniversityBoiseUSA83725

(2021)

###### Abstract.

Research in the area of search engines for children remains in its infancy.
Seminal works have studied how children use mainstream search engines, as well
as how to design and evaluate custom search engines explicitly for children.
These works, however, tend to take a one-size-fits-all view, treating children
as a unit. Nevertheless, even at the same age, children are known to possess
and exhibit different capabilities. These differences affect how children
access and use search engines. To better serve children, in this vision paper,
we spotlight accessibility and discuss why current research on children and
search engines does not, but should, focus on this significant matter.

children, information retrieval, accessibility, personalization

††copyright: iw3c2w3††journalyear: 2021††conference: IR for Children
2000-2020: Where Are We Now? – Workshop co-located with the 44th International
ACM SIGIR Conference on Research and Development in Information Retrieval;
July 15, 2021; Online Event††ccs: Social and professional topics
Children††ccs: Human-centered computing Accessibility††ccs: Information
systems Web searching and information discovery

##  1\. ”You got a play-date with destiny!”: Foundation

A wide range of users regularly turn to search engines in varying settings,
e.g., work, home, and school (Haider and Sundin, 2019; pew, 2021; Sentance,
[n.d.]; Chaffey, 2021). For decades, the Information Retrieval (IR) community
has introduced algorithmic solutions to improve and expand the performance of
search engines; it has also studied the people who utilize them. The bulk of
existing research works respond to the requirements of “general” users who
are, for the most part, adult searchers. We could, however, name other “non-
traditional” user groups, e.g., expert searchers, searchers for whom English
is not their first language, and children111Here, whenever we state children
we refer to any person under the age of 18, as per UNICEF’s Convention on the
Rights of the Child (Unicef et al., 1989) who have unique needs and
expectations when using search engines., who routinely use search engines, but
struggle to best take advantage of them as they are not designed with non-
traditional searchers in mind. Children, in particular, have specialized
cognitive and physical requirements when it comes to information seeking using
search engines (Bilal, 2010). With children making up almost a quarter of the
population and being heavily reliant on search engines to satisfy their
information needs (Rowlands et al., 2008), we scope our discussion to
encompass search engines and children.

From a preliminary literature review on Google Scholar and the ACM Digital
Library using queries including “web search children” and “search engine
children,” it emerges that research about children and search engines started
in the late 1990s. To our knowledge, the earliest publications include those
by Dania Bilal (Bilal, 1998, 1999), who aimed to understand how children
interact with search engines specifically designed for them, as well as Martyn
Wild (1996), who studied how children use the Internet for information
seeking. These contributions provided the groundwork for future research
looking into (i) how children use search engines, (ii) modifying search
engines algorithmically for children, and (iii) the design of search engines
tailored to children (Gossen, 2016; Danovitch, 2019). Thus far, promising
research in this area has probed each stage of the information seeking
process. Given that children struggle with query formulation, it is not
unexpected to see projects studying how children express their information
needs in the form of queries or introducing new strategies to ease the burden
of query formulation (Bilal and Gwizdka, 2018; Gupta and Hilal, 2013;
Vanderschantz and Hinze, 2017b). Query suggestions could, to a degree,
facilitate the task of identifying effective queries to initiate the search
process. Oftentimes, however, suggested queries are the result of query-log-
based strategies which are heavily influenced by searches conducted on search
engines by general users. To address this limitation, researchers have
produced query suggestion strategies that are more appealing to children and
that best respond to their search intent (Madrazo Azpiazu et al., 2018;
Dragovic et al., 2016; Shaikh et al., 2015). When looking at results retrieved
in response to children’s queries, Anuyah et al. (2019) and Bilal and Huang
(2019) investigate the reading level of SERP and whether they align with a
child’s reading level. When considering the relevance of retrieved resources,
children tend to explore search engine result pages (SERP) sequentially, i.e.,
from top to bottom (Gwizdka and Bilal, 2017; Landoni et al., 2019), as opposed
to deciding relevance through scanning SERP snippets and clicking on a given
result. This prompted researchers to investigate ways to both filter and re-
rank resources so that those more relevant and suitable for children make
their way to the top of the SERP (Eickhoff et al., 2010; Vanderschantz and
Hinze, 2017a; Patel and Singh, 2016; Milton et al., 2020; Bilal and Boehm,
2017; Figueiredo and Meyers, 2019; Collins-Thompson et al., 2011). From the
standpoint of how children use search engines, Foss et al. (2012) as well as
Duarte Torres and Weber (2011) study children’s interactions at different
stages of the information seeking process.

The literature that we have discussed has been pivotal to the advancement of
IR regarding children and search engines. Yet, research has been sporadic
throughout the last two decades and limited to few research groups. We
attribute the inconsistent nature of this type of research to issues related
to obtaining children’s data and the ability to freely share benchmarks as
well as labeled data to inform development and evaluation, which other domains
do not have with as datasets are fallible, e.g., CLEF, TREC, etc. More
importantly, these scholarly works focus on children in specific age ranges,
e.g., 8 to 11 year-olds or adolescents. This is a concern as (i) children in
these user groups do not exhibit uniform (search) behavior, and (ii) the full
spectrum of requirements and expectations of children (18 and under) has been
overlooked. Given the exigency of supporting children’s search, a one-size-
fits-all solution is not adequate. Instead, various lenses that take into
consideration the different skills children possess should be pursued when
altering or designing search systems. In this paper, we spotlight the
accessibility lens. Explicitly, we discuss the demand for making search
engines more accessible for children of different mental, physical, and
learning/developmental abilities.

##  2\. ”We got to get this wagon train a-movin’!”: Gaps

The call to create accessible search engines is not a new idea (Serdyukov et
al., 2011; Kerkmann and Lewandowski, 2012). IR researchers have allocated
efforts to explore how adult searchers affected by dyslexia deal with search
engines (Fourney et al., 2018), the information-seeking process of adults with
invisible disabilities (Muir et al., 2019), and how to best adapt search
engines to searchers who are vision-impaired (Vtyurina, 2019; Vtyurina et al.,
2019). Unfortunately, substantial progress has yet to be made by the IR
community regarding accessibility for children–the population currently under
study–beyond some preliminary investigations like autism (Young et al., 2016).
To highlight some opportunities for adapting search engines to support
children with disabilities, we provide some motivating examples showcasing the
necessity to dedicate scholarly efforts to holistically look at children,
search engines, and accessibility.

Query formulation. Downs et al. (2020) present a specialized spellchecker
(KidSpell) tailored explicitly to children to help with query formulation, as
there are trends in how children misspell words that differ from those
observed among adults. We posit, however, that KidSpell would not necessarily
work for children with dyslexia, who are prone to make different types of
misspellings (Li et al., 2013; Kvikne and Berget, 2019). Additionally,
KidSpell incorporates a visual and audio component that may adversely impact
users with autism by unintentionally inducing sensory overload (Mikropoulos et
al., 2020).

Query suggestions. Madrazo Azpiazu et al. (2018) introduce ReQuIK, a query
suggestion strategy for children ages 8 to 11 that infers children’s intent
from their original queries. ReQuIK, which conventionally displays
suggestions, may not be applicable for children who are vision impaired.
Vision hurdles could indeed be bypassed by relying on conversational voice
search, which Lovato et al. (2019) explore, but this too comes with
accessibility gaps. For a conversational voice search to be effective, it must
understand the verbal input provided by users, which is difficult in the case
of children in general (Gossen, 2016; Gossen et al., 2013; Shivakumar and
Georgiou, 2020; Fainberg et al., 2016; Yarosh et al., 2018; Cheng et al.,
2018), but is further exacerbated when children have speech impediments or
disorders like Tourette syndrome.

Ranking. Milton et al. (2020) and Usta et al. (2021) propose new ranking
algorithms to prioritize retrieved results that are relevant to educational
contexts. Both rankers depend upon a user’s age, which is mapped to a
respective school grade and then used to identify online resources that align
with the educational curriculum outlined for a said grade. By assuming that a
child’s age directly matches with their developmental stage or reading
ability, the rankers cannot account for children that have disabilities like
autism or dyslexia.

Interactions. Landoni et al. (2021) investigate whether adding visual cues to
SERP displays to provide clues for resource relevance eases the process of
locating resources addressing children’s information needs. Aside from the
visual issues that we have already discussed, the authors utilize a
traditional SERP which can be difficult to navigate for young children who
lack fine motor skills (Gossen, 2016). When considering children with more
extreme physical disabilities, like missing limbs, cerebral palsy, or muscular
dystrophy, it becomes almost impossible to employ standard keyboards and
mouses to interact with SERP.

SERP. Landoni et al. (2020) explore the emotional responses captured in SERP
generated by children searching for classroom-related materials. The authors
point out that during their user study, teachers observed emotional responses
evoked in child participants by search results. The ethical nature of whether
distressing search tasks are suitable for children on an emotional level is
also brought up. This concern is escalated when considering children with
mental health disorders, particularly those with bipolar, depressive, anxiety,
attention deficit (ADD/ADHD), or post-traumatic stress disorders.
Additionally, research strategies that leverage the emotions of children must
also consider that some of them may not have an adequate emotional maturity
level or ability to feel emotions, which is a symptom of antisocial
personality disorder, psychopathy, or sociopathy.

The examples we have discussed neither in any way represent an exhaustive list
of all known disabilities that impact children nor the open problems related
to the accessibility of search engines. Instead, they are meant to offer a
glimpse of how existing research is underserving children with disabilities
and their potential use of search engines.

##  3\. ”Well, then, let’s find out together!”: Future

Even from the few examples we have drawn attention to in Section 2, it is
clear that there are plenty of research gaps that emerge when considering the
complex problem of accessibility. Indeed, living up to the requirements and
expectations of how children with disabilities use search engines and how
search engines can better support them, is not an easy feat. We hypothesize
that research in this area cannot be done in isolation and that instead, it
will require long-term, dedicated collaborations involving researchers from
multiple disciplines. Increasing accessibility of search engines is one
important step forward towards creating an environment where all users,
especially children, have equal access to essential information. Accessibility
is a broad concept, one that encompasses multiple lenses. As a starting point
to foster discussion in this area, we shine a light on three categories of
disabilities that affect children’s ability to use search engines: physical,
mental, and developmental/learning.

Consider, for instance, physical interfaces, e.g., augmentative communication
devices or voice synthesizers, that are meant to convey ideas for disabled
people – how do researchers ensure users can use such devices to interface
with search engines as a means for users to form queries? How do search
engines handle input received from any assistive hardware and translate users’
information needs into queries or trigger click interactions? While some
hardware has already been designed, e.g., specialized controllers in the video
game industry, to improve accessibility for users with motor disabilities,
what can we learn as a community from these specialized tools and adopt to
make search more accessible? What about the way that SERP are presented, would
spacing of results be an issue? Do audio and visual aspects of SERP present
barriers or distractions for children with disorders such as anxiety or
ADD/ADHD?

Many interfaces on child-oriented search engines are designed to be more
engaging by using audio and visual elements. Some of these visual elements are
based on bright colors, which are known to have inherent emotions attached to
them, e.g., red is associated with sweets and green with healthy (Huang and
Lu, 2015). What sort of impact do these visual elements have on children with
mental disorders? Black and other dark colors are often associated with
connotations of depression. How do search engines deal with depressed children
as users? How would a search engine know if a child is suffering from some
form of trauma that could be triggered by results presented to them? Many
mental health issues will go undiagnosed for years. How can a search engine be
aware of and adapt to something that even the users, their teachers, or their
parents do not know?

With developmental conditions where age and maturity differ, how do search
engines account for the difference in development? In their current state,
modern search engines are heavily text-based, requiring that users can
adequately read and understand the resources returned. When a child is behind
in their reading level or math skills due to dyslexia or dyscalculia, how do
search engines adapt so that they can provide resources that are at children’s
cognitive level instead of age level?

The questions we have expounded here are not comprehensive of all the avenues
to explore. Instead, our goal is simply to encourage researchers to consider
significant barriers that, nowadays, search engines exhibit when it comes to
serving children with disabilities. As previously mentioned, tackling such a
complex and diverse matter should take place in a multidisciplinary setting.
Together, researchers from domains including education, mechanical &
electrical engineering, developmental & clinical psychology, sociology,
natural language processing, human-computer interaction, machine learning, and
medical must ruminate on what accessibility means to them. It is only based on
their reflection and collaboration with IR researchers that will enable the
design, development, and assessment of search engines that respond to real-
world necessities and can therefore provide the appropriate support that
children with disabilities need when interacting with search engines. It is
key to remember that accessibility does not have to be thought of as a burden,
as it enhances search engines without reducing their effectiveness (Azzopardi
and Bache, 2010). While the current generation of IR researchers has focused
on the effectiveness of search engines, it is imperative to inspire the next
to focus on accessibility as it is a long-term problem. It is also imperative
that we involve researchers coming into the IR community to (i) successfully
be part of interdisciplinary research teams and (ii) update IR curriculum
taught at undergraduate and graduate institutions to increase awareness about
different types of users and accessibility issues affecting IR-related systems
–beyond search engines–as they will be the ones carrying the torch forward. As
Eve Andersson, the Director of Google said, “the accessibility problems of
today are the mainstream breakthroughs of tomorrow” (Brownlee, 2018).

###### Acknowledgements.

Work partially funded by NSF Awards # 1763649 and #1930464.

## References

  * (1)
  * pew (2021) 2021\.  Demographics of Internet and Home Broadband Usage in the United States.  https://www.pewresearch.org/internet/fact-sheet/internet-broadband/?menuItem=6b886b10-55ec-44bc-b5a4-740f5366a404
  * Anuyah et al. (2019) Oghenemaro Anuyah, Ashlee Milton, Michael Green, and Maria Soledad Pera. 2019.  An empirical analysis of search engines’ response to web search queries associated with the classroom setting.  _Aslib Journal of Information Management_ (2019).
  * Azzopardi and Bache (2010) Leif Azzopardi and Richard Bache. 2010.  On the relationship between effectiveness and accessibility. In _Proceedings of the 33rd international ACM SIGIR conference on Research and development in information retrieval_. 889–890.
  * Bilal (1998) Dania Bilal. 1998\.  Children’s Search Processes in Using World Wide Web Search Engines: An Exploratory Study.. In _Proceedings of the ASIS annual meeting_ , Vol. 35. ERIC, 45–53.
  * Bilal (1999) Dania Bilal. 1999\.  Web Search Engines for Children: A Comparative Study and Performance Evaluation of” Yahooligans!,”” Ask Jeeves for Kids,” and” Super Snooper.”.. In _Proceedings of the ASIS annual meeting_ , Vol. 36. ERIC, 70–83.
  * Bilal (2010) Dania Bilal. 2010\.  The mediated information needs of children on the Autism Spectrum Disorder (ASD). In _Proceedings of the 31st ACM SIGIR Workshop on Accessible Search Systems, Geneva, Switzerland_. Citeseer, 42–49.
  * Bilal and Boehm (2017) Dania Bilal and Meredith Boehm. 2017.  Towards new methodologies for assessing relevance of information retrieval from web search engines on children’s queries.  _Qualitative and Quantitative Methods in Libraries_ 2, 1 (2017), 93–100.
  * Bilal and Gwizdka (2018) Dania Bilal and Jacek Gwizdka. 2018.  Children’s query types and reformulations in Google search.  _Information Processing & Management_ 54, 6 (2018), 1022–1041.
  * Bilal and Huang (2019) Dania Bilal and Li-Min Huang. 2019.  Readability and word complexity of SERPs snippets and web pages on children’s search queries.  _Aslib Journal of Information Management_ (2019).
  * Brownlee (2018) John Brownlee. 2018\.  How Designing For Disabled People Is Giving Google An Edge.  https://www.fastcompany.com/3060090/how-designing-for-the-disabled-is-giving-google-an-edge
  * Chaffey (2021) Dave Chaffey. 2021\.  Search engine marketing statistics: The latest search usage and adoption data to inform your strategies and tactics.  https://www.smartinsights.com/search-engine-marketing/search-engine-statistics/
  * Cheng et al. (2018) Yi Cheng, Kate Yen, Yeqi Chen, Sijin Chen, and Alexis Hiniker. 2018.  Why doesn’t it work? voice-driven interfaces and young children’s communication repair strategies. In _Proceedings of the 17th ACM Conference on Interaction Design and Children_. 337–348.
  * Collins-Thompson et al. (2011) Kevyn Collins-Thompson, Paul N Bennett, Ryen W White, Sebastian De La Chica, and David Sontag. 2011.  Personalizing web search results by reading level. In _Proceedings of the 20th ACM international conference on Information and knowledge management_. 403–412.
  * Danovitch (2019) Judith H Danovitch. 2019\.  Growing up with Google: How children’s understanding and use of internet-based devices relates to cognitive development.  _Human Behavior and Emerging Technologies_ 1, 2 (2019), 81–90.
  * Downs et al. (2020) Brody Downs, Oghenemaro Anuyah, Aprajita Shukla, Jerry Alan Fails, Sole Pera, Katherine Wright, and Casey Kennington. 2020.  Kidspell: A child-oriented, rule-based, phonetic spellchecker. In _Proceedings of The 12th Language Resources and Evaluation Conference_. 6937–6946.
  * Dragovic et al. (2016) Nevena Dragovic, Ion Madrazo Azpiazu, and Maria Soledad Pera. 2016\.  ” Is Sven Seven?” A Search Intent Module for Children. In _Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval_. 885–888.
  * Duarte Torres and Weber (2011) Sergio Duarte Torres and Ingmar Weber. 2011.  What and how children search on the web. In _Proceedings of the 20th ACM international conference on Information and knowledge management_. 393–402.
  * Eickhoff et al. (2010) Carsten Eickhoff, Pavel Serdyukov, and Arjen P. de Vries. 2010\.  Web Page Classification on Child Suitability. In _Proceedings of the 19th ACM International Conference on Information and Knowledge Management_ (Toronto, ON, Canada) _(CIKM ’10)_. Association for Computing Machinery, New York, NY, USA, 1425–1428.  https://doi.org/10.1145/1871437.1871638
  * Fainberg et al. (2016) Joachim Fainberg, Peter Bell, Mike Lincoln, and Steve Renals. 2016\.  Improving Children’s Speech Recognition Through Out-of-Domain Data Augmentation.. In _Interspeech_. 1598–1602.
  * Figueiredo and Meyers (2019) Vanessa Figueiredo and Eric M Meyers. 2019.  The false trade-off of relevance for safety in children’s search systems.  _Proceedings of the Association for Information Science and Technology_ 56, 1 (2019), 651–653.
  * Foss et al. (2012) Elizabeth Foss, Allison Druin, Robin Brewer, Phillip Lo, Luis Sanchez, Evan Golub, and Hilary Hutchinson. 2012.  Children’s search roles at home: Implications for designers, researchers, educators, and parents.  _Journal of the American Society for Information Science and Technology_ 63, 3 (2012), 558–573.
  * Fourney et al. (2018) Adam Fourney, Meredith Ringel Morris, Abdullah Ali, and Laura Vonessen. 2018.  Assessing the readability of web search results for searchers with dyslexia. In _The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval_. 1069–1072.
  * Gossen (2016) Tatiana Gossen. 2016\.  _Search engines for children: search user interfaces and information-seeking behaviour_.  Springer.
  * Gossen et al. (2013) Tatiana Gossen, Michael Kotzyba, Sebastian Stober, and Andreas Nürnberger. 2013.  Voice-controlled search user interfaces for young users. In _7th Annual Symposium on Human-Computer Interaction and Information Retrieval_. 2–5.
  * Gupta and Hilal (2013) Neha Gupta and Saba Hilal. 2013.  Algorithm to filter & redirect the web content for kids’.  _International Journal of Engineering and Technology_ 5 (2013).
  * Gwizdka and Bilal (2017) Jacek Gwizdka and Dania Bilal. 2017.  Analysis of children’s queries and click behavior on ranked results and their thought processes in google search. In _Proceedings of the 2017 conference on conference human information interaction and retrieval_. Association for Computing Machinery, New York, NY, USA, 377–380.
  * Haider and Sundin (2019) Jutta Haider and Olof Sundin. 2019.  _Invisible search and online search engines: The ubiquity of search in everyday life_.  Routledge.
  * Huang and Lu (2015) L Huang and J Lu. 2015\.  Eat with your eyes: Package color influences the expectation of food taste and healthiness moderated by external eating.  _Marketing Management_ 25, 2 (2015), 71–87.
  * Kerkmann and Lewandowski (2012) Friederike Kerkmann and Dirk Lewandowski. 2012.  Accessibility of web search engines: Towards a deeper understanding of barriers for people with disabilities.  _Library review_ (2012).
  * Kvikne and Berget (2019) Birgit Kvikne and Gerd Berget. 2019.  In search of trustworthy information: a qualitative study of the search behavior of people with dyslexia in Norway.  _Universal Access in the Information Society_ (2019), 1–12.
  * Landoni et al. (2021) Monica Landoni, Mohammad Aliannejadi, Theo Huibers, Emiliana Murgia, and Maria Soledad Pera. 2021\.  Right Way, Right Time: Towards a Better Comprehension of Young Students’ Needs When Looking for Relevant Search Results. In _Proceedings of 29th Conference on User Modeling, Adaptation and Personalization (UMAP)_. To Appear.
  * Landoni et al. (2019) Monica Landoni, Davide Matteri, Emiliana Murgia, Theo Huibers, and Maria Soledad Pera. 2019.  Sonny, Cerca! evaluating the impact of using a vocal assistant to search at school. In _International Conference of the Cross-Language Evaluation Forum for European Languages_. Springer, ”Springer International Publishing”, ”Cham”, 101–113.
  * Landoni et al. (2020) Monica Landoni, Maria Soledad Pera, Emiliana Murgia, and Theo Huibers. 2020.  Inside Out: Exploring the Emotional Side of Search Engines in the Classroom. In _Proceedings of the 28th ACM Conference on User Modeling, Adaptation and Personalization_. 136–144.
  * Li et al. (2013) Alberto Quattrini Li, Licia Sbattella, and Roberto Tedesco. 2013\.  Polispell: an adaptive spellchecker and predictor for people with dyslexia. In _International Conference on User Modeling, Adaptation, and Personalization_. Springer, 302–309.
  * Lovato et al. (2019) Silvia B Lovato, Anne Marie Piper, and Ellen A Wartella. 2019.  Hey Google, do unicorns exist? Conversational agents as a path to answers to children’s questions. In _Proceedings of the 18th ACM International Conference on Interaction Design and Children_. 301–313.
  * Madrazo Azpiazu et al. (2018) Ion Madrazo Azpiazu, Nevena Dragovic, Oghenemaro Anuyah, and Maria Soledad Pera. 2018.  Looking for the Movie Seven or Sven from the Movie Frozen? A Multi-perspective Strategy for Recommending Queries for Children. In _Proceedings of the 2018 Conference on Human Information Interaction & Retrieval_. 92–101.
  * Mikropoulos et al. (2020) Tassos A Mikropoulos, Michael Delimitros, Pavlos Gaintatzis, Georgia Iatraki, Aikaterini Stergiouli, Angeliki Tsiara, and Katerina Kalyvioti. 2020.  Acceptance and User Experience of an Augmented Reality System for the Simulation of Sensory Overload in Children with Autism. In _2020 6th International Conference of the Immersive Learning Research Network (iLRN)_. IEEE, 86–92.
  * Milton et al. (2020) Ashlee Milton, Oghenemaro Anuyah, Lawrence Spear, Katherine Landau Wright, and Maria Soledad Pera. 2020\.  A Ranking Strategy to Promote Resources Supporting the Classroom Environment. In _To appear in the Proceedings of the 2020 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology (WI-IAT’20)_.
  * Muir et al. (2019) Rebecca Muir, Kim M Thompson, and Asim Qayyum. 2019\.  Considering “atmosphere” in facilitating information seeking by people with invisible disabilities in public libraries.  _Proceedings of the Association for Information Science and Technology_ 56, 1 (2019), 216–226.
  * Patel and Singh (2016) Deepshikha Patel and Prashant Kumar Singh. 2016.  Kids safe search classification model. In _2016 International Conference on Communication and Electronics Systems (ICCES)_. IEEE, 1–7.
  * Rowlands et al. (2008) Ian Rowlands, David Nicholas, Peter Williams, Paul Huntington, Maggie Fieldhouse, Barrie Gunter, Richard Withey, Hamid R Jamali, Tom Dobrowolski, and Carol Tenopir. 2008\.  The Google generation: the information behaviour of the researcher of the future. In _Aslib proceedings_. Emerald Group Publishing Limited.
  * Sentance ([n.d.]) Rebecca Sentance. [n.d.].  What are the differences in how age demographics search the internet?  https://www.userzoom.com/ux-library/what-are-the-differences-in-how-age-demographics-search/
  * Serdyukov et al. (2011) Pavel Serdyukov, Djoerd Hiemstra, and Ian Ruthven. 2011\.  Towards accessible search systems. In _ACM SIGIR Forum_ , Vol. 44. ACM New York, NY, USA, 23–27.
  * Shaikh et al. (2015) Meher T Shaikh, Maria Soledad Pera, and Yiu-Kai Ng. 2015\.  Suggesting simple and comprehensive queries to elementary-grade children. In _2015 IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology (WI-IAT)_ , Vol. 1. IEEE, 252–259.
  * Shivakumar and Georgiou (2020) Prashanth Gurunath Shivakumar and Panayiotis Georgiou. 2020.  Transfer learning from adult to children for speech recognition: Evaluation, analysis and recommendations.  _Computer speech & language_ 63 (2020), 101077.
  * Unicef et al. (1989) Unicef et al. 1989\.  Convention on the Rights of the Child.  (1989).
  * Usta et al. (2021) Arif Usta, Ismail Sengor Altingovde, Rifat Ozcan, and Ozgur Ulusoy. 2021.  Learning to Rank for Educational Search Engines.  _IEEE Transactions on Learning Technologies_ (2021).
  * Vanderschantz and Hinze (2017a) Nicholas Vanderschantz and Annika Hinze. 2017a.  Do internet search engines support children’s search query construction: a visual analysis.  (2017).
  * Vanderschantz and Hinze (2017b) Nicholas Vanderschantz and Annika Hinze. 2017b.  A Study of Children’s Search Query Formulation Habits. In _Proceedings of the 31st International BCS Human Computer Interaction Conference (HCI 2017) 31_. 1–4.
  * Vtyurina (2019) Alexandra Vtyurina. 2019\.  Towards Non-Visual Web Search. In _Proceedings of the 2019 Conference on Human Information Interaction and Retrieval_. 429–432.
  * Vtyurina et al. (2019) Alexandra Vtyurina, Adam Fourney, Meredith Ringel Morris, Leah Findlater, and Ryen W White. 2019\.  VERSE: Bridging screen readers and voice assistants for enhanced eyes-free web search. In _The 21st International ACM SIGACCESS Conference on Computers and Accessibility_. 414–426.
  * Wild (1996) Martyn Wild. 1996\.  Researching the use of the Internet with young children. In _1995). Proceedings of Edith Cowan Memorial Conference_. 41–50.
  * Yarosh et al. (2018) Svetlana Yarosh, Stryker Thompson, Kathleen Watson, Alice Chase, Ashwin Senthilkumar, Ye Yuan, and AJ Bernheim Brush. 2018.  Children asking questions: speech interface reformulations and personification preferences. In _Proceedings of the 17th ACM Conference on Interaction Design and Children_. 300–312.
  * Young et al. (2016) Nicole Young, Kristelle Hudry, David Trembath, and Giacomo Vivanti. 2016.  Children with autism show reduced information seeking when learning new tasks.  _American journal on intellectual and developmental disabilities_ 121, 1 (2016), 65–73.