# A Cross Entropy Interpretation of Rényi Entropy for $\alpha$-leakage

Ni Ding1, Mohammad Amin Zarrabian2, and Parastoo Sadeghi3  1School of Computer
Science, University of Auckland<EMAIL_ADDRESS>2College of
Engineering and Computer Science, Australian National University,
<EMAIL_ADDRESS>3School of Engineering and Information
Technology, University of New South Wales<EMAIL_ADDRESS>
###### Abstract

This paper proposes an $\alpha$-leakage measure for $\alpha\in[0,\infty)$ by a
cross entropy interpretation of Rényi entropy. While Rényi entropy was
originally defined as an $f$-mean for $f(t)=\exp((1-\alpha)t)$, we reveal that
it is also a $\tilde{f}$-mean cross entropy measure for
$\tilde{f}(t)=\exp(\frac{1-\alpha}{\alpha}t)$. Minimizing this Rényi cross-
entropy gives Rényi entropy, by which the prior and posterior uncertainty
measures are defined corresponding to the adversary’s knowledge gain on
sensitive attribute before and after data release, respectively. The
$\alpha$-leakage is proposed as the difference between $\tilde{f}$-mean prior
and posterior uncertainty measures, which is exactly the Arimoto mutual
information. This not only extends the existing $\alpha$-leakage from
$\alpha\in[1,\infty)$ to the overall Rényi order range $\alpha\in[0,\infty)$
in a well-founded way with $\alpha=0$ referring to nonstochastic leakage, but
also reveals that the existing maximal leakage is a $\tilde{f}$-mean of an
elementary $\alpha$-leakage for all $\alpha\in[0,\infty)$, which generalizes
the existing pointwise maximal leakage.

##  I Introduction

Information leakage is usually measured in a Bayesian setting [1]: the
adversary’s knowledge gain on sensitive attribute after observing the released
data in return refers to the private information leakage to the data curator.
This parallels the quantitative information flow [2] in computer science. For
applications such as data privacy where the focus is usually on the worst-case
or risky high-cost data breach, maximal leakage is proposed in [3], where the
maximum is incurred by the event where the adversary attains best estimation
(on private data), as well as the attribute that reveals most information to
the adversary. This maximal leakage measure is further generalized by a
tunable $\alpha$-leakage [4] by incorporating the idea of Renyi uncertainty
measure/entropy [5] and Arimoto conditional entropy [6]: the Rényi order can
be chosen from $\alpha=1$ for average leakage measure to $\alpha=\infty$ for
maximal leakage measure. It is also shown in [4, Theorems 1 and 2] that the
$\alpha$-leakage is closely related to the two $\alpha$-order dependence
measures: Arimoto mutual information [6] [7, Eq. (21)] and Sibson mutual
information [8].

While Rényi measures, e.g., Rényi entropy and divergence, Arimoto and Sibson
mutual information, apply to all $\alpha\in[0,\infty)$, the $\alpha$-leakage
[4] is defined for $\alpha\in[1,\infty)$ only. Following [4], [9, 10] extend
Rényi order range of the $\alpha$-loss [4, Section III-A] to
$\alpha\in(0,\infty)$, but still leaves $\alpha=0$ out.111In fact, the
$\alpha$-loss in [4, Section III-A] at extended order $\alpha=0$ cannot be
directly determined by the continuity in $\alpha$ using L’Hôpital’s rule. On
the other hand, [11, 12] specifically use the max-entropy at $\alpha=0$ to
quantify the nonstochastic leakage, indicating that leakage measure can be
defined for the whole range $[0,\infty)$. In addition, for the minimizer of
$\alpha$-loss in [4, Section III-A]: the scaled probability $P_{X_{\alpha}}$
that normalizing $P_{X}^{\alpha}(x)$,222This scaled probability also appears
in Sibson identity [7, 13, 14]. an interesting observation in [10] showing
that probability masses assigned to high probability events increase as
$\alpha$ changes from $1$ to $\infty$ but reduce as $\alpha$ decreases blow
$1$. However, the reason what causes this difference has not been explained.

This paper proposes an $\alpha$-leakage measure in the form of Kolmogorov-
Nagumo (quasi-arithmetic or generalized $\tilde{f}$-mean) by a cross entropy
interpretation of Rényi entropy. While Rényi entropy was originally defined as
an $f$-mean for $f(t)=\exp((1-\alpha)t)$ [5], we reveal that it is also a
$\tilde{f}$-mean cross entropy measure for
$\tilde{f}(t)=\exp(\frac{1-\alpha}{\alpha}t)$ quantifying uncertainty incurred
by a soft decision $P_{\hat{X}}$ averaged w.r.t. a given probability
distribution $P_{X}$. Minimizing this Rényi cross-entropy over $P_{\hat{X}}$
gives Rényi entropy of $P_{X}$. This is used to determine the best estimation
on sensitive data an adversary can attain before and after data release and
therefore defines prior and posterior uncertainty or information gain,
respectively, in privacy leakage. An $\alpha$-leakage is then proposed as the
reduction in $\tilde{f}$-mean uncertainty. It is shown to be equal to Arimoto
mutual information and this equivalence extends from $\alpha\in[1,\infty)$ [4,
Theorem 1] to the overall Rényi order range $\alpha\in[0,\infty)$, where the
reason that $P_{X_{\alpha}}$ weights less for high probable events for
$\alpha\in(0,1)$, as observed in [10], is found to be a change from maximizing
certainty to minimizing uncertainty. At $\alpha=0$, $P_{X_{\alpha}}$ becomes
uniform distribution and the proposed $\alpha$-leakage reduces to the
nonstochastic one in [11, 12]. It is also shown that Sibson mutual information
is a $\tilde{f}$-mean over an $\alpha$-order elementary uncertainty (measured
by Rényi divergence), which equals to the pointwise maximal leakage (PML) [15]
at $\alpha=\infty$ and so maximal leakage [3] is a $\tilde{f}$-mean of PML.

##  II Notation

Capital and lowercase letters denote random variable and its elementary event
or instance, respectively, e.g., $x$ is an instance of random variable $X$.
Calligraphic letters denote sets, e.g., $\mathcal{X}$ refers to the alphabet
of $X$. We assume finite countable alphabet in this paper. Let $P_{X}(x)$
denote the probability $\Pr(X=x)$ on an elementary event $x$. For
$\mathcal{B}\subseteq\mathcal{X}$,
$\mathbf{P}_{X}(\mathcal{B})=(P_{X}(x):x\in\mathcal{B})$ is a probability
vector indexed by $\mathcal{B}$. The probability mass function is then
$\mathbf{P}_{X}(\mathcal{X})$, for which we use simplified notation
$\mathbf{P}_{X}$. The support of probability mass is denoted by
$\text{supp}(P_{X})=\\{x\colon P_{X}(x)>0\\}\subseteq\mathcal{X}$ and its
cardinality is $|\text{supp}(P_{X})|$. The expectation is denoted by
$\mathbb{E}_{X}[f(X)]=\sum_{x\in\mathcal{X}}P_{X}(x)f(x)$. $\mathbf{P}_{X}$
and $\mathbf{P}_{\hat{X}}$ refer to two probability distributions on the same
alphabet $\mathcal{X}$. For the conditional probability
$\mathbf{P}_{Y|X}=(P_{Y|X}(y|x)\colon x\in\mathcal{X},y\in\mathcal{Y})$, we
denote $\mathbf{P}_{Y|X=x}=(P_{Y|X}(y|x)\colon y\in\mathcal{Y})$ the
probability of $Y$ given the event $X=x$.

##  III Rényi Entropy: An $\tilde{f}$-mean Measure

In [5], Alfréd Rényi relaxed postulates for Shannon entropy to define the
$\alpha$-order uncertainty as a Kolmogorov-Nagumo mean (generalized $f$-mean)
for $f(t)=\exp((1-\alpha)t)$ as follows. For all
$\mathcal{B}\subseteq\mathcal{X}$, the $\alpha$-order uncertainty measure for
generalized probability distribution $\mathbf{P}_{X}(\mathcal{B})$
is333$\mathbf{P}_{X}(\mathcal{B})$ is a generalized probability distribution
if $\sum_{x\in\mathcal{B}}P_{X}(x)\leq 1$ [5].

$H_{\alpha}(\mathbf{P}_{X}(\mathcal{B}))=\frac{1}{1-\alpha}\log\sum_{x\in\mathcal{B}}\frac{P_{X}(x)}{\sum_{x\in\mathcal{B}}P_{X}(x)}\Big{(}\frac{1}{P_{X}(x)}\Big{)}^{1-\alpha}$

At singleton $\mathcal{B}=\\{x\\}$, we have _$X$ -elementary uncertainty
measure_ of $P_{X}(x)$ for all $x$

$H_{\alpha}(\mathbf{P}_{X}(\\{x\\}))=\frac{1}{1-\alpha}\log\Big{(}\frac{1}{P_{X}(x)}\Big{)}^{1-\alpha}=-\log
P_{X}(x).$

Rényi entropy is then defined as an $f$-mean of $X$-elementary uncertainty
w.r.t. to probability distribution $P_{X}$ itself:

$\displaystyle H_{\alpha}(\mathbf{P}_{X})$
$\displaystyle=\frac{1}{1-\alpha}\log\sum_{x\in\mathcal{X}}P_{X}(x)P_{X}^{\alpha-1}(x)$
(1)
$\displaystyle=f^{-1}(\mathbb{E}_{X}[f(H_{\alpha}(\mathbf{P}_{X}(\\{x\\})))])$
(2)

for $\alpha\in(0,1)\cup(1,\infty)$, with the measure in extended orders
$\alpha=0,1$ and $\infty$ determined by the continuity in $\alpha$:
$H_{0}=\log\text{supp}(P_{X})$ is the max-entropy, $H_{1}=\mathbb{E}_{X}[-\log
P_{X}(x)]$ is the Shannon entropy and $H_{\infty}=-\log\max_{x}P_{X}(x)$ is
the min-entropy.

Rewrite Rényi entropy (1) as

$\displaystyle H_{\alpha}(\mathbf{P}_{X})$
$\displaystyle=\frac{\alpha}{1-\alpha}\log\Big{(}\sum_{x\in\mathcal{X}}P_{X}^{\alpha}(x)\Big{)}^{\frac{1}{\alpha}}$
(3)
$\displaystyle=\frac{\alpha}{1-\alpha}\log\sum_{x\in\mathcal{X}}P_{X}(x)\Big{(}\frac{P_{X}^{\alpha}(x)}{\sum_{x\in\mathcal{X}}P_{X}^{\alpha}(x)}\Big{)}^{\frac{\alpha-1}{\alpha}}$
$\displaystyle=\frac{\alpha}{1-\alpha}\log\sum_{x\in\mathcal{X}}P_{X}(x)\Big{(}\frac{1}{P_{X_{\alpha}}(x)}\Big{)}^{\frac{1-\alpha}{\alpha}}$
(4)

where
$P_{X_{\alpha}}(x)=\frac{P_{X}^{\alpha}(x)}{\sum_{x\in\mathcal{X}}P_{X}^{\alpha}(x)}$
for all $x\in\mathcal{X}$. This is a $\tilde{f}$-mean for
$\tilde{f}(t)=\exp({\frac{1-\alpha}{\alpha}}t)$:444[5, Postulate 5’] requires
monotonic, continuous and invertible function, which satisfies for both
$f(t)=\exp((1-\alpha)t)$ and $\tilde{f}(t)=\exp({\frac{1-\alpha}{\alpha}}t)$.
for $\mathcal{B}\subseteq\mathcal{X}$, define uncertainty

$\tilde{H}_{\alpha}(\mathbf{P}_{X}(\mathcal{B}))=\frac{\alpha}{1-\alpha}\log\sum_{x\in\mathcal{B}}\frac{P_{X}(x)}{\sum_{x\in\mathcal{B}}P_{X}(x)}\Big{(}\frac{1}{P_{X_{\alpha}}(x)}\Big{)}^{\frac{1-\alpha}{\alpha}}$

with the $X$-elementary uncertainty being

$\tilde{H}_{\alpha}(\mathbf{P}_{X}(\\{x\\}))=\frac{\alpha}{1-\alpha}\log\Big{(}\frac{1}{P_{X_{\alpha}}(x)}\Big{)}^{\frac{1-\alpha}{\alpha}}=-\log
P_{X_{\alpha}}(x).$

Then, Rényi entropy is a $\tilde{f}$-mean of
$\tilde{H}_{\alpha}(\mathbf{P}_{X}(\\{x\\}))$:

$H_{\alpha}(\mathbf{P}_{X})=\tilde{H}_{\alpha}(\mathbf{P}_{X})=\tilde{f}^{-1}(\mathbb{E}_{X}[\tilde{f}(\tilde{H}_{\alpha}(\mathbf{P}_{X}(\\{x\\})))]).$
(5)

The measure at extended orders $\alpha=0,1$ and $\infty$ is determined by the
continuity in $\alpha$ using (4):

$H_{\alpha}(\mathbf{P}_{X})=\begin{cases}\log\max_{x\in\text{supp}(P_{X})}\frac{1}{P_{X_{0}}(x)}&\alpha=0\\\
-\sum_{x\in\mathcal{X}}P_{X}(x)\log P_{X_{1}}(x)&\alpha=1\\\
-\log\sum_{x\in\mathcal{X}}P_{X}(x)P_{X_{\infty}}(x)&\alpha=\infty\end{cases}$
(6)

with the scaled probability $\mathbf{P}_{X_{\alpha}}$ in corresponding orders
being555 A derivation of $P_{X_{\infty}}(x)$ can be found in [4, Appendix A].

$\displaystyle
P_{X_{0}}(x)=\begin{cases}1/|\text{supp}(P_{X})|&x\in\text{supp}(P_{X})\\\
0&\text{otherwise}\end{cases},$ $\displaystyle P_{X_{1}}(x)=P_{X}(x),\forall
x,$ $\displaystyle
P_{X_{\infty}}(x)=\begin{cases}1/|\operatorname*{arg\,max}_{x}P_{X}(x)|&x\in\operatorname*{arg\,max}_{x}P_{X}(x)\\\
0&\text{otherwise}\end{cases},$

Here, both (2) and (5) are Kolmogorov-Nagumo means stating that the
uncertainty or information gain is accumulative w.r.t. its appearance
frequency in the codomain of $f$ and $\tilde{f}$, respectively.666In fact,
equations (2) and (5) hold for all partitions $\mathcal{I}$ of $\mathcal{X}$
[5, Postulate 5’]. For example, for (2),
$H_{\alpha}(\mathbf{P}_{X})=f^{-1}(\sum_{\mathcal{B}\in\mathcal{I}}P_{X}(\mathcal{B})f(H_{\alpha}(P_{X}(\mathcal{B}))))$
with $P_{X}(\mathcal{B})=\sum_{x\in\mathcal{B}}P_{X}(x)$ for all
$\mathcal{I}$.  However, their $X$-elementary uncertainty measures different
probability mass: $H_{\alpha}(\mathbf{P}_{X}(\\{x\\}))$ measures $P_{X}(x)$,
while $H_{\alpha}(\mathbf{P}_{X}(\\{x\\}))$ measures scaled probability mass
$P_{X_{\alpha}}(x)$. That is, $\tilde{H}_{\alpha}(\mathbf{P}_{X})$ in (5), or
$H_{\alpha}(\mathbf{P}_{X})$ expressed as in (4), should be interpreted as the
$\tilde{f}$-average information gain incurred by scaled probability
$\mathbf{P}_{X_{\alpha}}$ with the appearance frequency of each elementary
information gain governed by the original probability $\mathbf{P}_{X}$. This
gives rise to a definition of $\alpha$-order cross entropy as follows.

##  IV $\alpha$-Cross Entropy

For two probability distributions $\mathbf{P}_{X}$ and $\mathbf{P}_{\hat{X}}$,
define cross entropy for $\alpha\in[0,\infty)$ by777Without confusion,
$H_{\alpha}$ with two inputs refers to cross entropy and $H_{\alpha}$ with one
input refers to entropy.

$H_{\alpha}(\mathbf{P}_{X},\mathbf{P}_{\hat{X}})=\\\
\begin{cases}\frac{\alpha}{1-\alpha}\log\sum_{x}P_{X}(x)P_{\hat{X}}^{\frac{\alpha-1}{\alpha}}(x)&\alpha\in(0,1)\cup(1,\infty)\\\
\log\max_{x\in\text{supp}(P_{X})}\frac{1}{P_{\hat{X}}(x)}&\alpha=0\\\
-\sum_{x\in\mathcal{X}}P_{X}(x)\log P_{\hat{X}}(x)&\alpha=1\\\
-\log\sum_{x\in\mathcal{X}}P_{X}(x)P_{\hat{X}}(x)&\alpha=\infty\end{cases}$
(7)

A common problem is the minimization of cross entropy over the decision
probability or soft decision $\mathbf{P}_{\hat{X}}$, for which we derive
Theorem 1 below. It can be considered as an extension of [4, Lemma 1] from
$\alpha\in[1,\infty)$ to $\alpha\in[0,\infty)$ but with a completely different
approach by using cross entropy
$H_{\alpha}(\mathbf{P}_{X},\mathbf{P}_{\hat{X}})$. The difference from [4]
will be discussed in detail in Sections IV-E and V-C.

###### Theorem 1

For a given $\mathbf{P}_{X}$,

$\min_{\mathbf{P}_{\hat{X}}}H_{\alpha}(\mathbf{P}_{X},\mathbf{P}_{\hat{X}})=H_{\alpha}(\mathbf{P}_{X})$
(8)

with the minimizer $\mathbf{P}_{\hat{X}}^{*}=\mathbf{P}_{X_{\alpha}}$ for all
$\alpha\in[0,\infty)$.

###### Proof:

For each $\alpha\in(0,1)\cup(1,\infty)$,

$\displaystyle\min_{\mathbf{P}_{\hat{X}}}H_{\alpha}(\mathbf{P}_{X},\mathbf{P}_{\hat{X}})$
$\displaystyle=\log\min_{\mathbf{P}_{\hat{X}}}\Big{(}\sum_{x}P_{X}(x)P_{\hat{X}}^{\frac{\alpha-1}{\alpha}}(x)\Big{)}^{\frac{\alpha}{1-\alpha}}$
(9)
$\displaystyle=\begin{cases}\log\big{(}\max_{\mathbf{P}_{\hat{X}}}\sum_{x}P_{X}(x)P_{\hat{X}}^{\frac{\alpha-1}{\alpha}}(x)\big{)}^{\frac{\alpha}{1-\alpha}}&\alpha\in(1,\infty)\\\
\log\big{(}\min_{\mathbf{P}_{\hat{X}}}\sum_{x}P_{X}(x)P_{\hat{X}}^{\frac{\alpha-1}{\alpha}}(x)\big{)}^{\frac{\alpha}{1-\alpha}}&\alpha\in(0,1)\end{cases}.$
(10)

Consider the convex combination
$\sum_{x}P_{X}(x)P_{\hat{X}}^{\frac{\alpha-1}{\alpha}}(x)$: it is concave in
$\mathbf{P}_{\hat{X}}$ for all $\alpha\in(1,\infty)$ where
$\frac{\alpha-1}{\alpha}\in(0,1)$ but convex in $\mathbf{P}_{\hat{X}}$ for
$\alpha\in(0,1)$ where $\frac{\alpha-1}{\alpha}\in(-\infty,0)$. In both cases,
problem (8) reduces to a convex minimization with the probability distribution
constraint $\sum_{x\in\mathcal{X}}P_{\hat{X}}(x)=1$, where the optimizer is
$\mathbf{P}_{\hat{X}}^{*}=\mathbf{P}_{X_{\alpha}}$ and the minimum is
$H_{\alpha}(\mathbf{P}_{X},\mathbf{P}_{X_{\alpha}})=H_{\alpha}(\mathbf{P}_{X})$
(See Appendix A).

For the extended orders $\alpha=0,1$ and $\infty$,

$\displaystyle\min_{\mathbf{P}_{\hat{X}}}H_{0}(\mathbf{P}_{X},\mathbf{P}_{\hat{X}})$
$\displaystyle=-\log\max_{\mathbf{P}_{\hat{X}}}\min_{x\in\text{supp}(P_{X})}P_{\hat{X}}(x)$
$\displaystyle=\log|\text{supp}(P_{X})|=H_{0}(\mathbf{P}_{X}),$
$\displaystyle\min_{\mathbf{P}_{\hat{X}}}H_{1}(\mathbf{P}_{X},\mathbf{P}_{\hat{X}})$
$\displaystyle=H_{1}(\mathbf{P}_{X})+\min_{\mathbf{P}_{\hat{X}}}D_{1}(\mathbf{P}_{X}\|\mathbf{P}_{\hat{X}})$
(11) $\displaystyle=H_{1}(\mathbf{P}_{X}),$
$\displaystyle\min_{\mathbf{P}_{\hat{X}}}H_{\infty}(\mathbf{P}_{X},\mathbf{P}_{\hat{X}})$
$\displaystyle=-\log\max_{\mathbf{P}_{\hat{X}}}\sum_{x\in\mathcal{X}}P_{X}(x)P_{\hat{X}}(x)$
$\displaystyle=-\log\max_{x\in\mathcal{X}}P_{X}(x)=H_{\infty}(\mathbf{P}_{X})$

with the minimizer $\mathbf{P}_{\hat{X}}^{*}=\mathbf{P}_{X_{0}}$,
$\mathbf{P}_{X_{1}}$ and $\mathbf{P}_{X_{\infty}}$, respectively. Thus, we
have the solution $\mathbf{P}_{X}^{*}=\mathbf{P}_{X_{\alpha}}$ and the minimum
$H_{\alpha}(\mathbf{P}_{X})$ for all $\alpha\in[0,\infty)$. ∎

Equation (11) is a decomposition of the cross entropy
$H_{1}(\mathbf{P}_{X},\mathbf{P}_{\hat{X}})=-\sum_{x\in\mathcal{X}}P_{X}(x)\log
P_{\hat{X}}(x)$ into the summation of $H_{1}(\cdot)$ and $D_{1}(\cdot\|\cdot)$
denoting Shannon entropy and Kullback–Leibler divergence, respectively.

###  IV-A Difference between $\alpha\in(0,1)$ and $\alpha\in(1,\infty)$

An interesting observation in (10) is the conversion from maximization to
minimization when $\alpha$ is crossing the value $1$. This is because
$\sum_{x}P_{X}(x)P_{\hat{X}}^{\frac{\alpha-1}{\alpha}}(x)$ is changing from
certainty to uncertainty measure as follows. Knowing $P_{\hat{X}}(x)$ denotes
the certainty of the event $x$ under decision $\mathbf{P}_{\hat{X}}$, for
$\alpha\in(1,\infty)$,
$\sum_{x}P_{X}(x)P_{\hat{X}}^{\frac{\alpha-1}{\alpha}}(x)$ measures the
expected certainty incurred by $\mathbf{P}_{\hat{X}}$; for $\alpha\in(0,1)$,
$\sum_{x}P_{X}(x)P_{\hat{X}}^{\frac{\alpha-1}{\alpha}}(x)=\sum_{x}P_{X}(x)\big{(}P_{\hat{X}}^{-1}(x)\big{)}^{\frac{1-\alpha}{\alpha}}$
measures expected uncertainty incurred by $\mathbf{P}_{\hat{X}}$.

Note, despite the conversion between certainty and uncertainty interpretation,
the cross entropy $H_{\alpha}(\mathbf{P}_{X},\mathbf{P}_{\hat{X}})$ remains an
uncertainty measure for all $\alpha\in[0,\infty)$. This $1$-crossing effect is
also true for Rényi entropy in (1):
$\sum_{x\in\mathcal{X}}P_{X}(x)P_{X}^{\alpha-1}(x)$ measures certainty for
$\alpha\in(1,\infty)$ and uncertainty for $\alpha\in(0,1)$. But,
$H_{\alpha}(\mathbf{P}_{X})$ remains an uncertainty measure for all
$\alpha\in[0,\infty)$.

$0$$2$$4$$6$$8$$10$$12$$14$$16$$18$$20$$0$$0.2$$0.4$$x$$P_{X_{\alpha}}(x)$$\alpha=10$$\alpha=5$$\alpha=1$$\alpha=0.5$$\alpha=0.01$

Figure 1: For $X\sim\text{Binomial}(20,5)$, the probability
$\mathbf{P}_{X_{\alpha}}$ with
$P_{X_{\alpha}}(x)=\frac{P_{X}^{\alpha}(x)}{\sum_{x\in\mathcal{X}}P_{X}^{\alpha}(x)}$
for all $x\in\\{0,1,\dotsc,20\\}$. Here, the plot for $\alpha=1$ shows the
original Binomial probability.

###  IV-B Optimal decision $\mathbf{P}_{X_{\alpha}}$ in $\alpha$

For the optimal decision $\mathbf{P}_{X_{\alpha}}$, there is also a clear
difference when $\alpha$ is crossing $1$. For $\alpha\in(1,\infty)$, the
decision that maximizes
$\sum_{x}P_{X}(x)P_{\hat{X}}^{\frac{\alpha-1}{\alpha}}(x)$ should assign
higher weights to the more probable events $x$ of $X$. Conversely, for
$\alpha\in(0,1)$, to minimize
$\sum_{x}P_{X}(x)P_{\hat{X}}^{\frac{\alpha-1}{\alpha}}(x)$, we should have
$P_{\hat{X}}^{\frac{\alpha-1}{\alpha}}(x)$ assign less weights to high
probability events. As the weight $P_{\hat{X}}^{\frac{\alpha-1}{\alpha}}(x)$
is always increasing in $\alpha$, when $\alpha$ is approaching $\infty$, all
probability mass will concentrates at the most probable events eventually;
when $\alpha$ decreases to $0$, uniform distribution is reached.

See Fig. 1. We choose the same binomial random variable as in [4, Fig. 3]. The
observation for range $\alpha\in[1,\infty)$ is the same as [4]: as $\alpha$
increases, the optimal decision $\mathbf{P}_{X_{\alpha}}$ accentuates high
probable events more than the low probable ones, which forces the probability
mass assigned to low probable events to decrease to zero. On the contrary, as
$\alpha$ decreases from $1$, $\mathbf{P}_{X_{\alpha}}$ compensate more weight
to less probability events (the same observation as in [10]), which in return
reduces the probability mass for high probability ones, until it flattens
around $\alpha=0$.

###  IV-C Optimal Estimation $\mathbf{P}_{\hat{X}|Y}^{*}$

Consider the estimation problem over Markov chain $X-Y-\hat{X}$ for given
channel $\mathbf{P}_{Y|X}$. For input $\mathbf{P}_{X}$, a receiver applies
decision $\mathbf{P}_{\hat{X}|Y}$ to channel output $Y$ to get the estimation
$\hat{X}$. For each $y\in\mathcal{Y}$, use the
$H_{\alpha}(\mathbf{P}_{X|Y=y},\mathbf{P}_{\hat{X}|Y=y})$ to quantify the
uncertainty caused by $\mathbf{P}_{\hat{X}|Y=y}$ averaged by the posterior
distribution $\mathbf{P}_{X|Y=y}$. The best estimation is the minimizer
$\mathbf{P}_{\hat{X}|Y=y}^{*}=\mathbf{P}_{X_{\alpha}|Y=y}$ of
$\min_{\mathbf{P}_{\hat{X}|Y=y}}H_{\alpha}(\mathbf{P}_{X|Y=y},\mathbf{P}_{\hat{X}|Y=y})$
with the minimum uncertainty attains at $H_{\alpha}(\mathbf{P}_{X|Y=y})$.
Here,
$P_{X_{\alpha}|Y=y}(x)=\frac{P_{X|Y=y(x)}^{\alpha}}{\sum_{x\in\mathcal{X}}{P_{X|Y=y(x)}^{\alpha}}},\forall
x$. This will be used for the posterior uncertainty in defining
$\alpha$-leakage in Section V.

At $\alpha=\infty$, $\mathbf{P}_{\hat{X}|Y=y}^{*}=\mathbf{P}_{X_{\infty}|Y=y}$
is a maximum a posteriori decision that assigns probability mass to the most
probable events in $\operatorname*{arg\,max}_{x}P_{X|Y=y}(x)$ only. This was
also pointed out in [4]. At $\alpha=0$,
$\mathbf{P}_{\hat{X}|Y=y}^{*}=\mathbf{P}_{X_{0}|Y=y}$ assigns the same
probability mass to all events $x\in\text{supp}(P_{X|Y=y})$. This is a
decision adopted in nonstochastic settings [11, 12], where the dataset is not
large enough to reveal the true statistics of a population (e.g., each event
only appears one or two times) and therefore the uncertainty largely depends
on the size of alphabet or support. Stacking $\mathbf{P}_{\hat{X}|Y=y}^{*}$
for all $y$, we construct the optimal decision
$\mathbf{P}_{\hat{X}|Y}^{*}=(\mathbf{P}_{X_{\alpha}|Y=y}\colon
y\in\mathcal{Y})$.

###  IV-D Arimoto Conditional Entropy

By equation (3) and the $\tilde{f}$-mean expression in (4), for each $y\in Y$,

$\exp\Big{(}\frac{1-\alpha}{\alpha}H_{\alpha}(\mathbf{P}_{X|Y=y})\Big{)}=\Big{(}\sum_{x\in\mathcal{X}}P_{X|Y}^{\alpha}(x|y)\Big{)}^{\frac{1}{\alpha}}\\\
=\mathbb{E}_{X|Y=y}\Big{[}\exp\Big{(}\frac{1-\alpha}{\alpha}\tilde{H}_{\alpha}(\mathbf{P}_{X|Y=y}(\\{x\\}))\Big{)}\Big{]}$

where $\tilde{H}_{\alpha}(\mathbf{P}_{X|Y=y}(\\{x\\}))=-\log
P_{X_{\alpha}|Y=y}(x)$. Then, the Arimoto conditional entropy [6] is again a
$\tilde{f}$-mean:

$\displaystyle H_{\alpha}(\mathbf{P}_{X|Y})$
$\displaystyle=\frac{\alpha}{1-\alpha}\log\mathbb{E}_{Y}\Big{[}\Big{(}\sum_{x\in\mathcal{X}}P_{X|Y}^{\alpha}(x|y)\Big{)}^{\frac{1}{\alpha}}\Big{]}$
$\displaystyle=\frac{\alpha}{1-\alpha}\log\mathbb{E}_{Y}\Big{[}\exp\Big{(}\frac{1-\alpha}{\alpha}H_{\alpha}(\mathbf{P}_{X|Y=y})\Big{)}\Big{]}$
(12)
$\displaystyle=\frac{\alpha}{1-\alpha}\log\mathbb{E}_{XY}\Big{[}\exp\Big{(}\frac{1-\alpha}{\alpha}\tilde{H}_{\alpha}(\mathbf{P}_{X|Y=y}(\\{x\\}))\Big{)}\Big{]}$
(13)

where (12) is a $\tilde{f}$-mean in $\mathcal{Y}$ where the $Y$-elementary
uncertainty measure is $H_{\alpha}(\mathbf{P}_{X|Y=y})$ for all
$y\in\mathcal{Y}$ and (13) is a $\tilde{f}$-mean in
$\mathcal{X}\times\mathcal{Y}$ where the $XY$-elementary uncertainty measure
is $\tilde{H}_{\alpha}(\mathbf{P}_{X|y}(\\{x\\}))$ for all
$(x,y)\in\mathcal{X}\times\mathcal{Y}$. Alternatively, we can write equation
(12) in terms of cross entropy as

$H_{\alpha}(\mathbf{P}_{X|Y})=\\\
\frac{\alpha}{1-\alpha}\log\mathbb{E}_{Y}\Big{[}\exp\Big{(}\frac{1-\alpha}{\alpha}\min_{\mathbf{P}_{\hat{X}|Y=y}}H_{\alpha}(\mathbf{P}_{X|Y=y},\mathbf{P}_{\hat{X}|Y=y})\Big{)}\Big{]},$

i.e., it is an $\tilde{f}$-mean of minimum uncertainty, with each
$Y$-elementary uncertainty minimized by the optimal strategy
$\mathbf{P}_{\hat{X}|Y}^{*}$ for the best estimation of $X$.

###  IV-E Comparison to $\alpha$-loss in [4]

In optimizations, an uncertainty incurs loss and an $\alpha$-loss function
$L_{\alpha}(\mathbf{P}_{X},\mathbf{P}_{\hat{X}})=\sum_{x\in\mathcal{X}}P_{X}(x)l_{\alpha}(P_{\hat{X}}(x))$
is proposed in [4, Section III-A] for $\alpha\in[1,\infty)$ with the
$X$-elementary loss being
$l_{\alpha}(P_{\hat{X}}(x))=\frac{\alpha}{\alpha-1}(1-P_{\hat{X}}^{\frac{\alpha-1}{\alpha}}(x))$,
which generalizes log-loss and $0$-$1$-loss at extended orders $\alpha=1$ and
$\infty$, respectively. However, this definition leave range $\alpha\in[0,1)$
out and the interpretation of the coefficient $\frac{\alpha}{\alpha-1}$ is not
clearly explained. In fact, it should rather be an exponential index, where we
have an $\alpha$-loss function well-founded by the Rényi probability [16, 17,
18] (see Appendix B) in the form of $\frac{1-\alpha}{\alpha}$-order power
mean, another Kolmogorov-Nagumo mean [14, Section II-A] using the minimand in
(9): for all $\alpha\in[0,\infty)$, we propose average $\alpha$-loss incurred
by decision $\mathbf{P}_{\hat{X}}$

$L_{\alpha}(\mathbf{P}_{X},\mathbf{P}_{\hat{X}})=\Big{(}\sum_{x}P_{X}(x)l_{\alpha}(P_{\hat{X}}(x))^{\frac{1-\alpha}{\alpha}}\Big{)}^{\frac{\alpha}{1-\alpha}}.$
(14)

with $X$-elementary loss being
$l_{\alpha}(P_{\hat{X}}(x))=P_{\hat{X}}^{-1}(x)$. This
$\frac{1-\alpha}{\alpha}$-order power mean is readily extended to orders
$\alpha=0$, $1$ and $\infty$:
$L_{0}(\mathbf{P}_{X},\mathbf{P}_{\hat{X}})=\max_{x\in\text{supp}(P_{X})}P_{\hat{X}}^{-1}(x)$
is nonstochastic loss;
$L_{1}(\mathbf{P}_{X},\mathbf{P}_{\hat{X}})=\prod_{x\in\mathcal{X}}P_{\hat{X}}(x)^{-P_{X}(x)}$
is the exponential of expected log-loss;
$L_{\infty}(\mathbf{P}_{X},\mathbf{P}_{\hat{X}})=\big{(}\sum_{x\in\mathcal{X}}P_{X}(x)P_{\hat{X}}(x)\big{)}^{-1}$
with $1-\sum_{x\in\mathcal{X}}P_{X}(x)P_{\hat{X}}(x)$ being the expected
$0$-$1$-loss. For all $\alpha\in[0,\infty)$,
$L_{\alpha}(\mathbf{P}_{X},\mathbf{P}_{\hat{X}})=\exp(H_{\alpha}(\mathbf{P}_{X},\mathbf{P}_{\hat{X}}))$.

###  IV-F Other cross entropy measures

There are two existing definitions of Rényi cross entropy proposed in [19,
20], respectively,

$\displaystyle H_{\alpha}(\mathbf{P}_{X},\mathbf{P}_{\hat{X}})$
$\displaystyle=\frac{1}{1-\alpha}\log\sum_{x\in\mathcal{X}}P_{X}(x)P_{\hat{X}}^{\alpha-1}(x),$
(15) $\displaystyle H_{\alpha}(\mathbf{P}_{X},\mathbf{P}_{\hat{X}})$
$\displaystyle=H_{\alpha}(\mathbf{P}_{X})+\min_{\mathbf{P}_{\hat{X}}}D_{\alpha}(\mathbf{P}_{X}\|\mathbf{P}_{\hat{X}}),$
(16)

to the best of our knowledge. Definition (15) is based on (1), where
$H_{\alpha}(\mathbf{P}_{X})$ is not the minimum of
$\min_{\mathbf{P}_{\hat{X}}}H_{\alpha}(\mathbf{P}_{X},\mathbf{P}_{\hat{X}})$
however. Definition (16) forces the decomposition in (11) over all
$\alpha\in[0,\infty)$. According to [5, Postulate 5’, Theorems 1 and 2], the
decomposition for order $\alpha=1$ is well defined. But, this decomposition
for the remaining $\alpha\in[0,1)\cup(1,\infty)$ should be further verified.

##  V $\alpha$-leakage

Information leakage studies [3, 4] are based on an estimation model: Markov
chain $U-X-Y-\hat{U}$, where the privatization channel $\mathbf{P}_{Y|X}$ is
given and $U$ denotes a sensitive attribute of channel input $X$. An adversary
wants to infer/estimate $U$ with the access to the privatized data $Y$. Using
the $\alpha$-cross entropy in (7) to get the adversary’s best estimations
$\mathbf{P}_{\hat{U}}^{*}$ and $\mathbf{P}_{\hat{U}|Y}^{*}$ and the
corresponding minima to quantify prior and posterior uncertainty,
respectively, we propose a leakage measure below as the reduction in
$\tilde{f}$-mean uncertainty, where
$\tilde{f}(t)=\exp(\frac{1-\alpha}{\alpha}t)$.

###### Definition 1

For all $[0,\infty)$, the $\alpha$-leakage is

$\displaystyle\mathcal{L}_{\alpha}(U\rightarrow Y)$
$\displaystyle=\min_{\mathbf{P}_{\hat{U}}}H_{\alpha}(\mathbf{P}_{U},\mathbf{P}_{\hat{U}})-$
$\displaystyle\frac{\alpha}{1-\alpha}\log\mathbb{E}_{Y}\Big{[}\exp\Big{(}\frac{1-\alpha}{\alpha}\min_{\mathbf{P}_{\hat{U}|Y=y}}H_{\alpha}(\mathbf{P}_{U|Y=y},\mathbf{P}_{\hat{U}|Y=y})\Big{)}\Big{]}$
(17)
$\displaystyle=H_{\alpha}(\mathbf{P}_{U})-H_{\alpha}(\mathbf{P}_{U|Y})=I_{\alpha}^{\text{A}}(U;Y),$

where $I_{\alpha}^{\text{A}}(U;Y)$ is the Arimoto mutual information between
$U$ and $Y$.

###  V-A Maximal $\alpha$-leakage

Following [3, 4], the maximal leakage is incurred by attribute $U$ that leaks
the most information.

###### Proposition 1

For Markov chain $U-X-Y$ with given $\mathbf{P}_{Y|X}$ and
$\mathbf{P}_{X}$,888The supremum in (18) is the same as $\sup_{U-X-Y-\hat{U}}$
in [3, Definition 1]: it is over all $U$ with $\mathbf{P}_{UX}$ satisfying
$\sum_{u\in\mathcal{U}}P_{UX}(u,x)=P_{X}(x),\forall x$ and the Markov chain
constraint $P_{Y|XU}(y|x,u)=P_{Y|X}(y|x),\forall u,x,y$, i.e., only fix
$\mathbf{P}_{X}$ and $\mathbf{P}_{Y|X}$ in Markov chain $U-X-Y-\hat{U}$. Also
note that $\sup_{U-X-Y}$ in [4, Definition 6] is over the same Markov chain
with only $\mathbf{P}_{Y|X}$ fixed.

$\displaystyle\sup_{\mathbf{P}_{UX}}$
$\displaystyle\mathcal{L}_{\alpha}(U\rightarrow Y)$ (18)
$\displaystyle=I_{\alpha}^{\text{S}}(X;Y)$ (19)
$\displaystyle=\frac{\alpha}{\alpha-1}\log\mathbb{E}_{Y}\Big{[}\exp\Big{(}\frac{\alpha-1}{\alpha}\mathcal{L}_{\alpha}(X\rightarrow
y)\Big{)}\Big{]}$ (20)

for all $\alpha\in[0,\infty)$ with the $Y$-elementary leakage being

$\displaystyle\mathcal{L}_{\alpha}(X\rightarrow y)$
$\displaystyle=\frac{1}{\alpha-1}\log\sum_{x\in\mathcal{X}}P_{X}(x)\Big{(}\frac{P_{X|Y}(x|y)}{P_{X}(x)}\Big{)}^{\alpha}$
(21) $\displaystyle=D_{\alpha}(\mathbf{P}_{X|Y=y}\|\mathbf{P}_{X}).$ (22)

###### Proof:

Equality (19) is based on the equivalence of Arimoto and Sibson mutual
information when optimizing over channel input [21], [7, Theorem 5] and the
data processing inequality for Sibson mutual information [22, Theorem 5]:

$\sup_{\mathbf{P}_{U}}I_{\alpha}^{\text{A}}(U;Y)=\sup_{\mathbf{P}_{U}}I_{\alpha}^{\text{S}}(U;Y)\leq
I_{\alpha}^{\text{S}}(X;Y)$

for all $U$ that forms the Markov chain $U-X-Y$ and supremum attains at $U=X$.
We rewrite the Sibson mutual information [8]

$I_{\alpha}^{\text{S}}(X;Y)=\frac{\alpha}{\alpha-1}\log\sum_{y\in\mathcal{Y}}\Big{(}\sum_{x\in\mathcal{X}}P_{X}(x)P_{Y|X}^{\alpha}(y|x)\Big{)}^{\frac{1}{\alpha}}$
(23)

in (20) as a $\tilde{f}$-mean of the $Y$-elementary measure in (21) w.r.t.
channel output $\mathbf{P}_{Y}$. ∎

One can further maximize over the channel input as in [4]:

$\mathcal{L}_{\alpha}^{\text{max}}(X\rightarrow
Y)=\sup_{\mathbf{P}_{X}}\sup_{\mathbf{P}_{UX}}\mathcal{L}_{\alpha}(U\rightarrow
Y)=\sup_{\mathbf{P}_{X}}I_{\alpha}^{\text{S}}(X;Y)$

which is exactly the channel capacity of order $\alpha$ [21]. It is denoted by
$\sup_{U-X-Y}\mathcal{L}_{\alpha}(U\rightarrow Y)$ in [4, Definition 6].

###  V-B $Y$-elementary $\alpha$-leakage

Consider the $Y$-elementary measure in (21) that is exactly the Rényi
divergence $D_{\alpha}(\mathbf{P}_{X|Y=y}\|\mathbf{P}_{X})$. For all
$\alpha\in(0,1)$,
$\exp\big{(}\frac{\alpha}{\alpha-1}\mathcal{L}_{\alpha}(X\rightarrow
y)\big{)}=\big{(}\sum_{x\in\mathcal{X}}P_{X}(x)\Big{(}\frac{P_{X|Y}(x|y)}{P_{X}(x)}\Big{)}^{\alpha}\big{)}^{1/\alpha}$
is called $\alpha$-lift in [23]. It also generalizes the pointwise maximal
leakage (PML) [15].

###### Corollary 1

At $\alpha=\infty$,

$\mathcal{L}_{\infty}(X\rightarrow
y)=\log\max_{x\in\text{supp}(P_{X})}\frac{P_{X|Y}(x|y)}{P_{X}(x)}$

is the pointwise maximal leakage (PML) [15] and the supremum in (18) is

$\displaystyle\sup_{\mathbf{P}_{UX}}\mathcal{L}_{\infty}(U\rightarrow Y)$
$\displaystyle=\log\mathbb{E}_{Y}\big{[}\exp\big{(}\mathcal{L}_{\infty}(X\rightarrow
y)\big{)}\big{]}$ (24)
$\displaystyle=\log\sum_{y\in\mathcal{Y}}\max_{x\in\text{supp}(P_{X})}P_{Y|X}(y|x).$

where $\log\sum_{y\in\mathcal{Y}}\max_{x\in\text{supp}(P_{X})}P_{Y|X}(y|x)$ is
proposed as the maximal leakage in [3]. ∎

Equation (24) states that the maximal leakage [3] is an $\tilde{f}$-mean of
PML [15].

###  V-C Comparison to $\alpha$-leakage in [4]

For the (elementary) loss function
$l_{\alpha}(P_{\hat{X}}(x))=\frac{\alpha}{\alpha-1}(1-P_{\hat{X}}^{\frac{\alpha-1}{\alpha}}(x))$
defined in [4, Section III-A], the corresponding $\alpha$-gain is
$g_{\alpha}(P_{\hat{X}}(x))=\frac{\alpha}{\alpha-1}P_{\hat{X}}^{\frac{\alpha-1}{\alpha}}(x)$.
An $\alpha$-leakage is proposed in [4, Definition 5] as the difference in the
logarithm of expected $\alpha$-gain between prior and posterior:

$\displaystyle\mathcal{L}_{\alpha}(U\rightarrow Y)$
$\displaystyle=\frac{\alpha}{\alpha-1}\log\frac{\max_{\mathbf{P}_{\hat{X}|Y}}\mathbb{E}_{XY}[g_{\alpha}(P_{\hat{X}|Y}(x))]}{\max_{\mathbf{P}_{\hat{X}}}\mathbb{E}_{X}[g_{\alpha}(P_{\hat{X}}(x))]}$
$\displaystyle=\frac{\alpha}{\alpha-1}\log\frac{\max_{\mathbf{P}_{\hat{X}|Y}}\mathbb{E}_{XY}[P_{\hat{X}|Y}^{\frac{\alpha-1}{\alpha}}(x)]}{\max_{\mathbf{P}_{\hat{X}}}\mathbb{E}_{X}[P_{\hat{X}}^{\frac{\alpha-1}{\alpha}}(x)]}.$
(25)

The coefficient $\frac{\alpha}{\alpha-1}$ before the logarithm is introduced
but not explained in [4] in terms of the measure itself. (25) also equals to
$I_{\alpha}^{\text{A}}(U;Y)$, but it is only defined in a partial range
$\alpha\in[1,\infty)$.999In fact, the leakage measure (25) can be extended to
the whole range $\alpha\in[0,\infty)$ by adopting our proposed $\alpha$-loss
in (14) that is well-supported by the interpretation of
$\frac{1-\alpha}{\alpha}$-power mean, which will lead to the proposed
$\alpha$-leakage definition in (17).

##  VI Conclusion

We revealed a $\tilde{f}$-mean cross entropy interpretation of Rényi entropy.
By a minimization of this cross entropy, an estimator’s best estimation rule
is determined. We used it to quantify the best-case uncertainty reduction an
adversary can achieve on estimating the sensitive attribute, by which an
$\alpha$-leakage is defined for the overall Rényi order range
$\alpha\in[0,\infty)$. We showed that the Sibson mutual information is a
$\tilde{f}$-mean of $\alpha$-order elementary leakage. This elementary leakage
generalizes PML. The difference between our measure and the existing
$\alpha$-leakage [4] for $\alpha\in[1,\infty)$ has been explained.

There are several directions for future works: (17) is in fact a
multiplicative uncertainty reduction $\mathcal{L}_{\alpha}(U\rightarrow
Y)=\frac{\alpha}{1-\alpha}\log\frac{\exp(\frac{1-\alpha}{\alpha}\min_{\mathbf{P}_{\hat{U}}}H_{\alpha}(\mathbf{P}_{U},\mathbf{P}_{\hat{U}}))}{\mathbb{E}_{Y}[\exp(\frac{1-\alpha}{\alpha}\min_{\mathbf{P}_{\hat{U}|Y=y}}H_{\alpha}(\mathbf{P}_{U|Y=y},\mathbf{P}_{\hat{U}|Y=y}))]}$.
A subtraction of uncertainty in codomain of $\tilde{f}$ can also be proposed
as leakage measure; Proposition 1 gives an interpretation of Sibson mutual
information [7, 13, 14] in privacy leakage. An operational meaning should also
provided as to what exactly Sibson mutual information measures. Further, the
relationship between $f$\- and $\tilde{f}$-mean should be explored: the
coefficient $\frac{\alpha}{\alpha-1}$ also appears after the minimization of
the $\alpha$-order measures in Sibson identity [13, 14].

## References

  * [1] F. du Pin Calmon and N. Fawaz, “Privacy against statistical inference,” in _Proceedings of 50th Annual Allerton Conference on Communication, Control, and Computing_ , Monticello, IL, 2012, pp. 1401–1408.
  * [2] G. Smith, _On the Foundations of Quantitative Information Flow_. Springer Berlin Heidelberg, 2009, pp. 288–302.
  * [3] I. Issa, A. B. Wagner, and S. Kamath, “An operational approach to information leakage,” _IEEE Transactions on Information Theory_ , vol. 66, no. 3, pp. 1625–1657, Mar. 2020.
  * [4] J. Liao, O. Kosut, L. Sankar, and F. du Pin Calmon, “Tunable measures for information leakage and applications to privacy-utility tradeoffs,” _IEEE Transactions on Information Theory_ , vol. 65, no. 12, pp. 8043–8066, Dec. 2019.
  * [5] A. Rényi, “On measures of entropy and information,” in _Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Contributions to the Theory of Statistics_ , vol. 4. University of California Press, 1961, pp. 547–562.
  * [6] S. Arimoto, “Information measures and capacity of order $\alpha$ for discrete memoryless channels,” _Topics in information theory_ , 1977.
  * [7] S. Verdú, “$\alpha$-mutual information,” in _Proceedings of Information Theory and Applications Workshop_ , San Diego, CA, 2015, pp. 1–6.
  * [8] R. Sibson, “Information radius,” _Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete_ , vol. 14, no. 2, pp. 149–160, 1969.
  * [9] G. R. Kurri, L. Sankar, and O. Kosut, “An operational approach to information leakage via generalized gain functions,” _IEEE Transactions on Information Theory_ , vol. 70, no. 2, pp. 1349–1375, Dec. 2023.
  * [10] T. Sypherd, M. Diaz, J. K. Cava, G. Dasarathy, P. Kairouz, and L. Sankar, “A tunable loss function for robust classification: Calibration, landscape, and generalization,” _IEEE Transactions on Information Theory_ , vol. 68, no. 9, pp. 6021–6051, Sep. 2022.
  * [11] N. Ding and F. Farokhi, “Developing non-stochastic privacy-preserving policies using agglomerative clustering,” _IEEE Transactions on Information Forensics and Security_ , pp. 3911–3923, Jun. 2020.
  * [12] F. Farokhi and N. Ding, “Measuring information leakage in non-stochastic brute-force guessing,” in _Proceedings of IEEE Information Theory Workshop_ , Riva del Garda, 2021, pp. 1–5.
  * [13] S. Verdú, “Error exponents and $\alpha$-mutual information,” _Entropy_ , vol. 23, no. 2, p. 199, Feb. 2021.
  * [14] B. Nakiboglu, “The Rényi capacity and center,” _IEEE Transactions on Information Theory_ , vol. 65, no. 2, pp. 841–860, Feb. 2019.
  * [15] S. Saeidian, G. Cervia, T. J. Oechtering, and M. Skoglund, “Pointwise maximal leakage,” _IEEE Transactions on Information Theory_ , vol. 69, no. 12, pp. 8054–8080, Dec. 2023.
  * [16] S. Fehr and S. Berens, “On the conditional Rényi entropy,” _IEEE Transactions on Information Theory_ , vol. 60, no. 11, pp. 6801–6810, Nov. 2014.
  * [17] G. Aishwarya and M. Madiman, “Remarks on Rényi versions of conditional entropy and mutual information,” in _Proceedings of IEEE International Symposium on Information Theory_ , Paris, 2019, pp. 1117–1121.
  * [18] ——, “Conditional Rényi entropy and the relationships between Rényi capacities,” _Entropy_ , vol. 22, no. 5, p. 526, May 2020.
  * [19] F. Valverde-Albacete and C. Peláez-Moreno, “The case for shifting the Rényi entropy,” _Entropy_ , vol. 21, no. 1, p. 46, Jan. 2019.
  * [20] F. C. Thierrin, F. Alajaji, and T. Linder, “On the Rényi cross-entropy,” in _Proceedings of 17th Canadian Workshop on Information Theory_ , Ottawa, ON, 2022, pp. 1–5.
  * [21] I. Csiszar, “Generalized cutoff rates and Rényi’s information measures,” _IEEE Transactions on Information Theory_ , vol. 41, no. 1, pp. 26–34, Jan. 1995.
  * [22] Y. Polyanskiy and S. Verdu, “Arimoto channel coding converse and Rényi divergence,” in _Proceedings of 48th Annual Allerton Conference on Communication, Control, and Computing_ , Monticello, IL, 2010, pp. 1327–1333.
  * [23] N. Ding, M. A. Zarrabian, and P. Sadeghi, “$\alpha$-information-theoretic privacy watchdog and optimal privatization scheme,” in _Proceedings of IEEE International Symposium on Information Theory_ , Melbourne, 2021, pp. 2584–2589.

##  Appendix A Proof of $\mathbf{P}_{X}^{*}=\mathbf{P}_{X_{\alpha}}$ in
Theorem 1

For $\alpha\in(1,\infty)$, the Lagrangian function is

$L(\mathbf{P}_{X},\lambda)=\sum_{x}P_{X}(x)\hat{P}_{X}^{\frac{\alpha-1}{\alpha}}(x)-\lambda\left(\sum_{x\in\mathcal{X}}\hat{P}_{X}(x)-1\right)$

For convex minimization, the Karush–Kuhn–Tucker condition is both necessary
and sufficient, where the solution of equality $\frac{\partial
L}{\partial\hat{P}_{X}(x)}=\frac{\alpha-1}{\alpha}P_{X}(x)\hat{P}_{X}^{-1/\alpha}(x)-\lambda=0$
determines the minimizer
$\hat{P}_{X}^{*}(x)=P_{X}^{\alpha}(x)\left(\frac{\alpha-1}{\alpha\lambda}\right)^{\alpha}$
for all $x$. With the constraint $\sum_{x\in\mathcal{X}}\hat{P}_{X}(x)=1$, we
have
$\left(\frac{\alpha\lambda}{\alpha-1}\right)^{\alpha}=\sum_{x\in\mathcal{X}}P_{X}^{\alpha}(x)$
being a normalizing factor. The solution for $\alpha\in(0,1)$ can be
calculated in the same way, which is again $\mathbf{P}_{X_{\alpha}}$. The
minimum is therefore $H_{\alpha}(\mathbf{P}_{X})$ for all
$\alpha\in[0,\infty)$.

##  Appendix B Rényi Probability

Define the _Rényi probability_ [16]

$\text{Ren}_{\alpha}(\mathbf{P}_{X})=\|P_{X}(\cdot)\|_{\alpha}^{\frac{\alpha}{\alpha-1}}=\Big{(}\sum_{x\in\mathcal{X}}P_{X}^{\alpha}(x)\Big{)}^{\frac{1}{\alpha-1}}.$
(26)

The Rényi entropy is the negative log-likelihood (log-loss) of Rényi
probability [16, 17, 18]

$H_{\alpha}(\mathbf{P}_{X})=-\log\text{Ren}_{\alpha}(\mathbf{P}_{X})$ (27)

In the same way, define Rényi probability for conditional probability
$\mathbf{P}_{X|Y}$ as an $\frac{\alpha-1}{\alpha}$-order power mean [16, 17,
18]:

$\displaystyle\text{Ren}_{\alpha}(\mathbf{P}_{X|Y})$
$\displaystyle=\Big{(}\mathbb{E}_{Y}\Big{[}\text{Ren}_{\alpha}(P_{X|Y=y})^{\frac{\alpha-1}{\alpha}}\Big{]}\Big{)}^{\frac{\alpha}{\alpha-1}}$
(28)
$\displaystyle=\Big{(}\mathbb{E}_{Y}\Big{[}\Big{(}\sum_{x\in\mathcal{X}}P_{X|Y}^{\alpha}(x|y)\Big{)}^{\frac{1}{\alpha}}\Big{]}\Big{)}^{\frac{\alpha}{\alpha-1}}$
$\displaystyle=\Big{(}\sum_{y\in\mathcal{Y}}P_{Y}(y)\Big{(}\sum_{x\in\mathcal{X}}P_{X|Y}^{\alpha}(x|y)\Big{)}^{\frac{1}{\alpha}}\Big{)}^{\frac{\alpha}{\alpha-1}}.$

The Arimoto conditional entropy [6] is also a log-loss of Rényi probability

$H_{\alpha}(\mathbf{P}_{X|Y})=-\log\text{Ren}_{\alpha}(\mathbf{P}_{X|Y}).$
(29)

It is clear from (28) that $\text{Ren}_{\alpha}(\mathbf{P}_{X|Y})$ is an
$\frac{\alpha-1}{\alpha}$-order power mean of $Y$-elementary Rényi probability
$\text{Ren}_{\alpha}(P_{X|Y=y})$. Whereas, our proposed $\alpha$-loss in (14)
is the reciprocal of an $\frac{\alpha-1}{\alpha}$-order power mean of
$X$-elementary measure: with $l_{\alpha}(P_{\hat{X}}(x))=P_{\hat{X}}^{-1}(x)$,

$\displaystyle L_{\alpha}(\mathbf{P}_{X},\mathbf{P}_{\hat{X}})$
$\displaystyle=\Big{(}\sum_{x}P_{X}(x)l_{\alpha}(P_{\hat{X}}(x))^{\frac{1-\alpha}{\alpha}}\Big{)}^{\frac{\alpha}{1-\alpha}}$
$\displaystyle=\Big{(}\Big{(}\sum_{x}P_{X}(x)P_{\hat{X}}^{\frac{\alpha-1}{\alpha}}(x)\Big{)}^{\frac{\alpha}{\alpha-1}}\Big{)}^{-1}.$

Here, $P_{\hat{X}}(x)$ measures the certainty incurred by each $X$-elementary
decision. The $\frac{\alpha-1}{\alpha}$-order power mean
$\Big{(}\sum_{x}P_{X}(x)P_{\hat{X}}^{\frac{\alpha-1}{\alpha}}(x)\Big{)}^{\frac{\alpha}{\alpha-1}}$
measures the expected certainty incurred by decision probability
$\mathbf{P}_{\hat{X}}$ w.r.t. $\mathbf{P}_{X}$, the reciprocal of which
measures the uncertainty and therefore is called $\alpha$-loss function. The
cross entropy proposed in Section III is in fact the log-loss of this
$\frac{\alpha-1}{\alpha}$-order power mean:

$H_{\alpha}(\mathbf{P}_{X},\mathbf{P}_{\hat{X}})=\log
L_{\alpha}(\mathbf{P}_{X},\mathbf{P}_{\hat{X}}),$

which can be seen from (10).


Finding Good Proofs for Answers to Conjunctive Queries Mediated by
Lightweight Ontologies (Technical Report)

Christian Alrabbaa Stefan Borgwardt Patrick Koopmann Alisa Kovtunova

§.§ Acknowledgments

This work was supported by DFG in grant 389792660, TRR 248
(<https://perspicuous-computing.science>), and QuantLA, GRK 1763

[1]
S. Abiteboul, R. Hull, and V. Vianu.
Foundations of Databases.
Addison-Wesley, 1995.

[2]
C. Alrabbaa, F. Baader, S. Borgwardt, P. Koopmann, and A. Kovtunova.
Finding small proofs for description logic entailments: Theory and
In E. Albert and L. Kovacs, editors, LPAR-23: 23rd International
Conference on Logic for Programming, Artificial Intelligence and Reasoning,
volume 73 of EPiC Series in Computing, pages 32–67. EasyChair, 2020.

[3]
C. Alrabbaa, F. Baader, S. Borgwardt, P. Koopmann, and A. Kovtunova.
On the complexity of finding good proofs for description logic
In S. Borgwardt and T. Meyer, editors, Proceedings of the 33rd
International Workshop on Description Logics (DL'20), volume 2663 of CEUR Workshop Proceedings, 2020.

[4]
C. Alrabbaa, F. Baader, S. Borgwardt, P. Koopmann, and A. Kovtunova.
Finding good proofs for description logic entailments using recursive
quality measures.
In A. Platzer and G. Sutcliffe, editors, Proceedings of the 28th
International Conference on Automated Deduction (CADE'21), volume 12699 of
LNCS, pages 291–308, 2021.

[5]
C. Alrabbaa, F. Baader, R. Dachselt, T. Flemisch, and P. Koopmann.
Visualising proofs and the modular structure of ontologies to support
ontology repair.
In S. Borgwardt and T. Meyer, editors, Proceedings of the 33rd
International Workshop on Description Logics (DL 2020), volume 2663 of
CEUR Workshop Proceedings. CEUR-WS.org, 2020.

[6]
C. Alrabbaa, W. Hieke, and A. Turhan.
Counter model transformation for explaining non-subsumption in EL.
In C. Beierle, M. Ragni, F. Stolzenburg, and M. Thimm, editors, Proceedings of the 7th Workshop on Formal and Cognitive Reasoning, volume
2961 of CEUR Workshop Proceedings, pages 9–22. CEUR-WS.org, 2021.

[7]
R. Alur and T. A. Henzinger.
A really temporal logic.
J. ACM, 41(1):181–204, 1994.

[8]
F. Baader.
Terminological cycles in a description logic with existential
In G. Gottlob and T. Walsh, editors, IJCAI-03, Proceedings of
the Eighteenth International Joint Conference on Artificial Intelligence,
pages 325–330. Morgan Kaufmann, 2003.

[9]
F. Baader, S. Borgwardt, P. Koopmann, A. Ozaki, and V. Thost.
Metric temporal description logics with interval-rigid names.
In Proc. of the 11th Int. Symp. on Frontiers of Combining
Systems (FroCoS'17), pages 60–76. Springer, 2017.

[10]
F. Baader, R. Peñaloza, and B. Suntisrivaraporn.
Pinpointing in the description logic $\mathcal{EL}^+$.
In KI 2007: Advances in Artificial Intelligence, 30th Annual
German Conference on AI, KI 2007, pages 52–67, 2007.

[11]
A. Borgida, D. Calvanese, and M. Rodriguez-Muro.
Explanation in the DL-Lite family of description logics.
In R. Meersman and Z. Tari, editors, On the Move to Meaningful
Internet Systems: OTM 2008, volume 5332 of Lecture Notes in Computer
Science, pages 1440–1457. Springer, 2008.

[12]
A. Borgida, E. Franconi, and I. Horrocks.
Explaining $\mathcal{ALC}$ subsumption.
In ECAI 2000, Proceedings of the 14th European Conference on
Artificial Intelligence, pages 209–213, 2000.

[13]
S. Borgwardt, W. Forkel, and A. Kovtunova.
Finding new diamonds: Temporal minimal-world query answering over
sparse ABoxes.
In Proc. of the 3rd Int. Joint Conf. on Rules and Reasoning,
RuleML+RR 2019, volume 11784 of LNCS, pages 3–18. Springer, 2019.

[14]
S. Borgwardt, W. Forkel, and A. Kovtunova.
Temporal minimal-world query answering over sparse ABoxes.
Theory Pract. Log. Program., 22(2):193–228, 2022.

[15]
C. Bourgaux, A. Ozaki, R. Peñaloza, and L. Predoiu.
Provenance for the description logic elhr.
In C. Bessiere, editor, Proceedings of the Twenty-Ninth
International Joint Conference on Artificial Intelligence, IJCAI 2020,
pages 1862–1869. ijcai.org, 2020.

[16]
S. Brandt, E. G. Kalaycı, V. Ryzhikov, G. Xiao, and M. Zakharyaschev.
Querying log data with metric temporal logic.
J. Artif. Intell. Res., 62:829–877, 2018.

[17]
A. Calì, G. Gottlob, and T. Lukasiewicz.
A general datalog-based framework for tractable query answering over
J. Web Semant., 14:57–83, 2012.

[18]
D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, and R. Rosati.
Tractable reasoning and efficient query answering in description
logics: The DL-Lite family.
J. of Automated Reasoning, 39(3):385–429, 2007.

[19]
D. Calvanese, D. Lanti, A. Ozaki, R. Peñaloza, and G. Xiao.
Enriching ontology-based data access with provenance.
In S. Kraus, editor, Proceedings of the Twenty-Eighth
International Joint Conference on Artificial Intelligence, IJCAI 2019,
pages 1616–1623. ijcai.org, 2019.

[20]
D. Calvanese, M. Ortiz, M. Simkus, and G. Stefanoni.
The complexity of explaining negative query answers in dl-lite.
In G. Brewka, T. Eiter, and S. A. McIlraith, editors, Principles
of Knowledge Representation and Reasoning: Proceedings of the Thirteenth
International Conference, KR 2012. AAAI Press, 2012.

[21]
İ. İ. Ceylan, T. Lukasiewicz, E. Malizia, C. Molinaro, and
A. Vaicenavicius.
Explanations for negative query answers under existential rules.
In D. Calvanese, E. Erdem, and M. Thielscher, editors, Proceedings of KR 2020, pages 223–232. AAAI Press, 2020.

[22]
F. Croce and M. Lenzerini.
A framework for explaining query answers in DL-Lite.
In C. Faron-Zucker, C. Ghidini, A. Napoli, and Y. Toussaint,
editors, Knowledge Engineering and Knowledge Management - 21st
International Conference, EKAW 2018, volume 11313 of Lecture Notes in
Computer Science, pages 83–97. Springer, 2018.

[23]
R. Fagin, P. G. Kolaitis, R. J. Miller, and L. Popa.
Data exchange: semantics and query answering.
Theor. Comput. Sci., 336(1):89–124, 2005.

[24]
G. Gottlob, S. Kikot, R. Kontchakov, V. V. Podolskii, T. Schwentick, and
M. Zakharyaschev.
The price of query rewriting in ontology-based data access.
Artif. Intell., 213:42–59, 2014.

[25]
V. Gutiérrez-Basulto, J. C. Jung, and A. Ozaki.
On metric temporal description logics.
In Proc. ECAI, pages 837–845. IOS Press, 2016.

[26]
M. Horridge.
Justification Based Explanation in Ontologies.
PhD thesis, University of Manchester, UK, 2011.

[27]
M. Horridge, B. Parsia, and U. Sattler.
Justification oriented proofs in OWL.
In The Semantic Web - ISWC 2010 - 9th International Semantic
Web Conference, ISWC 2010, Part I, pages 354–369, 2010.

[28]
N. Immerman.
Descriptive Complexity.
Springer, 1999.

[29]
H. W. Kamp.
Tense Logic and the Theory of Linear Order.
PhD thesis, Computer Science Department, University of California
at Los Angeles, USA, 1968.

[30]
Y. Kazakov, P. Klinov, and A. Stupnikov.
Towards reusable explanation services in protege.
In A. Artale, B. Glimm, and R. Kontchakov, editors, Proc. of
the 30th Int. Workshop on Description Logics (DL'17), volume 1879 of CEUR Workshop Proceedings, 2017.

[31]
Y. Kazakov, M. Krötzsch, and F. Simancik.
The incredible ELK - From polynomial procedures to efficient
reasoning with $\mathcal{EL}$ ontologies.
J. Autom. Reason., 53(1):1–61, 2014.

[32]
P. Koopmann.
Signature-based abduction with fresh individuals and complex concepts
for description logics.
In Z. Zhou, editor, Proceedings of the Thirtieth International
Joint Conference on Artificial Intelligence, IJCAI 2021, pages 1929–1935.
ijcai.org, 2021.

[33]
D. L. McGuinness.
Explaining Reasoning in Description Logics.
PhD thesis, Rutgers University, NJ, USA, 1996.

[34]
L. R. Nielsen, K. A. Andersen, and D. Pretolani.
Finding the K shortest hyperpaths.
Computers & OR, 32:1477–1497, 2005.

[35]
R. Peñaloza.
Axiom-Pinpointing in Description Logics and Beyond.
PhD thesis, Technische Universität Dresden, Germany, 2009.

[36]
R. Rosati.
On conjunctive query answering in EL.
In D. Calvanese, E. Franconi, V. Haarslev, D. Lembo, B. Motik,
A. Turhan, and S. Tessaris, editors, Proceedings of the 2007
International Workshop on Description Logics (DL2007), volume 250 of CEUR Workshop Proceedings. CEUR-WS.org, 2007.

[37]
S. Schlobach and R. Cornet.
Non-standard reasoning services for the debugging of description
logic terminologies.
In G. Gottlob and T. Walsh, editors, Proc. of the 18th Int.  Joint Conf. on Artificial Intelligence (IJCAI 2003), pages 355–362. Morgan
Kaufmann, 2003.

[38]
G. Stefanoni.
Explaining query answers in lightweight ontologies.
Diploma thesis, Technische Universität Wien, 2011.

[39]
P. A. Walega, B. C. Grau, M. Kaminski, and E. V. Kostylev.
Datalogmtl: Computational complexity and expressive power.
In S. Kraus, editor, Proceedings of the Twenty-Eighth
International Joint Conference on Artificial Intelligence, IJCAI 2019,
pages 1886–1892. ijcai.org, 2019.

[40]
P. A. Walega, B. C. Grau, M. Kaminski, and E. V. Kostylev.
Tractable fragments of datalog with metric temporal operators.
In C. Bessiere, editor, Proceedings of the Twenty-Ninth
International Joint Conference on Artificial Intelligence, IJCAI 2020,
pages 1919–1925. ijcai.org, 2020.

§ ADDITIONAL DEFINITIONS: HYPERGRAPHS

A (directed, labeled) hypergraph [34] is a triple $H=(V,E,\el)$, where

* $V$ is a set of vertices,

* $E$ is a set of hyperedges $(S,d)$ with a tuple of source vertices $S$
target vertex $d\in V$, and

* $\el\colon V\to \mathcal{S}_\L$ is a labeling function that assigns sentences to

We extend the function $\ell$ to hyperedges as follows: $\ell(S,d):=\big((\ell(s))_{s\in S},\ell(d)\big)$.

For finite $V$, the size of $H$, denoted $|H|$, is measured by the size of the labels of
its hyperedges:
$$\card{H}:=\sum_{(S,d)\in E}\card{(S,d)}, \text{ where } \card{(S,d)}:=\card{\el(d)}+\sum_{v\in

A vertex $v\in V$ is called a leaf if it has no incoming hyperedges, there is no
$(S,v)\in E$; and $v$ is a sink if it has no outgoing hyperedges, there is no $(S,d)\in
E$ such that $v\in S$. We denote the set of all leafs and the set of all sinks in $H$ as
$\leaf(H)$ and $\sink(H)$, respectively.

A hypergraph $H'= (V', E', \el')$ is called a subgraph of $H= (V, E, \el)$ if $V'\subseteq V$, $E'\subseteq E$ and $\el'=\el|_{V'}$.
In this case, we also say that $H$ contains $H'$ and write $H' \subseteq H$.

Given two hypergraphs $H_1=(V_1,E_1,\el_1)$ and $H_2=(V_2,E_2,\el_2)$ $\el_1(v)=\el_2(v)$ for every $v\in V_1\cap V_2$, the union of the two hypergraphs is
defined as $H_1 \cup H_2:=$ $(V_1\cup V_2,E_1\cup E_2, \el_1 \cup \el_2)$.

Given a hypergraph $H=(V,E,\el)$ and $s,t\in V$, a path $P$ of length $q\geq 0$ in $H$ from $s$ to $t$ is a sequence of vertices and

\[ P=(d_0,i_1,(S_1,d_1),d_1,i_2,(S_2,d_2),\dots, d_{q-1},i_q,(S_q,d_q),d_q), \]

where $d_0=s$, $d_q=t$, and $d_{j-1}$ occurs in $S_j$ at the $i_j$-th position, for all $j$, $1\le j\le q$. If
there is such a path of length $q > 0$ in $H$, we say that $t$ is reachable from $s$
in $H$.
If $t = s$, then $P$ is called a cycle.

The hypergraph $H$ is acyclic if it does not contain a cycle.

The hypergraph $H$ is connected if

every vertex is connected to every other vertex by a series of paths and reverse paths.

A hypergraph $H=(V,E,\el)$ is called a tree with root $t\in V$ if $t$ is reachable
from every vertex $v\in V\setminus\{t\}$ by exactly one path. In particular, the root is the only
sink in a tree, and all trees are acyclic and connected.

Let $H=(V,E,\el)$, $H'=(V',E',\el')$ be two hypergraphs.  A homomorphism from $H$ to
$H'$, denoted $h\colon H\rightarrow H'$, is a mapping $h\colon V\to V'$ s.t. for
all $(S,d)\in E$, one has $h(S,d):=\big((h(v))_{v\in S},\,h(d)\big)\in E'$ and, for all $v\in V$, it
holds that $\el'(h(v))=\el(v)$.

Such an $h$ is an isomorphism if it is a bijection, and its inverse, $h^-\colon H' \to H$,
is also a homomorphism.

The unraveling of an acyclic hypergraph $H=(V,E,\ell)$ at a vertex $v\in V$ is the tree
$H_T=(V_T,E_T,\ell_T)$, where $V_T$ consists of all paths in $H$ that end in $v$, $E_T$
contains all hyperedges $((P_1,\dots,P_n),P)$ where each $P_i$ is of the
form $\big(d_i,i,((d_1,\dots,d_n),d)\big)\cdot P$, and $\ell_T(P)$ is the label of the starting
vertex of $P$ in $H$.

Moreover, the mapping $h_T\colon V_T\to V$ that maps each path to its starting vertex (and in
particular $h_T(v)=v$) is a homomorphism from $H_T$ to $H$.

The tree size $\mtree(\p)$ of a proof is defined recursively as follows:

\begin{align*}
\mtree(v)&:=1 &&\text{for every leaf }v, \\
\mtree(d)&:=1+\sum_{v\in S} \mtree(v), &&\text{for every }(S,d)\in E, \\
\mtree(\p)&:=\mtree(v), &&\text{for the sink vertex }v.
\end{align*}

This recursively counts the vertices in subproofs and is equal to the size of a tree unraveling of .

§ PROOF DETAILS

§.§ Derivation Structures

Assume that we have a proof $\p$ in $\Rcq(\Tmc\cup\Amc,\q(\vec{a}))$.

We first defer all applications of schema to the very end of the proof, which is possible since all other inferences remain applicable to any instance $\exists\vec{x}.\,\phi(\vec{x},\vec{a})$ of a CQ $\exists\vec{x},\vec{y}.\,\phi(\vec{x},\vec{y})$. This transformation can only decrease the size of the proof.

We then recursively change the labeling function so that it uses
Skolem terms rather than quantified variables. Specifically, starting from the leafs of , we adapt
inferences of schema so that instead of a rule
$\psi(\vec{y},\vec{z})\to\exists\vec{u}.\,\chi(\vec{z},\vec{u})\in\Tmc$, the
corresponding Skolemized version
$\psi(\vec{y},\vec{z})\to\chi'(\vec{z})\in\Tmc^s$ is used, with existentially
quantified variables in the conclusion replaced by the corresponding Skolem
terms. The resulting hypergraph has the same size, since we only changed the
labeling, and moreover all CQs are ground.

In this process, whenever we apply a rule $\phi(\vec{x},\vec{y})\to\exists\vec{x}.\,\phi(\vec{x},\vec{y})$ generated by to a ground CQ using , we can omit this subproof since $\exists\vec{x}.\,\phi(\vec{x},\vec{y})$ is satisfied by the same ground atoms used to match $\phi(\vec{x},\vec{y})$.

Next, we split each modified inference into a corresponding set of inferences – this replaces each vertex $v$ by at most $|\Tmc|$ vertices (at most for each new atom derived from the right-hand size of a rule in ),

and thus increases the size of the hypergraph by a factor polynomial in the size of $\p$.

Even though contains no version of the inference schema to generate copies of atoms, we can always use the same ground atom several times in the same inference if necessary.

At the same time, we remove all inferences (since anyway uses multiple
premises instead of a conjunction) and replace them by a single application of (conjoining all atoms relevant for $\q(\vec{a})$).

This can also only decrease the size of the proof.

Similarly, the final step becomes an instance of that produces the final conclusion $\q(\vec{a})$.

We obtain a proof in $\Rsk(\Tmc^s\cup\Amc,\q(\vec{a}))$ that is of size polynomial in the size of $\p$.

Now assume that we have a proof $\p$ in $\Rsk(\Tmc^s\cup\Amc,\q(\vec{a}))$.
We transform $\p$ into a semi-linear proof in $\Rsk(\Tmc\cup\Amc,\q(\vec{a}))$.
In the beginning, we keep the Skolemization, which is eliminated in the last step.
We first collect any
ABox assertions from $\Amc$ that are used in $\p$ into a single CQ using .
Then we aggregate inferences of into -inferences. Specifically,
provided that for an $\gMOPO$ inference $(S,d)$, all labels of nodes in $S$
occur on a node $v$ that we have already aggregated, we collect all inferences
of the form $(S,d')$ (same premises, different conclusion), and transform them
into a single inference using (a Skolemized version of) .

When $S$ contains the same atom multiple times, we first generate an appropriate number of copies using and ; the number of such additional proof steps for each -inference is bounded by $|\Tmc|$ (more precisely, the maximum number of atoms on the left-hand side of any rule in ).

Depending on which premises are still
needed in later inferences, we keep them in the conclusion of each -inference or not. Since we
keep all atoms together in each step, the final application of is not
needed anymore. The resulting proof is de-Skolemized by replacing Skolem terms
by existentially quantified variables again using . The output of this transformation
is again polynomial in the size of the original proof: the number of initial
applications of is bounded by the size of $\p$, the aggregated -steps can only decrease the size of the proof, and for each of these steps, we need at most $|\Tmc|$ additional - and -steps.

§.§ Atemporal Queries

Fix a set $\NC^n$ of $\leq n$ individual names, and collect in
$\mathfrak{A}$ all of the (constantly many) ABoxes $\Amc$ using only names from
$\sig(\Tmc)\cup\NC^n$ and $\a$ for which $\R(\Tmc\cup\Amc,\q(\a))$ contains
a proof of (tree) size $\leq n$; the latter could be done, by simple breadth-first search for proofs up to size $n$.
We can identify every such ABox $\Amc$ with a
CQ $q_\Amc(\a)$ obtained by replacing individual names not in $\a$ by
existentially quantified variables. We now have that, for any ABox $\Amc$, there
exists an $\Amc'\in\mathfrak{A}$ with $\Amc\models q_{\Amc'}(\a)$ iff there
exists a proof for $\Tmc\cup\Amc\models \q(\a)$ of (tree) size at most $n$.
Consequently, we can reduce the decision problem in the theorem to deciding
whether $\Amc$ entails the (fixed) union of conjunctive queries (UCQ)

\[
\bigvee_{\Amc\in\mathfrak{A}}q_\Amc(\a).
\]

Deciding UCQ entailment without a TBox is possible in in data complexity [1].

Let $Q(\vec{x})$ be a UCQ that is a rewriting of $\q(\vec{x})$ and , such that $\Tmc\cup\Amc\models\q(\a)$ is equivalent to $\Amc\models Q(\a)$ for all ABoxes .

For every CQ $q'(\a)\in Q(\a)$, we can
determine the minimal proof (tree) size $n_{q'}$ for $\Tmc\cup\Amc_{q'}\models
\q(\a)$, where $\Amc_{q'}$ is obtained from $q'(\a)$ by replacing every variable
by a fresh individual name.

These ABoxes represent all possibilities of an ABox entailing $\q(\a)$ w.r.t. (up to isomorphism), and hence they can be used as (a fixed number of) representatives in the search for small proofs of the entailment.

The computation of $n_{q'}$ does not depend on the input data, and hence can be done offline via search in the derivation structure.

Let $n_\textit{max}$ be the maximum of the values $n_{q'}$. To
every $n\leq n_\textit{max}$, we assign the UCQ

\[
Q_n=\bigvee\{q'\in Q\mid n_{q'}\leq n\}
\]

Given $\Amc$, $\a$, and $n$, we can now decide whether $\Tmc\cup\Amc\models
\q(\a)$ admits a proof of (tree) size $\leq n$ by 1) computing the UCQ $Q_{n'}$
for $n'=\min(n,n_\textit{max})$, and 2) checking whether $\Amc\models
2) is the standard query answering problem which has data complexity. To see that the combined task 1)+2) can be done in , we
note that $n_\textit{max}$ does not depend on the data, so that we only need to
process the least $\log_{n_\textit{max}}$ bits of $n$ to determine $n'$, which
can be done by a circuit of constant depth.

and only need to be applied once, at the very end, to produce
the query $\q(\vec{a})$. For , the remaining rule is such that it
always has one premise that is a CQ. Consequently, we can always construct a
proof that is composed of $\lvert\q(\vec{x})\rvert$ linear proofs (one for each
atom), which are then connected using $\gCONJ$ and produce the conclusion with
As argued in the main text, we can assume that the nesting depth
of Skolem terms is polynomially bounded by $\lvert\Tmc\rvert$, which means the
number of labels on each path is polynomially bounded by $\lvert\Tmc\rvert$ as

Additionally, we can always simplify any
proof in which the same label occurs twice along some path, which means that
this polynomial bound transfers also to the depth of our proof. We obtain that
we can always find a proof of polynomial tree size.

The upper bound is shown in the main text, but it still remains to show a matching
lower bound.

We reduce the problem of query answering to the given problem. Specifically,
let $\tup{\Tmc,\Amc}$ be a DL-Lite KB, $\q(\vec{x})$ a query and $\vec{a}$ such
that $\lvert{x}\rvert=\lvert{a}\rvert$, and suppose we want to determine whether
$\Tmc\cup\Amc\models \q(\vec{a})$. We know by Lemma <ref>
if $\Tmc\cup\Amc\models \q(\vec{a})$, then there exists a proof for this
in $\Rsk(\Tmc\cup\Amc, \q(\vec{a}))$
is of (tree) size at most $n=p(\lvert{\Tmc}\rvert,\lvert\q(\vec{x})\rvert)$, where $p$ is some
polynomial. By using
Lemma <ref>, we can also find such a polynomially bounded
number $n$ in case $\R=\Rcq$.

We now
construct a new KB $\Tmc_0\cup\Amc_0$ such that $\Tmc_0\cup\Amc_0\models
\q(\vec{x})$, but only with a proof of (tree) size $>n$.
$\Amc_0$ is obtained from the atoms of $\q(\a)$ by replacing every quantified variable by a fresh individual name, and each predicate $P$ by $P_0$.

$\Tmc_0$ contains for
predicate $P$ occurring in $\q$ and every $i\in\{0,\ldots,n\}$ the CI
$P_{i}\sqsubseteq P_{i+1}$, as well as $P_n\sqsubseteq P$. Clearly,
$\Tmc_0\cup\Amc_0\models \q(\vec{a})$, and every proof for this corresponds to a
tree of depth $n+1$, and is thus larger than $n$. Moreover, $\Tmc_0$,
$\Amc_0$, and $n$ are all of polynomial size in the size of the input to the query answering problem.
Now set $\Tmc_1=\Tmc_0\cup\Tmc$, $\Amc_1=\Amc_0\cup\Amc$. We have
$\Tmc_1\cup\Amc_1\models \q(\a)$; however, a proof of (tree) size $\leq n$ exists in
$\R(\Tmc_1\cup\Amc_1,\q(\a))$ iff $\Tmc\cup\Amc\models\q(\a)$.

We construct a compressed version of $\Rsk(\Tmc\cup\Amc,\q(\vec{a}))$ of
polynomial size.

We introduce for every role $R$ the individual name $b_{\exists R}$.
Our compressed derivation structure is defined inductively as follows, where
for a role name $P$, we identify $P^-(a,b)$ with $P(b,a)$ and $(P^-)^-$ with $P$.

* every axiom $\alpha\in\Tmc\cup\Amc$ has a node $v_\alpha$ with

* for nodes $v_1$, $v_2$ with $\el(v_1)=A(a)$ and $\el(v_2)=A\sqsubseteq
B$ there is an edge $(\{v_1,v_2\},v_3)$, where $\el(v_3)=B(a)$.

* for nodes $v_1$, $v_2$ with $\el(v_1)=P(a,b)$ and
$\el(v_2)=P\sqsubseteq Q$, there is an edge $(\{v_1,v_2\},v_3)$ with

* for nodes $v_1$, $v_2$ with $\el(v_1)=A(a)$ and
$\el(v_2)=A\sqsubseteq\exists P$, there is an edge $(\{v_1,v_2\},v_3)$
with $\el(v_3)=P(a,b_{\exists P^-})$,

* for nodes $v_1$, $v_2$ with $\el(v_1)=P(a,b)$ and
$\el(v_2)=\exists P\sqsubseteq A$, there is an edge $(\{v_1,v_2\},v_3)$
with $\el(v_3)=A(a)$,

* for nodes $v_1$, $v_2$ with $\el(v_1)=P(a,b)$ and
$\el(v_2)=\exists P\sqsubseteq\exists Q$, there is an edge
with $\el(v_3)=Q(a,b_{\exists Q^-})$.

Due to the conclusions with the fresh individual names, the inferences in this
compressed derivation structure are not sound, so that it is not really a
derivation structure. But because its size is polynomial, we can use the procedure from <cit.> to compute for every node $v$ a proof of
minimal size. To use these proofs to construct a tree proof in $\Rsk(\Tmc\cup\Amc,\q(\vec{a}))$,
we still need to match the variables in $\q(\vec{a})$ to the constants in the
derivation structure.

For every pair $\tup{t_1,t_2}$ of terms occurring in $\q(\vec{a})$ together in
an atom, and every possible assignment $(t_1\mapsto a_1, t_2\mapsto a_2)$ of
these terms to individual names from the compressed derivation structure, we
assign a cost $\gamma(t_1\mapsto a_1, t_2\mapsto a_2)$ that is the sum of the
minimal proof sizes for every atom in $\q(\vec{a})$ that contains only $t_1$
and $t_2$, with these terms replaced using the assignment. We build a labeled
graph, the cost graph, with every node a mapping from one term in
$\q(\vec{a})$ to one constant in our compressed derivation structure, and every
edge between two nodes $(t_1\mapsto a_1)$ and $(t_2\mapsto a_2)$ labeled with
the cost $\gamma(t_1\mapsto a_1, t_2\mapsto a_2)$ (no edge if there is no edge
between $t_1$ and $t_2$ in the Gaifman graph). Every edge in the cost graph
corresponds to an edge in the Gaifman graph of $\q(\vec{a})$, but the same edge
in the Gaifman graph can be represented by several edges in the cost graph.
We can thus transform the cost graph into a directed acyclic graph, making
sure that for every edge $(t_1\mapsto a_1, t_2\mapsto a_2)$, the edge
$(t_1,t_2)$ points from the root towards the leafs of the Gaifman graph, where
we choose an arbitrary node as the root.

We now eliminate assignments from the cost graph starting from the leafs:

* Consider a node $(t_1\mapsto a_1)$ and for some term $t_2$,
all outgoing edges of the form $(t_1\mapsto a_1, t_2\mapsto a_2)$. Once all
the nodes $t_2\mapsto a_2$ have already been visited by the algorithm, assign to
each edge $(t_1\mapsto a_1,t_2\mapsto a_2)$ a combined cost obtained by adding
to $\gamma(t_1\mapsto a_1,t_2\mapsto a_2)$ the costs of every edge reachable
from $(t_2\mapsto a_2)$, and remove all edges for which the resulting value is
not minimal. In case several edges have a minimal value assigned, choose an
arbitrary edge to remove, so that we obtain a unique edge $(t_1\mapsto a_1,
t_2\mapsto a_2)$ for $t_1\mapsto a_1$ and $t_2$.

* If an assignment $(t\mapsto a)$ has no incoming edges, remove it from
the cost graph.

The algorithm processes each edge in the polynomially sized cost graph at most
once, and thus terminates after a polynomial number of steps with an assignment
of variables to constants appearing in the compressed derivation structure.
We can use this assignment to first construct a minimal proof for $\q(\a)$ over the
compressed derivation structure, where every atom in $\q(\a)$ has its own
independent minimal proof. Note that we cannot obtain a smaller proof in
$\q(\a)$, since every atom has a minimal proof assigned, and our elimination
procedure made sure that there cannot be a different choice of assignments of
terms in $\q(\a)$ to constants that would lead to smaller proofs anywhere else.

We then replace every constant with the
corresponding term in  $\Rsk(\Tmc\cup\Amc,\q(\a))$, starting from the original
individual names and following the structure of the proof, to obtain the desired
proof of minimal tree size.

For example, we would replace an atom $P(a,b_{\exists P^-})$ that is derived in
the proof from $A(a)$ and $A\sqsubseteq\exists P$ by $P(a,f(a))$, where $f$ is
the Skolem function for the existentially quantified variable in
$A\sqsubseteq\exists P$, and replace $b_{\exists P^-}$ by $f(a)$ also in
subsequent proof steps, provided it refers to a successor of $a$. More
generally, we replace $P(t,b_{\exists P^-})$ , where $t$ is already a Skolem
term, by $P(t,f(t))$, whenever it is derived from $A(t)$ and
$A\sqsubseteq\exists P$.

We prove Theorem <ref> in the following two lemmas.
For tree-shaped CQs, $\OPx'(\Lmc,\mtree)$ and $\OP\sk(\Lmc,\msize)$ are -hard.

We reduce SAT to $\OPx'(\Lmc,\mtree)$. Let $c_1,\ldots,c_m$ be a set of clauses
over propositional variables $p_1,\ldots,p_n$. Each clause $c_i$ is a disjunction
of literals of the form $p_j$ or $\overline{p_j}$, where the latter denotes the
negation of $p_j$. In the following, we assume clauses to be represented as sets of literals.
we assume that for every
variable $p_i$, we also have the clause $p_i\vee\overline{p_i}$. For every variable $p_i$,
we add the assertions $T(p_i)$ and $T(\overline{p}_i)$.

For every clause $c_i$ and every literal $l_j\in c_i$, we add an assertion

Furthermore, if $i<m$, we add the role
assertion $r(c_i,c_{i+1})$. The conjunctive query $\q$ is Boolean and contains
for every clause $c_i$ the atoms
c(x_i^{(c)}, x_i^{(p)}), T(x_i^{(p)})
%\ \ t(x_i^{(p)}, x_i^{(t)}),\ \ T(x_i^{(t)}),\ \
%f(x_i^{(p)}, x_i^{(f)}),\ \ F(x_i^{(f)}),
and moreover, if $i<m$, $r(x_i^{(c)}, x_{i+1}^{(c)})$,

so that the query is

We have
$\Amc\models \q$ independently of whether the SAT problem has a
solution or not.

We set our bound as $k=2+m+(m-1)+n$, which distributes as follows in a proof
if the set of clauses is satisfiable. Assume that $a:\{p_1,\ldots,p_n\}\rightarrow\{0,1\}$ is
a satisfying assignment for our set of clauses.

* 2 vertices are needed for the conclusions of and ,

* $m$ vertices contain, for each clause $c_i$, the atom $c(c_i, l)$, where $l\in c_i$
is made true by the assignment $a$,

* $m-1$ vertices contain the atom $r(c_i,c_{i+1})$ for each $i\in\{1,\ldots

* for each variable $p_i$, depending on whether $a(p_i)=1$ or $a(p_i)=0$,
we use either $T(p_i)$ or $T(\overline{p}_i)$. This needs another $n$ vertices.

Note that there cannot possibly be a smaller proof, since every atom in the
query needs to be matched by some ABox assertion. Correspondingly, if the
SAT problem has a solution, we can construct a proof of the desired tree size in $\Rsk'$, and
if there is a proof of the desired tree size, we can extract a solution for the SAT problem
from it. It follows that the problem is -hard.

The same arguments apply to the original deriver since a single atom $T(p_i)$ or $T(\overline{p}_i)$ can be used multiple times in one application of , but is only counted once.

For tree-shaped CQs, $\OP\cq(\Lmc,\mtree)$ is -hard.

The central observation is that we can simulate in the behavior of
$\gEXISTSb$ when copying atoms. Specifically, fix an inference of $\gEXISTSb$
with premise $\phi(\vec{t})$, conclusion $\exists\vec{x}.\,\phi'(\vec{x})$ and
substitution $\sigma$ s.t. $\exists\vec{x}.\,\phi'(\vec{x})\sigma=\phi(\vec{t})$, and
let $\alpha(\vec{x_1})$, $\alpha(\vec{x_2})\in\phi'(\vec{x})$ be such that

To obtain a similar effect in $\Rcq$, we
would use to derive
$\alpha(\vec{x_1})\rightarrow\exists\vec{x_1}.\,\alpha(\vec{x_1})$, which is then used
with and the current CQ to obtain a query in which both
$\alpha(\vec{x_1})$ and $\alpha(\vec{x_2})$ occur (recall can be used
in such a way that the new atoms are not replacing others, but are simply
added). Note that this way, we can duplicate an arbitrary number of variables
using two steps.
Let $\Amc$ and $\q$ be as in the proof of Lemma <ref>, and assume
the SAT-problem has a satisfying assignment $a$.

We can then
construct a tree proof as follows, where this time, we collect the different atoms
one after using $\CONJ$ into a single query. Since these inferences always have two
premises, we only count the leaves in the following, as a binary tree with $n$ leaves and all
other vertices binary always has $2n-1$ vertices in total. Specifically, this means that the
number of vertices is independent on how we organize the inferences listed in the following.

* We need to collect all clauses of the form $r(c_i,c_{i+1})$, and $c(c_i,l_j)$, where
$l_i$ is some literal in $c_i$ evaluate to true under the chosen assignment $a$. This gives
$2m-1$ leaves,

* Another $n$ leaves are needed to add, for each variable $p_i$, $T(p_i)$ if $a(p_i)=1$,
and $T(\overline{p}_i)$ if $a(p_i)=0$.

Since this makes $2m-1+n$ leaves, we obtain that the corresponding proof must have
$4m+2n-3$ nodes in total, independently on how we organize these inferences. We instantiate
with $\q(\vec{x})\rightarrow\exists\vec{x}\q(\vec{x})$, where
$\q(\vec{x})$ is our query, containing as quantified variables exactly $\vec{x}$.
Since the left hand side matches our ground query constructed so far, we apply it
as final step to produce the conclusion, obtaining a tree proof of size $4+2n-1$.

Similar as before, we argue that there cannot be possibly a smaller proof for the query, since
every leaf of this proof has to be used. Consequently, if we find a proof of tree size $4+2n-1$, we
can construct a satisfying assignment from it, and if there is a satisfying assignment, we
can construct a proof of size $4+2n-1$. It follows that the problem must be -hard.

§.§ Temporal Queries

The lower bound follows from the atemporal case, see Theorem <ref>. Note that the temporal inference rules do not operate on domain elements.

For the upper bound, first of all we need to show that the temporal derivation structures are sound and complete, if $\Tmc\cup\Amc\models\q(\a,\iota)$ holds, then we can provide a proof for it.

The soundness of the new inferences can be easily verified from the semantics.

Completeness for both and can be shown by induction on the shape of the MTCQ $\q$. Namely, as common in the datalogMTL literature ( [39, 40]), we organize the timeline by rulers: we divide ABox facts into (finitely many) non-overlapping intervals whose time
points satisfy the same ABox facts. Ruler intervals can be non-regularly distributed. Since TBoxes are atemporal, inside a ruler interval all ontological inferences are the same for all timepoints.

As the basis of the induction over $\q$, we take the assumption that there are proofs for $\q(\a,\rho)=(\exists \y.\phi(\a,\y))@\rho$ if $\Tmc\cup \Amc\models \q(\a,\rho)$, for $\rho$ being a ruler interval and $\phi$ a CQ (see the correctness argument Section <ref>).

Up to this point, only need the temporal versions of , , The next phase of inferring temporal operators does not require and anymore.

We now apply whenever possible and keep as the last step; note that aggregates formulas involving different variable names.

For temporal operators we can use similar arguments as in the case of datalogMTL over $\mathbb{R}$ [16]: our inference schemas were inspired by the chase procedure there. The cases $\land$ and $\lor$ can be shown by contradiction.

Next, for the procedure above, we can show that it builds a proof of bounded size.

There exist polynomials $p_1$, $p_2$ such that for any TBox $\Tmc$, temporal ABox $\Amc$,
MTCQ $\q(\vec{x},w)$ with $\Tmc\cup\Amc\models
\q(\vec{a},\iota)$, there exists a proof
in $\Rtsk(\Tmc\cup\Amc,\q(\vec{a},\iota))$
whose tree size is bounded by $p_1(\lvert\Tmc\rvert,\lvert
\q(\vec{x})\rvert, \lvert \tem(\q) \rvert + \lvert \iota \rvert)$, if $\lvert \iota \rvert$ is finite, and by $p_2(\lvert\Tmc\rvert,\lvert
\q(\vec{x})\rvert, \lvert \Amc \rvert)$, otherwise.

The number of ruler intervals depends on the ABox: it is equal to the number of different endpoints mentioned in ABox ${}+2$ for infinities. Thus, in the case where $\iota$ is unbounded, we need to take into consideration all ruler intervals, for which we can find proofs for CQs of polynomial size according to Lemma <ref>.
(we only need to consider the CQs occurring in $\q$). We need at most $\lvert \q \rvert \cdot \lvert \Amc \rvert$ applications of to merge ruler intervals for all CQs (recall that takes finitely many premises); the dependence on $\lvert \Amc \rvert$ comes from the fact that a CQ may be satisfied in several non-contiguous intervals.

Each of the temporal schemas $\mathbf{(\boxplus)}$ corresponds to one kind of temporal operator; again, we need to apply them to a fixed CQ (or pair of CQs) at most $\lvert \Amc \rvert$ times. We run after each, resolving one temporal operator for all intervals, $\phi \luntil_{[0,3]}\psi$ over the facts $\phi@[0,5]$, $\psi@[3]$, $\psi@[6]$ is derived separately for the intervals $[0,3]$ and $[3,6]$, which we can coalesce.

The last step is if the desired certain answer interval is inside of one we obtain by the procedure above.

When $\iota=[t_1,t_2]$ is finite, we do not need to consider all ruler intervals in $\Amc$: it is enough to concentrate on the ones in $[t_1-\lvert \tem(\q)\rvert, t_2+\lvert \tem(\q)\rvert]$, an interval outside of which no facts can be part of a proof. Clearly, the size of the resulting set of relevant interval rulers is bounded by $2\cdot\lvert \tem(\q)\rvert+\lvert \iota\rvert$ (recall that $\lvert \tem(\q)\rvert$ is finite). Therefore, we can re-apply the rationale as above replacing $\lvert \Amc\rvert$ by the new bound independent of $\Amc$.

Finally, observe that the new inferences such as and $\mathbf{(\boxplus)}$ are orthogonal to the temporalized rules from Section <ref>. Thus, transitioning between derivers $\{\Rcq,\Rsk\}$ maintains the structure of temporal inferences intact and Lemma <ref> also holds in the temporal case.
Since Lemma <ref> bounds the size of a proof, by Lemma <ref>, the upper bound follows.

We can prove the rewritability claim by induction on the structure of the MTCQ.

CQs are UCQ-rewritable by assumption.

For the temporal dimension, over any MTCQ with bounded intervals can be transformed into an equivalent formula with only next temporal operator ($\lnext$ in LTL notation), the semantics of which is the same as of punctual temporal operators $\boxminus_{[1,1]}$ and $\boxplus_{[1,1]}$ in Figure <ref>. For example, by the recursive rewriting procedures below, in finitely many steps we reach a positive formula without $\boxplus$ and $\luntil$:

$$\boxplus_{[r_1,r_2]}\phi \equiv
\begin{cases}
\lnext(\boxplus_{[r_1-1,r_2-1]}\phi) , \text{ if } r_1 > 0, \\
\phi \land \lnext(\boxplus_{[0,r_2-1]} \phi), \text{ if } r_1 = 0 \text{ and } r_2 > 0,\\
\phi, \text{ otherwise.}
\end{cases}

\phi \luntil_{[r_1,r_2]} \psi \equiv
\begin{cases}
\phi \land \lnext(\phi\luntil_{[r_1-1,r_2-1]} \psi), \text{ if } r_1 > 0, \\
\psi \lor (\phi \land \lnext(\phi\luntil_{[0,r_2-1]} \psi)), \text{ if } r_1 = 0 \text{ and } r_2 > 0,\\
\psi, \text{ otherwise.}
\end{cases}

A celebrated result of Kamp [29] is that, over both $(\Zbb, <)$ and $(\mathbb{R}, <)$, all LTL operators are definable in $\FO(<)$, first-order logic with the built-in linear order. Thus, any MTCQ is $\FO(<)$-rewritable. In terms of circuit complexity, this means that MTCQ answering is in LogTime-uniform for data complexity [28].

We can see that our -rewriting is a positive-existential (PE) first-order formula, uses only $\land$, $\lor$, and existential quantification with the linear order seen as a predicate. Such a formula can be directly converted into an equivalent UCQ [1].

The second statement of the proof follows from as similar argument as in the proof of Theorem <ref>, we can pre-compute the minimal proof (tree) size for each of the CQs in this (fixed) UCQ.