* For $p\in (q_j,p_{j+1}]$ for some $j\in\left\{1,\ldots,m'-1\right\}$:

///*********  Old proof

We divide the proof to three steps: in the first step we prove that if $u(1)=\max_{p\in[0,1]} u(p)$, then $v(p)$ and $\hat{v}(p)$ are nondecreasing; in the second step we prove that $\hat{v}(\hat{p}^*)\geq v(p^*)$ and in the third we prove that $\hat{v}(p)\geq v(p)$.

Step 1: if $u(1)=\max_{p\in[0,1]} u(p)$, then $v(p)$ and $\hat{v}(p)$ are nondecreasing.

Let $p'<p$. At belief $p$, one possible message strategy is to split between $p'$ and 1. Following that split, if the split results in the belief being 1, it is possible to keep splitting between 1 and $p'$ until the belief reaches $p'$. Once the belief reaches $p'$, it is possible to use a strategy which yields  $v(p')$. The above possible strategy gives at belief $p$ a putative value that is a convex combination of $u(1)$ and $v(p')$. This combination is no less than $v(p')$.

Step 2: $\hat{v}(\hat{p}^*)\geq v(p^*)$.

From Lemma 3 in Cardaliaguet et al (2016), if $(p^*, (\textnormal{cav} u)(p^*))$
lies on the line segment connecting $(p', u(p'))$ and $(p'',u(p''))$ for some $p', p'' \in [0,1]$ that satisfy $p'\leq p^*\leq p''$, then the value function is linear on $[p',p'']$, and the sender's optimal message strategy at each belief between $p'$ and $p''$ (and to reveal no information if $p'=p''=p^*$). The value at $p^*$ is a convex combination of $u(p')$ and $u(p'' )$.

* If $\hat{p}^*\in[p',p'']$ then the optimal strategy for belief $\hat{p}^*$ in game $\hat{G}$ is a split between $p'$ and $p''$ with higher weight to the higher $u(p'')$.

///G: Is the formula needed??

* If $\hat{p}^*>p''$, then $(\hat{p}^*, (\textnormal{cav} u)(\hat{p}^*))$ lies on a line segment connecting some $(\hat{p}',u(\hat{p'}))$ and $(\hat{p}'',u(\hat{p''}))$, where $p''\leq \hat{p}'$. The value $\hat{v}(\hat{p}^*)$ is a convex combination of $u(\hat{p}')$ and $u(\hat{p}'')$. The monotonicity of $u$ completes the argument.

Step 3: $\hat{v}(p)\geq v(p)$.
We show that (I)  for every $p<p^*$, there is a message strategy in the game $\hat{G}$ that with some probability plays an optimal strategy $\sigma^*(p)$ of the game $G$ and with the remaining probability splits to $\hat{p}^*$ (and when the belief is $p^*$, we have from the previous steps that $\hat{v}(\hat{p}^*)\geq v(p^*)\geq v(p) $), and (II) for every $p>p^*$, there is a message strategy in the game $\hat{G}$ that with some probability plays $\sigma^*(p)$, and with the remaining probability the belief reaches $1$. If the belief ends up being 1, then it repeatedly splits between $p$ and 1, until it reaches $p$, and then it continues according to $\sigma^*(p)$. The repeated split between $p$ and $1$ results in a putative value that is a convex combination of $u(1)$ and $\hat{v}(p)$, no lower than $\hat{v}(p)$.

Proving (I).
discrete game proof.
If the length of a period is $\Delta$, then, when this period begins at belief $p$, when game $G$ is played, from Eq. (<ref>), the next period begins at belief
\[q:=pe^{-\Delta (\lambda_0+\lambda_1)}+p^*\left(1-e^{-\Delta (\lambda_0+\lambda_1)}\right)\]
. In game $\hat{G}$ the next period begins with belief is
\[\hat{q}:=pe^{-\Delta (\hat{\lambda}_0+\hat{\lambda}_1)}+p^*\left(1-e^{-\Delta (\hat{\lambda}_0+\hat{\lambda}_1)}\right)\]
We have that $\hat{\lambda}_0+\hat{\lambda_1}=\lambda_0+\lambda_1$, $\hat{p}^*>p^*$, and so $\hat{q}>q$. For $\Delta$ small, it also holds that $\hat{q}\leq \hat{p}^*$. This means that $\hat{q}$ can be presented as a convex combination of $q$ and $\hat{p}^*$, as required.

continuous-time game proof.
In continuous-time game we want the randomization between $\sigma^*(p)$ and $\hat{p}^*$ to maintain an expectation of $\mathbb{E}[p^{t+h}|p^t]$. For this we need to randomize the transition to $\hat{p}^*$ with a probability $\theta$ that satisfies:

\[\mathbb{E}[p^{t+h}|p^t]=\hat{p}^*+(p^t-\hat{p}^*)e^{-(\hat{\lambda}_0 + \hat{\lambda}_1)h}=(1-\theta)\left(\hat{p}^*+(p^t-\hat{p}^*)e^{-(\hat{\lambda}_0 + \hat{\lambda}_1)h}\right)+ \theta \hat{p}^*.\]

This gives:

\[\theta=\frac{(\hat{p}^*-p^*)\left(1-e^{-(\lambda_0+\lambda_1)h}\right)}{\hat{p}^*-p^*-(p^t-p^*)e^{-(\lambda_0+\lambda_1)h}}.\]

\[ \lim_{h\to 0}\frac{\theta}{h}=\frac{(\hat{p}^*-p^*)(\lambda_0+\lambda_1)}{\hat{p}^*-p^* +(\lambda_0+\lambda_1)(p^t-p^*)}.\]

We have that

\begin{multline*}
\frac{\partial p^t}{\partial t}=\\
(1-\lim_{h\to 0}\frac{\theta}{h})\left(p^*+(p^t-p^*)e^{-(\lambda_0+\lambda_1)h}\right)+\hat{p}^*\lim_{h\to 0}\frac{\theta}{h} .
\end{multline*}

Proving (II).
discrete game proof.

There are two cases to consider: $p^*\leq p \leq \hat{p}^*$ and $\hat{p}^*<p$.
In the first case, during one period the belief in game $G$ is nonincreasing while the belief in game $\hat{G}$ is nondecreasing. The means that the next period's belief is higher in game $\hat{G}$ compared to in game $\hat{G}$. This allows for the required randomization, between the optimal strategy for game $G$, $\sigma^*(p)$ and splitting to belief 1. We turn to consider the second case.

If the length of a period is $\Delta$, then, when this period begins at belief $p$, when game $G$ is played, from Eq. (<ref>), the next period begins at belief
\[q:=pe^{-\Delta (\lambda_0+\lambda_1)}+p^*\left(1-e^{-\Delta (\lambda_0+\lambda_1)}\right)\]
. In game $\hat{G}$ the next period begins with belief is
\[\hat{q}:=pe^{-\Delta (\hat{\lambda}_0+\hat{\lambda}_1)}+p^*\left(1-e^{-\Delta (\hat{\lambda}_0+\hat{\lambda}_1)}\right)\]
We have that $\hat{\lambda}_0+\hat{\lambda_1}=\lambda_0+\lambda_1$, $\hat{p}^*>p^*$, and so $\hat{q}>q$. For $\Delta$ small, it also holds that $\hat{q}\leq \hat{p}^*$. This means that $\hat{q}$ can be presented as a convex combination of $q$ and 1, as required.

[](2,0.1) – (2,-0.1)node[below, scale=0.65] $p_j$;
[](1.5,0.1) – (1.5,-0.11);
[](5.5,0.1) – (5.5,-0.11);
[red, loosely dotted](5.5, 3)– (5.5,-0.5)node[below, scale=0.65] $p_{j+1}-b$;
[thick, green, loosely dotted](6.5, 3)– (6.5,-0.5)node[below, scale=0.65] $p_{j+1}+b$;

[](5.5,0.1) – (5.5,-0.11);
[red, loosely dotted](1.5, 2)– (1.5,-0.5)node[below, scale=0.65] $p_{j}-b$;
[thick, green, loosely dotted](2.5, 2)– (2.5,-0.5)node[below, scale=0.65] $p_{j}+b$;

[](6,0.1) – (6,-0.1)node[below, scale=0.65]$p_{j+1}$;
[->] (-0.5,0) – (8,0) node[right] $p$;
[->] (0,-0.5) – (0,4) node[above] $u$;
[blue, dashed] (0.5,0.5) – (2,0.5);
[blue, dashed] (2,2) – (6,2);
[blue, dashed] (6,3) – (7.5,3);

[thick, green, densely  dotted] (0.5,0.47) – (2.5,0.47);
[thick, red, densely  dotted] (0.5,0.53) – (1.5,0.53);
[thick, red, densely dotted]
(1.5,2.03) –
[thick, green, densely  dotted] (2.5,1.97) – (6.5,1.97);

[thick, red, densely dotted]
(5.5, 3.02) –
(7.5, 3.02);
[thick, green, densely  dotted] (6.5,2.97) – (7.5,2.97);

[loosely dotted] (2,0) – (2,2);
[loosely dotted] (6,0) – (6,3);

[scale=0.7] at (7, 4.3)   $\overline{w}^b$;
[scale=0.7] at (7, 4)   $u$;
[scale=0.7] at (7, 3.7)   $\underline{w}^b$;

[blue, dashed] (7.3,4) – (7.9,4);
[red, densely dotted]
(7.3,4.3) –
[thick, green, densely dotted](7.3,3.7)–(7.9,3.7);

The indirect payoff functions $\overline{w}^b$ and $\underline{w}^b$ approximating $u$ from above and from below, respectively.

/// Eilon: the next remark is in discrete time, and should not be here.
In the remark, do Equations (6) and (7) hold with the same $\mu$?
After all, time is continuous in the equations and discrete in the model.

Equations (<ref>) and (<ref>) hold also in the discrete-time game, using the geometric distribution rather than the exponential distribution. Equations  (<ref>) and (<ref>) hold in the case that the belief $p''$ is reached exactly when the belief begins at $p'$ and no information is revealed. Otherwise, the belief does not reach $p''$ exactly, but rather is slightly below and slightly above it within $\Delta$ time of (<ref>), when $\Delta$ is the duration of a period.

Suppose that $p^*=p_0$.

Then, what we want to show is:

\[\lim_{\eta\to0}\frac{\overline{v}(p_0-\eta) - \overline{u}(p_0-\eta)}{\eta}>\frac{\overline{v}(p_{-1})-\overline{u}(p_{-1})}{p^*-p_{-1}}.\]

The right hand side is bounded.

Consider the left hand side.

\[\overline{v}(p_0-\eta)\geq \overline{v}_{split_to_p0}(p_0-\eta) \]

From Conclusion <ref>, plugging $p=p'=p_0-\eta$ and $p''=p^*=p_0$, we obtain

\begin{multline}
w(\sigma_{split}, p_0-\eta)\\= \overline u_\delta(p_0-\eta)\frac{p_0(\mu+1)-p_0}{\eta(\mu+1)} +\overline u_\delta(p_0)\frac{p_0-(p_0-\eta)(\mu+1)}{\eta(\mu+1)} + (p_0-\eta)\mu\frac{\overline u_\delta(p_0)-\overline u_\delta(p_0-\eta)}{\eta(\mu+1)}
\\= \overline u_\delta(p_0-\eta)\frac{p_0\mu}{\eta(\mu+1)} +\overline u_\delta(p_0)\frac{-p_0\mu+\eta(\mu+1)}{\eta(\mu+1)} + (p_0-\eta)\mu\frac{\overline u_\delta(p_0)-\overline u_\delta(p_0-\eta)}{\eta(\mu+1)}
\\= \overline u_\delta(p_0-\eta)\frac{p_0\mu-p_0\mu +\eta\mu}{\eta(\mu+1)} +\overline u_\delta(p_0)\frac{-p_0\mu+\eta(\mu+1)+p_0\mu-\eta\mu}{\eta(\mu+1)}
\\= \overline u_\delta(p_0-\eta)\frac{\eta\mu}{\eta(\mu+1)} +\overline u_\delta(p_0)\frac{\eta}{\eta(\mu+1)}
\\= \overline u_\delta(p_0-\eta)\frac{\mu}{\mu+1} +\overline u_\delta(p_0)\frac{1}{\mu+1}
\end{multline}

\begin{multline*}
\frac{\overline{v}_\delta(p_0-\eta) - \overline{u}(p_0-\eta)}{\eta} \geq \frac{\overline u_\delta(p_0-\eta)\frac{\mu}{\mu+1} +\overline u_\delta(p_0)\frac{1}{\mu+1} - \overline{u}_\delta(p_0-\eta)}{\eta} \\
=\frac{\overline u_\delta(p_0)-\overline{u}_\delta(p_0-\eta)}{\eta(\mu+1)}
\end{multline*}

$\overline u_\delta (p_0-\eta)=\frac{h_0-h_{-1}}{\delta}(-\eta) + h_0 = \frac{h_0-\left(\frac{h_0-h_{-1}}{\delta}(p_0-\eta-p_0)+h_0\right) }{\eta(\mu+1)} = \frac{h_0-h_{-1}}{\delta(\mu+1)}$.

This expression is independent of $\eta$ and is higher than the bound on the right hand side for small enough $\delta$.

Proof of (c)(ii):
Suppose again that

We want to show that

\[\lim_{\eta\to 0}\frac{\overline{u}_\delta(p_0+\eta)-\overline{v}_\delta(p_0+\eta)}{\eta}<\frac{\overline{u}_\delta(p_1)-\overline{v}_\delta(p_1)}{p_1-p_0}.\]

We have $\overline{u}_\delta(p_0+\eta)=h_0$.

Also, $\overline{v}_\delta(p_0+\eta)
\geq \overline{w}_\delta(\sigma_{split},p_0+\eta)$.

By Conclusion <ref> for $p=p_0+\eta$. $p'=p_0$ and $p''=p_1$ we have:

\begin{multline*}
\overline{w}_\delta(\sigma_{split},p_0+\eta)\\
+ h_1\frac{p_0-p_0(\mu+1)}{(p_1-p_0)(\mu+1)}
+ (p_0+\eta)\mu\frac{h_1-h_0}{(p_1-p_0)(\mu+1)}
\\
=h_0\frac{(p_1-p_0)(\mu+1)-\eta\mu}{(p_1-p_0)(\mu+1)} + h_1\frac{\eta\mu}{(p_1-p_0)(\mu+1)}.
\end{multline*}

\[\frac{h_0-v(p_0+\eta)}{\eta}\leq \frac{\eta\mu(h_0-h_1)}{\eta(\mu+1)(p_1-p_0)}=\frac{\mu(h_0-h_1)}{(\mu+1)(p_1-p_0)}.\]

What we want to show is that

\[\frac{h_1-\overline{v}_\delta(p_1)}{p_1-p_0}>\frac{\mu(h_0-h_1)}{(\mu+1)(p_1-p_0)}.\]

Cancelling out $(p_1-p_0)$ and rearranging we obtain that we want to show that

\[h_1+\frac{\mu(h_1-h_0)}{(\mu+1)(p_1-p_0)}>\overline{v}_\delta(p_1)\]

but this holds due to Lemma <ref>.

We have

\begin{eqnarray*}
&=&\left(1-e^{-r\rmd t} \right)u(p) + e^{-r\rmd t}w(p + \rmd p;\sigma^{slide}_{0,p^*,0})\\
&=&ru(p)\rmd t + (1-r\rmd t)\left(w(p;\sigma^{slide}_{0,p^*,0})+w'(p;\sigma^{slide}_{0,p^*,0})\rmd p\right).
\end{eqnarray*}

Using  Eq. (<ref>) we deduce that

\begin{eqnarray*}
w'(p;\sigma^{slide}_{0,p^*,0})\tfrac{\rmd p}{\rmd t}(1-r\rmd t)\\
\end{eqnarray*}

and therefore

\[w'(p;\sigma^{slide}_{0,p^*,0})=\frac{r\cdot(u(p)-w(p;\sigma^{slide}_{0,p^*,0}))}{(\lambda_0+\lambda_1)(p-p^*)}
= \overline g_\delta(p).\]

REMARK 3

We can conclude the following lemma, which, together with the remark that follows, completes the proof of Lemma <ref>.

For the case where $p^*=p_0$, we need to verify that the sender's message strategy of splitting the belief between $p_{-1}$ and $p_0$ for beliefs in $[p_{-1},p_0)$ indeed gives a value with continuous derivative that is nonincreasing.
To this end, we need to find the derivative over this interval.
Substituting $p'=p_{-1}$ and $p''=p_0=p^*$ in Eq. (<ref>), we get that  $w'(p;\overline\sigma^*_\delta) = \tfrac{\mu\cdot\left(v(p_0)-h_{-1}\right)}{(\mu+1)\left(p_0-p_{-1}\right)}$ for all $p\in[p_{-1},p_0]$. We need to show that $w'(p;\overline\sigma^*_\delta)$ is equal to the derivative of the value at $p_{-1}$, which is $\overline g_\delta(p_{-1})$  (as according to $\overline{\sigma}^*_\delta$ the belief slides from $\overline{q}_{-1}$ to $p_{-1}$, and thus the left derivative of the putative value function at $p_{-1}$ is, by Lemma <ref>, $\overline{g}_\delta(p_{-1})$).
We thus need to show that $\mu\cdot\tfrac{v(p_{-1})-h_{-1}}{p_0-p_{-1}}=\tfrac{\mu\cdot\left(v(p_0)-h_{-1}\right)}{(\mu+1)\left(p_0-p_{-1}\right)}$.
This equality is equivalent to $v(p_{-1})=\tfrac{v(p_0)}{\mu+1}+\mu\cdot\tfrac{h_{-1}}{\mu+1}$, which holds by Eq. (<ref>) and Eq. (<ref>). Similar arguments prove the continuity of the derivative of the value function at $p_1$.

To prove Lemma <ref>, we show that $w_\Delta(p,\sigma)$ can be bounded from above by the value of a continuous time game with a slightly different instantaneous payoff function.

In order to define the altered instantaneous payoff function, consider the difference between the discrete and the continuous-time game. Suppose that at the beginning of a period (possibly following a split of the belief), the belief is $p$. In the discrete time model, the sender obtains $u(p)$ for the entire $\Delta$ time duration of one period, while in the continuous time model the instantaneous payoff might change during the next $\Delta$ time period. However, in our model, such a change during a period happens only if $p$ is close to an end-point of a continuity interval and is moving towards that end-point.

Specifically, denote the maximal difference between the belief at some time $t$ and the belief at time $t+\Delta$ (see Eq. (<ref>)) by:

\[b(\Delta):=\max_{p\in\left\{0,1\right\}}|p-p^*|e^{-(\lambda_0+\lambda_1)\Delta}.\]

Observe that $\lim_{\delta\to 0} b(\Delta)=0$.
The sender may gains from the game being discrete only if the belief at the beginning of the period is in one of the intervals $[p_j,p_j-b)$, $j\in\{1,\ldots,m'\}$. Only in these cases is it possible for the sender to continue to profit from the higher $u(p)=h_j$ throughout the entire duration $\Delta$ of a period in the discrete time model, while in the continuous-time model the belief might become lower than $p_j$, making the instantaneous payoff function the lower $h_{j-1}$.

Thus, the value of the discrete-time game can be bounded by the value of a continuous-time game with slightly changed $u$ function: one where for beliefs higher that $p^*$ the instantaneous $u$ is shifted by $b(\Delta)$ to the left. Denote the altered instantaneous payoff function by $u^{b(\Delta)}$, (see Figure <ref>) and define it to be:

$u^{b(\Delta)}(p)=h_j$ for $p\in[p_j-b(\Delta),p_{j+1}-b(\Delta))$, $j\in\left\{1,\dots, m'-1\right\}$, $u^{b(\Delta)}(p)=h_0$ for $p\in[p_0,p_{-1}-b(\Delta))$, $u^{b(\Delta)}(p)=u(p)$ for $p\in[0,p_0)$, and $u^{b(\Delta)}(p)=h_{m'-1}$ for $p\in [p_{m'-1}-b(\Delta),1]$.

\begin{equation*}
u^{b(\Delta)} = \begin{cases}
h_m             & p\in[p_{-m},p_{-m}-b(\Delta)),\\
h_j             & p\in[p_j-b(\Delta),p_{j+1}-b(\Delta)),~ j\in\{-m+1,\ldots,m'-2\},\\
h_{m'-1} & p\in[p_{m'-1}-b(\Delta),p_{m'}].
\end{cases}
\end{equation*}

[](2,0.1) – (2,-0.1)node[below, scale=0.65] $p_j$;
[](1.5,0.1) – (1.5,-0.11);
[](5.5,0.1) – (5.5,-0.11);
[red, loosely dotted](5.5, 3)– (5.5,-0.5)node[below, scale=0.65] $p_{j+1}-b$;

[](5.5,0.1) – (5.5,-0.11);
[red, loosely dotted](1.5, 2)– (1.5,-0.5)node[below, scale=0.65] $p_{j}-b$;
[](6,0.1) – (6,-0.1)node[below, scale=0.65]$p_{j+1}$;
[->] (-0.5,0) – (8,0) node[right] $p$;
[->] (0,-0.5) – (0,4) node[above] $u$;
[blue, dashed] (0.5,0.5) – (2,0.5);
[blue, dashed] (2,2) – (6,2);
[blue, dashed] (6,3) – (7.5,3);

[thick, red, densely  dotted] (0.1,0.53) – (1.5,0.53);
[thick, red, densely dotted]
(1.5,2.03) –

[thick, red, densely dotted]
(5.5, 3.02) –
(7.5, 3.02);

[loosely dotted] (2,0) – (2,2);
[loosely dotted] (6,0) – (6,3);

[scale=0.7] at (7, 4.3)   $u^{b(\Delta)}$;
[scale=0.7] at (7, 4)   $u$;

[blue, dashed] (7.3,4) – (7.9,4);
[red, densely dotted]
(7.3,4.3) –

The indirect payoff functions $u^{b(\delta)}$ approximating $u$ from above.

Next, we bound the value of $G_{\Delta}(u)$ by the value of $G_{cont}(u^{b(\Delta)})$ and then show that the value of $G_{cont}(u^{b(\Delta)})$ converges to $v_{cont}$ as $\Delta$ diminishes.
In order to show that the value of $G_{\Delta}(u)$ is bounded by the value of $G_{cont}(u^{b(\Delta)})$, we show that for any strategy $\sigma$ in $G_{\Delta}(u)$ there is a strategy $\sigma^{b(\Delta)}$ in $G_{cont}(u^{b(\Delta)})$ that has the same distribution of beliefs as $\sigma$ at the sequence of times $(k\Delta)_{k=0,1,\ldots}$. During time intervals $(k\Delta, (k+1)\Delta)$, $k\in \mathbb{N}$, the belief in the discrete game is equal to the belief at time $k\Delta$, while the belief according to the continuous time strategy is within at most $b(\Delta)$ distance from the beginning of period belief. The argument is inductive: at time 0 the strategy $\sigma^{b(\Delta)}$ does the same as the strategy $\sigma$: either split the belief (with the same distribution) or reveal no information. Then, along the time interval $(0,\Delta)$ the strategy $\sigma^{b(\Delta)}$ does not reveal information. Thus, it remains within at most $b$ distance from the belief after the action taken at time 0. At the end of this first period, the beliefs have the same distribution again, since under both strategies no information was revealed since the possible initial revaluation of information at time 0. A similar argument works for the second period: $\sigma^b$ mimics $\sigma$ at time $\Delta$ and then reveals no information along the time interval $(\Delta,2\Delta)$. Inductively, the argument is complete.

We conclude that the belief evolves under strategy $\sigma^{b(\Delta)}$ so that it is always with at most $b(\Delta)$ distance from the belief evolving under the strategy $\sigma$. Since $u^{b(\Delta)}$ is designed to capture all possible gains from $b(\Delta)$ distance in the beliefs, we have that the putative value obtained when employing $\sigma$ in $G_\Delta(u)$ is at least as high as the one obtained by $\sigma^b$ in $G_{cont}(u^{b(\Delta)})$. Therefore, it is left to show that as $\Delta$ decreases, the value of $G_{cont}(u^{b(\Delta)})$ converges to the value of $G_{cont}(u)$.

Denote $\overline{v}^{b(\Delta)}$ to be the value of $G_{cont}(u^{b(\Delta)})$.   For a small $\Delta$, implying a small $b(\Delta)$, the function $u^{b(\Delta)}$ satisfies
Assumption <ref>. Therefore, we know what is the optimal strategy for $G_{cont}(u^{b(\Delta)})$, denote it
For $p\in[p_0,p_1]$ the value is a convex combination of $h_0$ and $h_1$, and their weights in the combination converges to their respective weight for $b=0$. This means that for all beliefs in $[p_0,p_1]$ we have that $\lim_{\Delta\to 0}\overline{v}^{b(\Delta)}(p)=v_{cont}(p)$. Similarly, the value obtained by splitting the belief between $p_{-j}-b(\Delta)$ and $p_{-j+1}-d(\Delta)$, $j=1,\ldots,m-1$ (and between 0 and $p_{-m+1}-b(\Delta)$) converges to the respective values when the split is between $p_{-j}$ and $p_{-j+1}$, $j=1,\ldots,m-1$ (and between 0 and $p_{-m+1}$) as $\Delta$ diminishes.

Finally, for beliefs that belong to some continuity interval $(p_j,p_{j+1}]$, $j=1,\ldots m'-1$, the optimal strategy for $G_{cont}(u^{b(\Delta)})$ is to reveal no information when the belief is in the interval $[p_j-b,\overline{q}_j^{b(\Delta)}]$, for some $\overline{q}_j^{b(\Delta)}\in (p_j-b(\Delta), p_{j+1})$, and splitting the belief between $\overline{q}_j^{b(\Delta)}$ and $p_{j+1}-b(\Delta)$ when the belief is in $[\overline{q}_j^{b(\Delta)},p_{j+1}]$. The sequence $\overline{q}_j^{b(\Delta)}$ converges to $q_j$ as $b(\Delta)$ diminishes.
To see that indeed $\overline{q}_j^{b(\Delta)}$ converges to $q_j$, assume, by negation, that it does not converge to $q_j$. Then there is a minimal $j$ and a subsequence $\overline{q}_j^{b(\Delta_n)}$ such that $\lim_{n\to\infty} \overline{q}_j^{b(\Delta_n)}=q*$, and $q^*\neq q_j$. The putative value at $p_{j+1}$ is continuous in the value of the belief $q_j$. This means that the sender can obtain for belief $p_{j+1}$ a value higher than respective $v_{cont}(q_{j+1})$ using sliding from $q^*$ to $p_j$ and splitting between $p_{j+1}$ and $q^*$ , a contradiction to the definition of a value.

///G: this is not very formal, is is convincing?

PROOF OF LEMMA 11
///G: A lot of the computations are repeating themselves, it is just the changing directions of beliefs and times that can be confusing. Once we are sure these are correct, we can delete some of it.

Proof of Lemma <ref>(a)

For $p\in[0,p^*)$, when no information is revealed, the belief increases. Let $p^t=p$ and $p^{t-dt}=p-dp$ where, (according to Eq. (<ref>)).

$ \frac{dp}{dt}
= (\lambda_0+\lambda_1)(p^*-(p-dp))$.

Combining with ${\overline{w}_\delta}(p-dp,\sigma^{slide}_{p-\eta,p})=(1-e^{-rdt})+e^{-rdt}\overline{w}_\delta(p,\sigma^{slide}_{p-\eta,p})$ we obtain:

\begin{eqnarray*}
{\overline{w}_\delta}'_-(p,\sigma^{slide}_{p-\eta,p})&=&\lim_{dt\to 0}\frac{{\overline{w}_\delta}(p^{t},\sigma^{slide}_{p-\eta,p})-{\overline{w}_\delta}(p^{t-dt},\sigma^{slide}_{p-\eta,p})}{dt}\cdot\frac{dt}{dp}\\
&=&\lim_{dt\to 0}\frac{{\overline{w}_\delta}(p^t,\sigma_1)-(1-e^{-rdt})\overline{u}_\delta(p^{t-dt})-e^{-rdt}{\overline{w}_\delta}(p^t,\sigma^{slide}_{p-\eta,p})}{dt}\cdot \frac{1}{(\lambda_0+\lambda_1)(p^*-p^{t-dt})}\\
&=&\frac{1}{(\lambda_0+\lambda_1)(p^*-p^t)}\lim_{dt\to 0}\frac{(1-e^{-rdt})({\overline{w}_\delta}(p^t,\sigma^{slide}_{p-\eta,p})-\overline{u}_\delta(p^{t-dt}))}{dt}\\
&=&\frac{1}{(\lambda_0+\lambda_1)(p^*-p^t)}\cdot r({\overline{w}_\delta}(p^t,\sigma^{slide}_{p-\eta,p})-\overline{u}_\delta(p^{t-}))\\
&=& \mu\frac{\overline{u}_\delta(p^-)-{\overline{w}_\delta}(p,\sigma^{slide}_{p-\eta,p})}{p-p^*},
\end{eqnarray*}

as claimed.

Let $p\in(p^*,1]$. In this case, when revealing no information, the belief decreases with time, thus $p^t=p$ and $p^{t+dt}=p-dp$.

\begin{eqnarray*}
{\overline{w}_\delta}'_-(p;\sigma^{slide}_{p-\eta,p})&=&\lim_{dt\to 0}\frac{{\overline{w}_\delta}(p^{t+dt},\sigma^{slide}_{p-\eta,p})-{\overline{w}_\delta}(p^t,\sigma^{slide}_{p-\eta,p})}{dt}\cdot \frac{dt}{dp}\\
&=&\frac{1}{(\lambda_0+\lambda_1)(p^*-p^t)} \lim_{dt\to 0}\frac{{\overline{w}_\delta}(p^{t+dt},\sigma^{slide}_{p-\eta,p})-(1-e^{-rdt})\overline{u}_\delta(p^t)-e^{-rdt}{\overline{w}_\delta}(p^{t+dt},\sigma^{slide}_{p-\eta,p})}{dt}\\
&=&\frac{1}{(\lambda_0+\lambda_1)(p^*-p^t)} \lim_{dt\to 0}\frac{(1-e^{-rdt})({\overline{w}_\delta}(p^{t+dt},\sigma^{slide}_{p-\eta,p})-\overline{u}_\delta(p^t))}{dt}\\
&=& \mu\frac{\overline{u}_\delta(p)-{\overline{w}_\delta}(p,\sigma^{slide}_{p-\eta,p})}{p-p^*}
\end{eqnarray*}

as claimed.

Proof of Lemma <ref>(b)

Let $p\in[0,p^*)$. We have that $p^{t+dt}=p+dp$, and the continuity of ${\overline{w}_\delta}$ is used to plug $\lim_{dt\to 0}{\overline{w}_\delta}(p^{t+dt},\sigma^{slide}_{p,p+\eta})={\overline{w}_\delta}(p^t,\sigma^{slide}_{p,p+\eta})$

\begin{eqnarray*}
w'_+(p,\sigma^{slide}_{p,p+\eta})&=&\lim_{dt\to 0}\frac{w(p^{t+dt},\sigma^{slide}_{p,p+\eta})-w(p^t,\sigma^{slide}_{p,p+\eta})}{dt}\cdot \frac{dt}{dp}\\
&=&\frac{1}{(\lambda_0+\lambda_1)(p^*-p^t)}\cdot\lim_{dt\to 0}\frac{w(p^{t+dt},\sigma^{slide}_{p,p+\eta})-(1-e^{-rdt})u(p^t)-e^{-rdt}w(p^{t+dt},\sigma^{slide}_{p,p+\eta})}{dt}\\
&=&\frac{1}{(\lambda_0+\lambda_1)(p^*-p^t)}\cdot\lim_{dt\to 0}\frac{(1-e^{-rdt})(w(p^{t+dt},\sigma^{slide}_{p,p+\eta})-u(p))}{dt}\\
&=& \mu\frac{u(p)-w(p,\sigma^{slide}_{p,p+\eta})}{p-p^*}
\end{eqnarray*}

as claimed.

Let $p\in(p^*,1]$. $p^t=p+dp$ and $p^{t+dt}=p$.

\begin{eqnarray*}
{\overline{w}_\delta}'_+(p,\sigma^{slide}_{p,p+\eta})&=&\lim_{dt\to 0}\frac{{\overline{w}_\delta}(p^{t+dt},\sigma^{slide}_{p,p+\eta})-{\overline{w}_\delta}(p^t,\sigma^{slide}_{p,p+\eta})}{dt}\cdot \frac{dt}{dp}\\
&=&\frac{1}{(\lambda_0+\lambda_1)(p^*-p^t)} \lim_{dt\to 0}\frac{{\overline{w}_\delta}(p^{t+dt},\sigma^{slide}_{p,p+\eta})-(1-e^{-rdt})\overline{u}_\delta(p^t)-e^{-rdt}{\overline{w}_\delta}(p^{t+dt},\sigma^{slide}_{p,p+\eta})}{dt}\\
&=&\frac{1}{(\lambda_0+\lambda_1)(p^*-p^t)} \lim_{dt\to 0}\frac{(1-e^{-rdt})({\overline{w}_\delta}(p^{t+dt},\sigma_2)-\overline{u}_\delta(p^t))}{dt}\\{\overline{w}_\delta}
&=& \mu\frac{\overline{u}_\delta(p)-{\overline{w}_\delta}(p,\sigma^{slide}_{p,p+\eta})}{p-p^*},
\end{eqnarray*}

as claimed.

Proof of Lemma <ref>(c)

For $p\in[p'.p'']$, splitting the belief between $p'$ and $p''$ at $p$ gives $ {\overline{w}_\delta}(p,\sigma^{split}_{p',p''}) = \frac{p''-p}{p''-p'}{\overline{w}_\delta}(p',\sigma^{split}_{p',p''})  + \frac{p-p''}{p''-p'}{\overline{w}_\delta}(p'',\sigma^{split}_{p',p''})$

Taking the derivative with respect to $p$ then gives:

\begin{equation}\label{eq split weight}
{\overline{w}_\delta}'(p,\sigma^{split}_{p',p''})=\frac{-{\overline{w}_\delta}(p',\sigma^{split}_{p',p''})+ {\overline{w}_\delta}(p'',\sigma^{split}_{p',p''})}{p''-p'}
\end{equation}

From equations (<ref>) and (<ref>) we have:

\[{\overline{w}_\delta}(p',\sigma^{split}_{p',p''})=\frac{\mu(p''-p')}{p^*-p'-\mu(p''-p')}\overline{u}_\delta(p')+\frac{p^*-p'}{p^*-p' +\mu(p''-p')}{\overline{w}_\delta}(p'',\sigma^{split}_{p',p''}).\]

Rearranging gives:

\[{\overline{w}_\delta}(p'',\sigma^{split}_{p',p''})=\frac{p^*-p'+\mu(p''-p')}{p^*-p'}{\overline{w}_\delta}(p',\sigma^{split}_{p',p''})+ \mu\frac{p''-p'}{p^*-p'}\overline{u}_\delta(p').\]

Plugging this expression into Eq. (<ref>) completes the argument.

Proof of Lemma <ref>(d)

This is similar to the proof of (c).

PROOF OF LEMMA 3 REMOVED PART:
We apply a splitting strategy to a continuous-time game and a discrete-time game and compare the resulting putative values. Specifically, let $p'<p''\leq p^*$ or $p^*\leq p''<p'$. We compare $w_\Delta(p',\sigma^{split}_{p',p''})$ and $w(p',\sigma^{split}_{p',p''})$.

From Eq. (<ref>) we have

\begin{equation}\label{eq jumping}w(p',\sigma^{split}_{p',p''})=\frac{\mu(p''-p')}{p^*-p'+\mu(p''-p')}u(p')+ \left(1-\frac{\mu(p''-p')}{p^*-p'+\mu(p''-p')}\right)w(p'',\sigma^{split}_{p',p''})\end{equation}

In the discrete-time game, let $X$ be the random variable representing the number of periods it takes for the belief to become $p''$ when using $\sigma^{split}_{p',p''}$. The random variable $X$ has a geometric distribution. At each period when the belief is $p'$, the probability that it switches to $p''$ (the parameter of the geometric distribution), denoted $p_{sw}$ satisfies, by Eq. (<ref>) and from expectancy of belief being preserved:

\[p^*+(p'-p^*)e^{-(\lambda_0+\lambda_1)\Delta}=p'(1-p_{sw})+p_{sw}p''.\]

\[p_{sw}=\frac{p^*-p'}{p''-p'}\left(1-e^{-\Delta(\lambda_0+\lambda_1)}\right).\]

Therefore, the total weight of the periods is takes the belief to switch from $p'$ to $p''$, denoted $Y^{\Delta, split}_{p',p''}$ is:

\begin{eqnarray}
\nonumber
Y^{\Delta, split}_{p',p''}&=&\sum_{k=1}^\infty P(X=k)\sum_{t=1}^{k-1}(1-e^{-\Delta r})e^{-\Delta r(t-1)} \\
\nonumber
& =&\sum_{k=1}^\infty (1-p_{sw})^{k-1}p_{sw}(1-e^{-\Delta r})\frac{1-e^{-\Delta r(k-1)}}{1-e^{-\Delta r}}\\
\nonumber
& =&p_{sw}\sum_{k=1}^\infty (1-p_{sw})^{k-1}(1-e^{-\Delta r(k-1)})\\
\nonumber
&=&p_{sw}\sum_{k=1}^\infty (1-p_{sw})^{k-1}-p_{sw}\sum_{k=1}^\infty \left((1-p_{sw})e^{-\Delta r}\right)^{k-1}\\
\nonumber
& =& p_{sw}\frac{1}{1-(1-p_{sw})} - p_{sw} \frac{1}{1-(1-p_{sw})e^{-\Delta r}}\\
\nonumber
& =& 1-\frac{p_{sw}}{1-(1-p_{sw})e^{-\Delta r}}\\
\nonumber
& =& 1-\frac{\frac{p^*-p'}{p''-p'}\left(1-e^{-\Delta(\lambda_0+\lambda_1)}\right)}{1-\left(1-\frac{p^*-p'}{p''-p'}\left(1-e^{-\Delta(\lambda_0+\lambda_1)}\right)\right)e^{-\Delta r}}
\end{eqnarray}

Therefore we compute, using l'Hôpital:

\begin{eqnarray}\label{equ: lim time split}
\lim_{\Delta\to 0}Y^{\Delta, split}_{p',p''}&=&
1-\lim_{\Delta\to 0}\frac{\frac{p^*-p'}{p''-p'}\left(1-e^{-\Delta(\lambda_0+\lambda_1)}\right)}{1-\left(1-\frac{p^*-p'}{p''-p'}\left(1-e^{-\Delta(\lambda_0+\lambda_1)}\right)\right)e^{-\Delta r}}\\
\nonumber &=&
1-\lim_{\Delta\to 0}\frac{\frac{p^*-p'}{p''-p'}(\lambda_0+\lambda_1)}{r-r\frac{p^*-p'}{p''-p'}\left(1-e^{-\Delta(\lambda_0+\lambda_1)}\right)+e^{-r\Delta}\frac{p^*-p'}{p''-p'}(\lambda_0+\lambda_1)}\\
\nonumber
\nonumber
\nonumber
&=& \frac{\frac{r}{\lambda_0+\lambda_1}(p''-p')}{\frac{r}{\lambda_0+\lambda_1}(p''-p')+p^*-p'}\\
\nonumber&=&\frac{\mu(p''-p')}{p^*-p' +\mu(p''-p')}.
\end{eqnarray}

The last expression is the same as $Y^{split}_{p',p''}$ in the continuous time model. We conclude that the discounted time it takes the belief to get from $p'$ to $p''$ in the discrete-time game converges, as $\Delta$ diminishes, to the discounted time it takes in the continuous-time game.

We proceed by comparing the discounted time it takes to slide (advance without revealing information) frzom belief $p'$ to belief $p''$ (where either $p'<p''<p^*$ or $p'>p''>p^*$). Using the strategy $\sigma^{slide}_{p',p''}$ in the continuous time the belief will get exactly to $p''$, while in the discrete time the belief at the beginning of the last sliding period can be below $p''$ and at the end of that period it may be slightly above it.

Formally, the discounted time in the continuous model is by Eq. (<ref>): $Y^{slide}_{p',p''}=1-\left(\frac{p^*-p''}{p^*-p'}\right)^{\frac{r}{\lambda_0+\lambda_1}}$. For the discrete time, the slide goes on for $n$ periods, where $n$ is the integer which satisfies the two following conditions for the case $p'>p''>p^*$ (for the case $p'<p''<p^*$ the next two inequalities are reversed):

\begin{eqnarray}
\nonumber
\nonumber
p^*+(p'-p^*)e^{-(\lambda_0+\lambda_1)\Delta n}\leq p''.
\end{eqnarray}

Equivalently, both for $p'>p''>p^*$ and for $p'<p''<p^*$:

\begin{eqnarray}
\nonumber
\nonumber
e^{-(\lambda_0+\lambda_1)\Delta n}\leq \frac{p''-p^*}{p'-p^*},
\end{eqnarray}

\begin{eqnarray}
\nonumber
\nonumber
e^{-\Delta n}\geq \left(\frac{p''-p^*}{p'-p^*}\right)^{-\frac{1}{\lambda_0+\lambda_1}}.
\end{eqnarray}

We can conclude that

\begin{equation}\label{eq lim time}
\lim_{\Delta\to 0} e^{-\Delta n}= \left(\frac{p''-p^*}{p'-p^*}\right)^{-\frac{1}{\lambda_0+\lambda_1}}.
\end{equation}

The discounted time it takes for the belief to get from $p'$ to $p''$ is then:

\begin{eqnarray}\label{eq yslide}
Y^{slide, \Delta}_{p',p''}&=(1-e^{-\Delta r}\sum_{k=1}^n \left(e^{-r\Delta}\right)^{k-1}\\
\nonumber
&=(1-e^{-\Delta r})\frac{1-e^{-r\Delta n}}{1-e^{-\Delta r}}\\
\nonumber
&=1-e^{-r\Delta n}.
\end{eqnarray}

Plugging the limit of Eq (<ref>) in Eq. (<ref>) we obtain:

\begin{equation}\label{eq Y slide}\lim_{\Delta\to 0}Y^{slide, \Delta}_{p',p''}=1-\left(\frac{p''-p^*}{p'-p^*}\right)^{-\frac{r}{\lambda_0+\lambda_1}}=Y^{slide}_{p',p''}.\end{equation}

Next, we use the results of the convergence of discounted discrete splitting and sliding times to the respective continuous times to prove the convergence of $w_\Delta (p,\sigma^*)$ to $v_{cont}(p)$. This is done by induction.
The induction is over the continuity intervals: first we show the convergence for beliefs in the interval $[p_0,p_1]$, then for beliefs in continuity intervals $[p_{-j}, p_{-j+1})$, $j\in\{2,\ldots m\}$ and finally for beliefs in continuity intervals $(p_j,p_{j+1}]$, $j\in\{1,\ldots m'\}$.

Beliefs in continuity interval $[p_0,p_1]$.  Strategy $\sigma^*$ instructs repeatedly splitting of the belief between $p_0$ and $p_1$. Conclusion <ref> with $p'=p_0$ and $p''=p_1$ gives the putative value obtained when using $\sigma^*$ for the relevant beliefs in the continuous time model. This conclusion is derived from Eq. (<ref>) and Eq. (<ref>). However, from Eq. (<ref>), this is also the limit of the putative value for the discrete time model as $\Delta$ diminishes.

Beliefs in continuity interval $[p_{-j},p_{-j+1}], j\in\{1,\ldots,m\}$.
For the continuity segments $[p_{-j},p_{-j+1}]$  the strategy $\sigma^*$ instructs splitting the belief between $p_{-j}$ and $p_{-j+1}$. From Eq. (<ref>) and by induction, the putative value in the discrete time model converges to the value in the continuous time model.

Beliefs in continuity interval $[p_{j},p_{j+1}], j\in\{1,\ldots,m'-1\}$.

For beliefs in $[p_j, q_j]$ the strategy $\sigma^*$ instructs revealing no information (meaning the belief slides towards $p_j$). During the sliding time the instantaneous value is $h_j$, and afterwards it is the putative value at $p_j$. From Eq. (<ref>) and by induction we have that the resulting combination in the discrete time model converges to the one in the continuous time model: the discounted time the sender obtains $h_j$ converges, and the value at $p_j$ converges by induction (in fact, the induction first is for beliefs in $[p_1,q_1]$, and the next paragraph completes the induction).

For beliefs in $[q_j, p_{j+1}]$ the strategy $\sigma^*$ instructs repeatedly splitting the belief between $q_j$ and $p_{j+1}$. Again, by Eq. (<ref>) and by induction, we complete the proof.


# Minimum $2$\- edge strongly biconnected spanning directed subgraph problem

Raed Jaberi

###### Abstract

Wu and Grumbach introduced the concept of strongly biconnected directed
graphs. A directed graph $G=(V,E)$ is called strongly biconnected if the
directed graph $G$ is strongly connected and the underlying undirected graph
of $G$ is biconnected. A strongly biconnected directed graph $G=(V,E)$ is said
to be $2$-edge-strongly biconnected if it has at least three vertices and the
directed subgraph $(V,E\setminus\left\\{e\right\\})$ is strongly biconnected
for all $e\in E$. Let $G=(V,E)$ be a $2$-edge-strongly biconnected directed
graph. In this paper we study the problem of computing a minimum size subset
$H\subseteq E$ such that the directed subgraph $(V,H)$ is $2$-edge-strongly
biconnected.

###### keywords:

Directed graphs , Connectivity , Approximation algorithms , Graph algorithms ,
strongly connected graphs

††journal: arXiv

##  1 Introduction

Wu and Grumbach [26] introduced the concept of strongly biconnected directed
graphs, A directed graph $G=(V,E)$ is called strongly biconnected if the
directed graph $G$ is strongly connected and the underlying undirected graph
of $G$ is biconnected. An edge $e$ in a strongly biconnected directed graph
$G=(V,E)$ is b-bridge if the subgraph $(V,E\setminus\left\\{e\right\\})$ is
not strongly biconnected. A strongly biconnected directed graph $G=(V,E)$ is
called $k$-edge-strongly biconnected if for each $L\subset E$ with $|L|<k$,
the subgraph $(V,E\setminus L)$ is strongly biconnected. A strongly
biconnected directed graph $G=(V,E)$ is therefore $2$-edge-strongly
biconnected if and only if it has no b-bridges. Given a $k$-edge-strongly
biconnected directed graph $G=(V,E)$, the minimum $k$-edge-strongly
biconnected spanning subgraph problem (denoted by MKESBSS) is to compute a
minimum size subset $E_{ke}\subseteq E$ such that the directed subgraph
$(V,E_{ke})$ is $k$-edge-strongly biconnected. In this paper we study the
MKESBSS problem for $k=2$. Note that optimal solutions for minimum $2$-edge-
connected spanning subgraph problem are not necessarily feasible solutions for
the $2$-edge strongly biconnnected spanning subgraph problem, as shown in
Figure 1.

$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$11$$12$

$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$11$$12$

$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$11$$12$

Figure 1: (a) A $2$-edge strongly biconnected directed graph. (b) This
subgraph is not $2$-edge strongly biconnected. But it is an optimal solution
for the minimum $2$-edge-connected spanning subgraph problem. (c) An optimal
solution for the minimum $2$-edge strongly biconnected spanning subgraph
problem

Let $G=(V,E)$ be a $k$-edge-connected directed graph. The problem of
calculating a minimum size $k$-edge-connected spanning subgraph of $G$ is NP-
hard for $k\geq 1$ [6, 1]. Clearly, the MKESBSS problem is NP-hard for $k\geq
1$. Results of Edmonds [2] and Mader [21] imply that the number of edges in
each minimal $k$-edge-connected directed graph is at most $2kn$ [1]. Cheriyan
and Thurimella [1] gave a $(1+4/\sqrt{k})$-approximation algorithm for the
minimum $k$-edge-connected spanning subgraph problem. Moreover, Cheriyan and
Thurimella [1] provided a $(1+1/k)$-approximation algorithm for the minimum
$k$-vertex-connected spanning subgraph problem. Georgiadis [10] improved the
running time of this algorithm for the minimum $2$-vertex-connected spanning
subgraph (M2VCSS) problem and presented an efficient linear time approximation
algorithm for the M2VCSS problem. Georgiadis et al. [11] presented efficient
approximation algorithms based on the results of [8, 7, 12, 4] for the M2VCSS
problem. Strongly connected components of a directed graph and blocks of an
undirected graphs can be calculated in $O(n+m)$ time using Tarjan’s algorithm
[24, 25]. Wu and Grumbach [26] introduced the concept of strongly biconnected
directed graph and strongly biconnected components. Italiano et al. [12, 13]
provided linear time algorithms for computing all the strong articulation
points and strong bridges of a directed graph. Georgiadis et al. [11] gave
efficient approximation algorithms based on the results of [8, 7, 12, 4, 3]
for the minimum $2$-vertex connected spanning subgraph problem. Jaberi [17,
15, 14] studied twinless articulation points and some related problems.
Moreover, He studied b-bridges and some related problems [18, 19]. Georgiadis
and Kosinas [9] proved that twinless articulation points and twinless bridges
can be found in $O(n+m)$ time. Jaberi studied minimum $2$-vertex strongly
biconnected spanning directed subgraph problem in [16] and minimum $2$-vertex-
twinless connected spanning subgraph problem in [20]. In this paper we study
the minimum $2$-edge strongly biconnected spanning subgraph problem (denoted
by M2ESBSS).

##  2 Approximation algorithm for the Minimum $2$\- edge strongly biconnected
spanning directed subgraph problem

In this section we present an approximation algorithm (Algorithm 2.2) for the
M2ESBSS Problem.

######  Lemma 2.1.

Let $G=(V,E)$ be a strongly biconnected directed graph and let $U\subseteq E$
such that the directed subgraph $G_{1}=(V,U)$ is strongly connected but the
underlying graph of $G_{1}$ is not biconnected. Let $(v,w)$ be an edge in
$E\setminus U$ such that $v,w$ are not in the same strongly biconnected
component of $G_{1}$. Then the directed subgraph
$(V,U\cup\left\\{(v,w)\right\\})$ has fewer strongly biconnected components
than $G_{1}$.

###### Proof.

There is a simple path $p$ from $w$ to $v$ in $g_{1}$ since $G_{1}$ is
strongly connected. Moreover, the edge $(v,w)$ and the path $p$ form a simple
cycle in the subgraph $(V,U\cup\left\\{(u,w)\right\\})$. Since the underlying
graph of the subgraph $(V,U\cup\left\\{(u,w)\right\\})$ contains a biconnected
component that contains $v$ and $w$, the vertices $v$ and $w$ are in the same
strongly biconnected component of the subgraph
$(V,U\cup\left\\{(u,w)\right\\})$. $\Box$

######  Algorithm 2.2.

Input: A $2$-edge strongly biconnected directed graph $G=(V,E)$
---
Output: a $2$-edge strongly biconnected subgraph of $G$
1 | identify a subset $U\subseteq E$ such that $H=(V,U)$ is a minimal
2 |  $2$-edge-connected subgraph of $G$.
3 |  if the subgraph $H=(V,U)$ is $2$-edge strongly biconnected then
4 |  | output $H=(V,U)$
5 | else
6 |  | $E_{2e}\leftarrow U$
7 |  |  $G_{2e}\leftarrow(V,E_{2e})$
8 |  |  while the underlying graph of $G_{2e}$ is not biconnected do
8 |  |  | compute the strongly biconnected components of $G_{2e}$
11 |  |  | find an edge $(v,w)\in E\setminus E_{2e}$ such that $v,w$ are not in
12 |  |  |  | the same strongly biconnected components of $G_{2e}$.
13 |  |  |  | add $(v,w)$ to $E_{2e}$.
14 |  | compute the b-bridges of $G_{2e}=(V,E_{2e})$.
15 |  |  for each b-bridge $t\in V$ do
16 |  |  |  while the underlying graph of $G_{2e}\setminus\left\\{t\right\\}$ is not biconnected do
17 |  |  |  | compute the strongly biconnected components of $G_{2s}\setminus\left\\{t\right\\}$
18 |  |  |  | find an edge $(u,w)\in E\setminus E_{2e}$ such that $u,w$ are not in
19 |  |  |  | the same strongly biconnected components of $G_{2e}\setminus\left\\{t\right\\}$.
20 |  |  |  | add $(u,w)$ to $E_{2e}$.
21 |  |  | output $G_{2e}$

######  Lemma 2.3.

The output of Algorithm 2.2 is $2$-edge strongly biconnected.

###### Proof.

It follows from Lemma 2.1. $\Box$

The following lemma shows that any $2$-edge-strongly biconnected directed
subgraph of a $2$-edge-strongly biconnected directed graph has at least $2n$
edges.

######  Lemma 2.4.

Let $G=(V,E)$ be a $2$-edge-strongly biconnected directed graph. Let
$U\subseteq E$ be an optimal solution for the M2ESBSS problem. Then the
subgraph $(V,U)$ has at least $2n$ edges.

###### Proof.

the subgraph $(V,U)$ has no strong bridges since it has no b-bridges.
Therefore, the subgraph $(V,U)$ is $2$-edge connected. $\Box$

Let $i$ be the number of b-bridges in $H$. The following lemma shows that
Algorithm 2.2 has an approximation factor of $((5+i)/2)$.

######  Theorem 2.5.

Let $i$ be the number of b-bridges in $H$. Then, $|E_{2e}|\leq i(n-1)+5n$.

###### Proof.

Results of Edmonds [2] and Mader [21] imply that the number of edges in $H$ is
at most $4n$ [1]. Moreover, by Lemma 2.4, any $2$-edge-strongly biconnected
directed subgraph of a $2$-edge-strongly biconnected directed graph has at
least $2n$ edges. Algorithm 2.2 adds at most $n-1$ edge to $E_{2e}$ in while
loop of lines $8$–$13$ since the number of strong biconnected components of
any directed graph is at most $n$. For every b-bridge in line $16$, Algorithm
2.2 adds at most $n-1$ edge to $E_{2e}$ in while loop. Consequently,
$|E_{2e}|\leq i(n-1)+5n$. $\Box$

######  Theorem 2.6.

Algorithm 2.2 runs in $O(n^{2}m)$ time.

###### Proof.

A minimal $2$-edge-connected subgraph can be found in time $O(n^{2})$ [1]. The
strongly biconnected components of a directed graph can be found in linear
time [26]. Moreover, by Lemma 2.1, lines $16$–$20$ take $O(nm)$ time. $\Box$

##  3 Open Problems

Results of Mader [22, 23] imply that the number of edges in each minimal
$k$-vertex-connected undirected graph is at most $kn$ [1]. Results of Edmonds
[2] and Mader [21] imply that the number of edges in each minimal $k$-vertex-
connected directed graph is at most $2kn$ [1]. Moreover, Results of Edmonds
[2] and Mader [21] imply that the number of edges in each minimal $k$-edge-
connected directed graph is at most $2kn$ [1]. Jaberi proved that each minimal
$2$-vertex-strongly biconnected directed graph has at most $7n$ edges. The
proof in is based on results of Mader [22, 23, 21] and Edmonds [2].

We leave as open problem whether the number of edges in each minimal $2$-edge
strongly biconnected directed graph is at most $7n$ edges.

Cheriyan and Thurimella [1] gave a $(1+\lfloor
4/\sqrt{k}\rfloor\rfloor)$-approximation algorithm for the minimum $k$-edge-
connected spanning subgraph problem for directed. For $k=2$, the second step
of this algorithm can be modified in order to obtain a feasible solution for
the M2ESBSS problem. An open problem is whether this algorithm has a good
approximation factor for the M2ESBSS problem.

## References

  * [1] J. Cheriyan, R. Thurimella, Approximating Minimum-Size $k$-Connected Spanning Subgraphs via Matching. SIAM J. Comput. $30(2):528$–$560(2000)$
  * [2] J. Edmonds, Edge-disjoint branchings. Combinatorial Algorithms, pages $91$–$96$, $1972$
  * [3] Donatella Firmani, Loukas Georgiadis, Giuseppe F. Italiano, Luigi Laura, Federico Santaroni: Strong Articulation Points and Strong Bridges in Large Scale Graphs. Algorithmica $74(3)$: $1123$–$1147(2016)$
  * [4] D. Firmani, G.F. Italiano, L. Laura, A. Orlandi, F. Santaroni, Computing strong articulation points and strong bridges in large scale graphs, SEA, LNCS $7276$, ($2012$) $195$–$207$.
  * [5] Loukas Georgiadis, Evangelos Kosinas, Linear-Time Algorithms for Computing Twinless Strong Articulation Points and Related Problems. ISAAC $2020$ $38:1$–$38:16$
  * [6] M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN $0$–$7167$–$1044$–$7$
  * [7] L. Georgiadis, Testing $2$-vertex connectivity and computing pairs of vertex-disjoint s-t paths in digraphs, In Proc. $37$th ICALP, Part I, LNCS $6198$ ($2010$) $738$–$749$.
  * [8] Loukas Georgiadis, Robert E. Tarjan, Dominator Tree Certification and Divergent Spanning Trees. ACM Trans. Algorithms $12(1):11:1$–$11:42(2016)$
  * [9] Loukas Georgiadis, Evangelos Kosinas, Linear-Time Algorithms for Computing Twinless Strong Articulation Points and Related Problems. ISAAC $2020$ $38:1$–$38:16$
  * [10] L. Georgiadis: Approximating the Smallest 2-Vertex Connected Spanning Subgraph of a Directed Graph. ESA $2011:13$–$24$
  * [11] L. Georgiadis, G. F. Italiano, A. Karanasiou: Approximating the smallest 2-vertex connected spanning subgraph of a directed graph. Theor. Comput. Sci. $807$: $185$–$200(2020)$
  * [12] G.F. Italiano, L. Laura, F. Santaroni, Finding strong bridges and strong articulation points in linear time, Theoretical Computer Science $447$ ($2012$) $74$–$84$.
  * [13] G. F. Italiano, L. Laura, F. Santaroni, Finding Strong Bridges and Strong Articulation Points in Linear Time. COCOA $(1)2010:157$–$169$
  * [14] Raed Jaberi, $2$-edge-twinless blocks, Bulletin des Sciences Mathématiques, Volume $168$, $102969$, ISSN $0007$–$4497$, $(2021)$, https://doi.org/10.1016/j.bulsci.2021.102969.
  * [15] Raed Jaberi, Computing 2-twinless blocks, Discrete Mathematics Letters, $29$–$33$, Volume $5(2021)$, DOI: 10.47443/dml.2020.0037
  * [16] Raed Jaberi, Minimum 2-Vertex Strongly Biconnected Spanning Directed Subgraph Problem Discrete Mathematics Letters, $40$–$43$, Volume $7(2021)$ DOI: 10.47443/dml.2021.0024
  * [17] Raed Jaberi, Twinless articulation points and some related problems. CoRR abs/1912.11799 $(2019)$
  * [18] Raed Jaberi, b-articulation points and b-bridges in strongly biconnected directed graphs. CoRR abs/2007.01897 $(2020)$
  * [19] Raed Jaberi, 2-blocks in strongly biconnected directed graphs. CoRR abs/2007.09793 $(2020)$
  * [20] Raed Jaberi, Minimum $2$-vertex-twinless connected spanning subgraph problem. CoRR abs/2001.03788 (2020)
  * [21] W. Mader, Minimal $n$-fach zusammenhängende Digraphen. J. Comb. Theory, Ser. B $38(2):102$–$117(1985)$
  * [22] W. Mader, Minimale n-fach kantenzusammenhängende Graphen. Math. Ann., $191:21$ –$28,1971$
  * [23] W. Mader, Ecken vom Grad n in minimalen n-fach zusammenhängenden Graphen. Arch. Math. (Basel), $23:219$–$224,1972$
  * [24] R. E. Tarjan, Depth First Search and Linear Graph Algorithms, SIAM J. Comput.,$1(2)(1972),146$–$160$
  * [25] Jens M. Schmidt: A simple test on $2$-vertex- and $2$-edge-connectivity. Inf. Process. Lett. $113(7):241$-$244(2013)$
  * [26] Z. Wu, S. Grumbach, Feasibility of motion planning on acyclic and strongly connected directed graphs. Discret. Appl. Math. $158(9):1017$–$1028(2010)$


4232

# Towards Vertical Privacy-Preserving Symbolic Regression via Secure
Multiparty Computation

Du Nguyen Duy<EMAIL_ADDRESS>Software Competence Center
HagenbergSoftwarepark 32aHagenbergAustria4232 ,  Michael Affenzeller
<EMAIL_ADDRESS>University of Applied Sciences Upper
AustriaSoftwarepark 11HagenbergAustria and  Ramin Nikzad-Langerodi
<EMAIL_ADDRESS>Software Competence Center
HagenbergSoftwarepark 32aHagenbergAustria4232

###### Abstract.

Symbolic Regression is a powerful data-driven technique that searches for
mathematical expressions that explain the relationship between input variables
and a target of interest. Due to its efficiency and flexibility, Genetic
Programming can be seen as the standard search technique for Symbolic
Regression. However, the conventional Genetic Programming algorithm requires
storing all data in a central location, which is not always feasible due to
growing concerns about data privacy and security. While privacy-preserving
research has advanced recently and might offer a solution to this problem,
their application to Symbolic Regression remains largely unexplored.
Furthermore, the existing work only focuses on the horizontally partitioned
setting, whereas the vertically partitioned setting, another popular scenario,
has yet to be investigated. Herein, we propose an approach that employs a
privacy-preserving technique called Secure Multiparty Computation to enable
parties to jointly build Symbolic Regression models in the vertical scenario
without revealing private data. Preliminary experimental results indicate that
our proposed method delivers comparable performance to the centralized
solution while safeguarding data privacy.

Symbolic Regression, Genetic Programming, Privacy-Preserving, Federated
Learning, Secure Multiparty Computation

††copyright: none

##  1\. Introduction

Symbolic Regression (SR) is a machine learning technique that seeks to find
the underlying mathematical relationship between the input and output
variables without imposing any preconceived notions about the structure of the
model. Compared to other commonly used data-driven methods, such as Support
Vector Machines or Deep Neural Networks, it has the advantage of producing
models that are easy to interpret and understand since the resulting
expression can be represented in a form that is familiar to humans
(Affenzeller et al., 2014). This can be particularly useful in fields such as
physics, engineering, and finance, where the ability to understand and analyze
the hidden equations is critical.

Traditional methods of SR involve using evolutionary algorithms, particularly
Genetic Programming (GP) (Koza, 1994). In GP-based SR (GPSR), a population of
candidate expressions is evolved using genetic operators, such as selection,
crossover, and mutation, to improve a fitness function (e.g., Mean Squared
Error) that evaluates the quality of the expressions. While GPSR can be
effective, growing concerns about data privacy and ownership might limit its
applicability to real-world scenarios. More specifically, during model
training, the whole dataset is needed to evaluate the quality of solutions.
Hence, the existing GP methods often assume that data is stored in one place
(i.e., a server or a cluster) and can be easily accessible. However, this
assumption is very challenging, if not impossible, to satisfy when the data is
distributed among different parties who might not share the same interests. In
such situations, even though data from all parties must be analyzed
simultaneously to achieve optimal performance, data centralization faces many
challenges.

On the one hand, data owners might be unwilling to share private data because
it is valuable or incorporates sensitive information. On the other hand,
nowadays, there are laws and regulations that restrict organizations from
freely exchanging data (Yang et al., 2019). Overall, data privacy and security
have become a prevalent topic not only for GPSR but for all other data-driven
techniques. During the last few years, many frameworks have been proposed for
training models while upholding data privacy and ownership, such as Federated
Learning (FL) (Konečnỳ et al., 2016), Secure Multi-party Computation (MPC)
(Mohassel and Zhang, 2017), Homomorphic Encryption (HE) (Gentry, 2009), and
Differential Privacy (DP) (Dwork et al., 2014). Based on these studies,
numerous privacy-preserving machine learning algorithms have been developed.
The existing works include linear regression (Gascón et al., 2016), tree-based
models (Liu et al., 2020), neural network architectures (Wagh et al., 2019),
and latent variables-based models (Nguyen Duy et al., 2022). Nevertheless,
relatively limited attention has been paid to their adoption in GPSR,
considering its wide-ranging potential.

As mentioned previously, the challenge in performing GPSR in a privacy-
preserving manner is to evaluate the fitness value on data scattered across
different organizations. There are two common data distribution schemas:
horizontal setting and vertical setting. Horizontal setting refers to a
scenario where different parties possess datasets that share the same variable
space but have minimal overlap in the sample space. This partitioning of data
is a common approach, particularly in the cross-device setting, where various
users aim to enhance their model performance for the same task. In contrast,
in a vertical setting, the local datasets share the same sample space but
differ in the feature space. This scheme is especially common in cooperation
among different enterprises across a value chain. While an FL-based GP
framework for training SR on horizontally distributed data has been proposed
recently (Dong et al., 2022), an approach for performing secure GPSR in the
vertical scenario is still missing.

To this end, we propose an MPC-based framework called Privacy Preserving
Symbolic Regression (PPSR) for training symbolic regression models on
vertically distributed data. To the best of our knowledge, this is the first
study that addresses this problem. In the context of the preliminary
experiment, PPSR yields comparable performance to the centralized GPSR
approach on the simulated datasets.

##  2\. Background

###  2.1. Symbolic Regression

As mentioned previously, Symbolic Regression (SR) is a form of regression
analysis that aims to find a mathematical expression (a symbolic model) that
best describes the relationship between a set of independent variables and a
dependent variable of a given dataset. When Genetic Programming (GP) is used
for conducting SR, the overall process (depicted in Figure 1) can be described
step-by-step as follows:

  * •

Step 1: Population Initialization. The first step is to initialize a
population of candidate solutions. Each candidate solution is represented as a
tree structure (see Figure 2), where the nodes represent mathematical
operators ($+$, $-$, $\times$, /, $sin(\cdot)$, $cos(\cdot)$, …), and the
leaves represent variables, constants or coefficients.

  * •

Step 2: Fitness Evaluation. Each candidate solution is evaluated by computing
its fitness on the given dataset. This is done by comparing the candidate
solution’s predicted values with the dependent variables’ actual values.

  * •

Step 3: Selection. The fittest candidate solutions are selected for
reproduction. Selection is typically made using a fitness-based approach, such
as tournament selection or roulette wheel selection.

  * •

Step 4: Variation. The selected candidate solutions are modified through a
combination of crossover and mutation operators. In the standard case,
crossover involves swapping subtrees between two candidate solutions, while
mutation involves randomly changing a subtree in a candidate solution.

  * •

Step 5: Fitness Evaluation. Evaluate the fitness of the new candidate
solutions by calculating the error between the predicted output of the
solution and the actual output of the training data.

  * •

Step 6: Replacement. Replace the old population with the new population of
candidate solutions. The fittest solutions from the previous generation may be
kept, while others may be replaced by the new solutions.

  * •

Step 7: Termination. Repeat steps 3 to 6 until a termination criterion is met.
This criterion can be a maximum number of generations, a minimum fitness
threshold, or a maximum amount of computation time. The final generation of
candidate solutions is typically sorted by fitness, and the fittest candidate
solution is selected as the solution to the symbolic regression problem.

During the entire process, Fitness Evaluation is the only module where the
algorithm needs to access the whole dataset. Thus, how to perform it while
protecting data privacy is the key to enabling the construction of a GP-based
SR model in a privacy-preserving manner.

Figure 1. An illustration of the GPSR workflow. Figure 2. An illustration of a
tree structure.

Suppose the given data is expressed as:

(1) $D=\\{d_{i}\ |\ d_{i}=(x_{i1},x_{i2},...,x_{in},y_{i}),i=1,2,...,m\\}$

where $n$ represents the number of input variables, $m$ is the number of
sample data, $x_{ik}$ means the $k^{th}$ variable value of the $i^{th}$ sample
data, and $y_{i}$ denotes the corresponding target.

The fitness function $F(\cdot)$ is typically a measure of how well a candidate
solution $f(\cdot)$ fits the training data $D$, and it can take various forms
depending on the specific problem and the goals of the analysis. A widely used
fitness function is Mean Square Error ($MSE$), which is defined as follows:

(2) $F=\frac{1}{m}\sum_{i=1}^{m}(y_{i}-\hat{y}_{i})^{2}$

where $\hat{y}_{i}=f(x_{i1},x_{i2},...,x_{in})$ is the predicted value for the
$i^{th}$ observation using the candidate solution.

Other often used functions are Root Mean Squared Error ($RMSE$) and R-Squared
($R^{2}$). However, regardless of the choice of the fitness function, the same
problem arises when $D$ is jointly owned by different clients who do not want
to expose private data.

###  2.2. Horizontal Federated Symbolic Regression

In (Dong et al., 2022), the authors proposed a horizontal federated GP
framework that enables the construction of GPSR models without disclosing
local data from data holders. The proposed framework consists of multiple
clients labeled as $C_{1}$ to $C_{K}$ and a central server, as shown in Figure
3. Initially, the server generates a population and broadcasts it to all
clients. Then, the clients calculate local fitness for all solutions (denoted
as a vector $\mathbf{z}_{j}$) in parallel using private data and then send
local fitness along with the local weight (denoted as $w_{j}$) back to the
server. The local weight indicates the client’s relative impact on the global
model and is proportional to the amount of data contributed. The server uses a
non-parametric clustering technique called Mean Shift Aggregation (Dong et
al., 2022) to estimate global fitness values. Finally, the server performs
genetic operations to create a new population and then repeats the process
until the stopping criteria are met.

Figure 3. Federated Genetic Programming framework.

The federated architecture employed here helps to protect privacy as it allows
local clients to keep their training data confidential while transmitting only
the fitness information to the server. However, since it assumes clients can
calculate the fitness value independently, this framework is only feasible in
the horizontal setting when the local datasets share the same feature space.
In contrast, in a vertical scenario, when the generated expressions involve
variables belonging to different clients, no single client can estimate the
fitness alone because it cannot access all the involved variables. Therefore,
the key distinction between our method and this work is our ability to handle
vertically distributed data, which is achieved by leveraging a privacy-
preserving technique called Secure Multiparty Computation.

###  2.3. Secure Multiparty Computation

Secure Multiparty Computation (MPC) is a cryptographic approach that enables
computation on data from different clients, such that the participants gain no
additional information about each others’ inputs, except what can be learned
from the public output of the algorithm. The underlying mechanics depend on
the protocol being applied. In this work, we use the 3-party secure
computation protocol (3PC), which is a framework extensively employed in
various privacy-preserving machine learning systems (Demmler et al.,
2015)(Wagh et al., 2019).

In the 3PC scheme, the three parties involved are denoted as $P_{0}$, $P_{1}$,
and $P_{2}$ (see Figure 4). All operations are performed in the ring
$\mathbb{Z}_{2^{L}}$ (integers modulo $2^{L}$), where each number is
represented as an $L$-bit integer. To securely evaluate a function $F(\cdot)$,
the data owners first share their private values with $P_{0}$ and $P_{1}$
using a secret sharing scheme. Then $P_{0}$ and $P_{1}$ will proceed to
evaluate $F(\cdot)$ over the secret shares with the support of $P_{2}$. The
output will be similarly secret-shared, meaning $P_{0}$ and $P_{1}$ each own
just a share of the result. Only when the shares are recombined the real
result is revealed.

Figure 4. An illustration of the 3PC scheme.

The sharing of a value $x$ is denoted by $\langle x\rangle=\\{\langle
x\rangle_{0},\langle x\rangle_{1}\\}$, where $\langle
x\rangle_{i}\in\mathbb{Z}_{2^{L}}$ indicates $P_{i}$’s share of $x$. To share
a secret $x$, the secret holder picks a random number $r$ from
$\mathbb{Z}_{2^{L}}$, assigns $\langle x\rangle_{0}:=r$ and $\langle
x\rangle_{1}:=x-r$, and then sends $\langle x\rangle_{0}$ and $\langle
x\rangle_{1}$ and to $P_{0}$ and $P_{1}$ respectively. Because of the way the
shares are created, from $P_{i}$’s perspective, they are merely random
numbers. However, when they are both sent to some party $P_{i}$, $P_{i}$ can
reconstruct $x$ immediately by summing up the two shares, i.e., $x=\langle
x\rangle_{0}+\langle x\rangle_{1}$.

Due to their homomorphic properties, the secret shares can be utilized to
implement secure computations. Addition and multiplication operations can be
easily performed on the shared values as follows:

  * •

Addition/Subtraction of a secret shared value $x$ to a public value (values
known to all parties) $a$: $P_{0}$ maintains $\langle x\rangle_{0}\pm a$, and
$P_{1}$ keeps $\langle x\rangle_{1}$.

  * •

Multiplication of a secret shared value $x$ with a public value $a$: The two
parties multiply their shares with $a$ respectively, i.e., $P_{0}$ gets
$\langle x\rangle_{0}\cdot a$, $P_{1}$ gets $\langle x\rangle_{1}\cdot a$.

  * •

Addition/Subtraction of two secret shared values $x$ and $y$: The two parties
add/subtract their shares respectively, i.e., $P_{0}$ gets $\langle
x\rangle_{0}\pm\langle y\rangle_{0}$, and $P_{1}$ gets $\langle
x\rangle_{1}\pm\langle y\rangle_{1}$.

  * •

Multiplication of two secret shared values $x$ and $y$ is implemented using
random Beaver triples (Beaver, 1992), ($a$, $b$, $c$) with $c=ab$, that
$P_{2}$ provides. The details of this operation are listed in Algorithm 1. It
is straightforward to prove that $\langle xy\rangle_{0}+\langle
xy\rangle_{1}=xy$.

Participants: $P_{0}$, $P_{1}$, and $P_{2}$

Input: $P_{i}$ holds {$\langle x\rangle_{i}$, $\langle y\rangle_{i}$},
$i\in\\{0,1\\}$

Output: $P_{i}$ gets $\langle xy\rangle_{i}$, $i\in\\{0,1\\}$

1 Function  _Mul(_$\langle x\rangle$ , $\langle y\rangle$_)_:

2 $P_{2}$ do:

3 Generate a Beaver triple $(a,b,c)$ such that $c=ab$

4 Generate for $i\in\\{0,1\\}$, $\langle a\rangle_{i},\langle
b\rangle_{i},\langle c\rangle_{i}$ and send to $P_{i}$

5 end

6

7 for  _$i\in\\{0,1\\}$ , $P_{i}$_ do

8 $\langle\epsilon\rangle_{i}=\langle x\rangle_{i}-\langle a\rangle_{i}$

9 $\langle\delta\rangle_{i}=\langle y\rangle_{i}-\langle b\rangle_{i}$

10 Reconstruct $\epsilon$ and $\delta$ by exchanging shares. $\epsilon$ and
$\delta$ are now public values.

11 Compute $\langle xy\rangle_{i}=\langle c\rangle_{i}+\epsilon\langle
b\rangle_{i}+\langle a\rangle_{i}\delta+i\epsilon\delta$

12 end for

13

14 End

Algorithm 1 Secret Sharing Multiplication

The combination of addition and multiplication operations can be used to
calculate linear and polynomial functions. For more complex functions that
cannot be efficiently computed using only these operations, standard
approximations can be utilized.

In our implementation, we leverage a Python package called CRYPTEN (Knott et
al., 2021) for performing secure computations. This library employs limit
approximation to compute exponentials, Householder iterations to compute
logarithms, Newton-Raphson iterations to compute reciprocals, and the
repeated-squaring method to compute sine and cosine functions. As 3PC is
performed on the integer ring $\mathbb{Z}_{2^{L}}$, when the inputs are in
floating-point format, they must be converted into fixed-point. CRYPTEN
handles this conversion by using fixed-point encoding (Mohassel and Zhang,
2017). More specifically, to obtain an integer value $x$ from a floating-point
value $x_{\mathbb{R}}$, it multiplies $x_{\mathbb{R}}$ with a large scaling
factor $2^{B}$ and rounds the result to the nearest integer $x=\lfloor
2^{B}x_{\mathbb{R}}\rceil$. And to decode an integer value, $x$, it calculates
$x_{\mathbb{R}}\approx x/2^{B}$. This method is naturally suitable for
addition and subtraction operations. However, considering the multiplication
of two numbers $x_{\mathbb{R}}$ and $y_{\mathbb{R}}$, we get $\lfloor
2^{B}x_{\mathbb{R}}\rceil\lfloor 2^{B}x_{\mathbb{R}}\rceil\approx 2^{B}\lfloor
2^{B}x_{\mathbb{R}}y_{\mathbb{R}}\rceil$. Therefore, after every
multiplication, the output will be scaled down by a factor of $2^{B}$.

##  3\. Vertical Privacy-Preserving Symbolic Regression

###  3.1. Preliminaries

In this study, we concentrate on the situation where $K$ clients
$C_{1},C_{2},...,C_{K}$ want to train an SR model on the joint data vertically
partitioned among them. Suppose $C_{j}$ secretly owns
$\mathbf{X}_{j}\in\mathbb{Z}^{m\times n_{j}}_{2^{L}}$ where $m$ represents the
number of observations, and $n_{j}$ represents the number of private
variables. In this scenario, only $C_{K}$ has access to the target variable
$\mathbf{y}\in\mathbb{Z}^{m\times 1}_{2^{L}}$. The joint dataset can be
denoted as $D=\\{\mathbf{X},\mathbf{y}\\}$ where
$\mathbf{X}=[\mathbf{X}_{1}|\mathbf{X}_{2}|...|\mathbf{X}_{K}]\in\mathbb{Z}^{m\times
n}_{2^{L}}$ with $n=\sum_{j=1}^{K}n_{j}$.

Even though we do not explicitly mention the conversion between real-valued
numbers and integer numbers in this section, it can be assumed to occur and
solved using the fixed-point encoding protocol explained previously.

###  3.2. Methodology

The proposed framework requires four parties (servers) which are labelled as
$P_{0}$, $P_{1}$, $P_{2}$, and $P_{3}$. While any client can assume the role
of $P_{3}$, $P_{2}$ must be a third party trusted by all clients. When there
are only two clients, they themselves can operate as $P_{0}$ and $P_{1}$. If
more clients are involved, two of them can be promoted as $P_{0}$ and $P_{1}$.
The overall workflow of PPSR includes two phases: Secret Data Sharing and
Model Training.

The phase of Secret Data Sharing involves all clients uploading their private
data to $P_{0}$ and $P_{1}$ in a secret-shared manner, as depicted in Figure
5. In Section 2.3, the sharing of a single value has been explained. To
securely share a matrix $\mathbf{X}_{j}$ or a vector $\mathbf{y}$ (only
$C_{K}$), clients simply apply secret sharing element-wise. The details of
this process are specified in Algorithm 2. As a result, each $P_{i}$ holds a
share of $\mathbf{X}$ and $\mathbf{y}$, referred to as
$\langle\mathbf{X}\rangle_{i}$ and $\langle\mathbf{y}\rangle_{i}$
respectively, such that $\sum_{i=0}^{1}\langle\mathbf{X}\rangle_{i}=X$ and
$\sum_{i=0}^{1}\langle\mathbf{y}\rangle_{i}=\mathbf{y}$. It is strictly
required that $P_{0}$ and $P_{1}$ are trustworthy and do not collude;
otherwise, they could exchange the shares and gain access to the actual
dataset.

Once the data is shared with the computing parties ($P_{0}$ and $P_{1}$), the
Model Training phase commences at $P_{3}$. The process involves Population
Initialization, Fitness Evaluation, Selection, Variation, Replacement, and
Termination, which is similar to the standard GP process. However, the unique
aspect of PPSR is in the Fitness Evaluation step where fitness values are
computed over the secret shares held by $P_{0}$ and $P_{1}$ rather than using
the raw data.

In order to assess the quality of a candidate expression $f(\cdot)$, $P_{3}$
will forward both the function and the fitness function $F(\cdot)$ (e.g.,
$MSE$, $RMSE$, $R^{2}$) to $P_{0}$ and $P_{1}$. Then these two parties will
estimate their shares of the predicted values
($\langle\hat{\mathbf{y}}\rangle_{i}$) by iteratively evaluating the function
$f(\cdot)$ on each row of $\langle\mathbf{X}\rangle_{i}$. As
$\langle\hat{\mathbf{y}}\rangle_{i}$ is an output of computations over secret
shares, it is simply a vector of random numbers from $P_{i}$’s viewpoint.
However, by definition, adding $\langle\hat{\mathbf{y}}\rangle_{0}$ to
$\langle\hat{\mathbf{y}}\rangle_{1}$ reveals the actual predicted values
$\hat{y}$. $P_{0}$ and $P_{1}$ then calculate their shares of the fitness
value $\langle z\rangle_{i}$ by applying the fitness function $F(\cdot)$ on
$\langle\mathbf{y}\rangle_{i}$ and $\langle\hat{\mathbf{y}}\rangle_{i}$, and
send $\langle z\rangle_{i}$ back to $P_{3}$ (depicted in Figure 6). Finally,
$P_{3}$ recombines the shares to obtain the true fitness value $z$. The
algorithmic representation of the secure fitness evaluation protocol is
displayed in Algorithm 3.

Participants: $C_{j}$ for $j\in\\{1,2,...,K\\}$, $P_{0}$, and $P_{1}$

Input: $C_{j}$ holds $\mathbf{X}_{j}\in\mathbb{Z}^{m\times n_{j}}_{2^{L}}$ for
$j\in\\{1,2,...,K\\}$, $C_{K}$ holds $\mathbf{y}\in\mathbb{Z}^{m\times
1}_{2^{L}}$

Output: For $i\in\\{0,1\\}$, $P_{i}$ gets their share of the training data
$\langle D\rangle_{i}$

1 Function  _SecretDataSharing(__)_ :

2 for  _$j\in\\{1,2,...,K\\}$ , $C_{j}$_ do

3 Generate a random matrix $\mathbf{R}\in\mathbb{Z}_{2^{L}}^{m\times n_{j}}$

4 Calculate $\langle\mathbf{X}_{j}\rangle_{0}=\mathbf{R}$ and
$\langle\mathbf{X}_{j}\rangle_{1}=\mathbf{X}_{j}-\mathbf{R}$

5 Transfer $\langle\mathbf{X}_{j}\rangle_{0}$ and
$\langle\mathbf{X}_{j}\rangle_{1}$ to $P_{0}$ and $P_{1}$ respectively

6 end for

7 $C_{K}$ do:

8 Generate a random vector $\mathbf{w}\in\mathbb{Z}_{2^{L}}^{m\times 1}$

9 Calculate $\langle\mathbf{y}\rangle_{0}=\mathbf{w}$ and
$\langle\mathbf{y}\rangle_{1}=\mathbf{y}-\mathbf{w}$

10 Transfer $\langle\mathbf{y}\rangle_{0}$ and $\langle\mathbf{y}\rangle_{1}$
to $P_{0}$ and $P_{1}$ respectively

11 end

12

13 for  _$i\in\\{0,1\\}$ , $P_{i}$_ do

14 Compile their share of the training dataset: $\langle
D\rangle_{i}=\\{\langle\mathbf{X}\rangle_{i},\langle\mathbf{y}\rangle_{i}\\}$,
with $\langle\mathbf{y}\rangle_{i}\in\mathbb{Z}^{m\times 1}_{2^{L}}$ and
$\langle\mathbf{X}\rangle_{i}=[\langle\mathbf{X}_{1}\rangle_{i}|\langle\mathbf{X}_{2}\rangle_{i}|...|\langle\mathbf{X}_{K}\rangle_{i}]\in\mathbb{Z}^{m\times
n}_{2^{L}}$

15 end for

16

17 End

Algorithm 2 Secret Data Sharing

Participants: $P_{0}$, $P_{1}$, $P_{2}$, and $P_{3}$

Input: $P_{i}$ holds $\langle D\rangle_{i}$ for $i\in\\{0,1\\}$, $P_{3}$ holds
the candidate expression $f(\cdot)$ and the fitness function $F(\cdot)$

Output: $P_{3}$ gets the fitness value $z$ of $f(\cdot)$

1 Function  _SecureFitnessEvaluation(__)_ :

2 $P_{3}$ do:

3 Forward the candidate expression $f(\cdot)$ and the fitness function
$F(\cdot)$ to $P_{0}$ and $P_{1}$

4 end

5

6 for  _$i\in\\{0,1\\}$ , $P_{i}$_ do

7 Compute its shares of predictions $\langle\hat{\mathbf{y}}\rangle_{i}$
locally by evaluating $f(\cdot)$ on each row of $\langle\mathbf{X}\rangle_{i}$

8 Compute its share of the fitness value $\langle z\rangle_{i}$ locally by
evaluating $F(\cdot)$ on $\langle\mathbf{y}\rangle_{i}$ and
$\langle\hat{\mathbf{y}}\rangle_{i}$

9 Send $\langle z\rangle_{i}$ to $P_{3}$

10 end for

11 *The assistance of $P_{2}$ is required whenever multiplication is involved.

12 $P_{3}$ do:

13 Combine the secret shares and get the real fitness value: $z=\langle
z\rangle_{0}+\langle z\rangle_{1}$

14 end

15

16 End

Algorithm 3 Secure Fitness Evaluation Figure 5. An illustration of the Secret
Data Sharing phase. Figure 6. An illustration of the Secure Fitness Evaluation
module.

###  3.3. Security Justification

In this section, we justify the security of PPSR. We consider the semi-honest
scenario, which covers a wide range of secure machine learning use cases.
Under this setting, each party will strictly comply with the predefined
protocol but might attempt to gain as much information as possible from their
perspective (Evans et al., 2018). In addition, we also assume that there is no
collusion between parties and clients.

In our proposed framework, throughout the entire process, the real datasets
stay securely in the client’s database. Even though the secret shares are
transferred to computing servers ($P_{0}$, $P_{1}$), they do not contain any
meaningful information about the original data but random values. Meanwhile,
$P_{2}$’s only task is to generate Beaver triples, and it receives nothing
from other parties. The security proofs of computation on secret shares under
the semi-honest setting can be found in (Knott et al., 2021). Concerning
$P_{3}$, although this party has access to the candidate expressions and their
associated fitness values during the model training, it is still challenging,
and in some cases not feasible, to retrieve the actual data, especially when
the data is extensive in size and dimension. The main reason behind this
challenge is that there could be numerous or even an infinite number of
datasets that can generate the same fitness value for a specific expression.

##  4\. Preliminary experiment

In this section, we conduct experiments on simulated data to evaluate the
capabilities of the proposed framework.

###  4.1. General Settings

We evaluated GPSR and PPSR on the Nguyen benchmark suite (Uy et al., 2011), a
standard collection of expressions utilized in symbolic regression. Due to the
need to simulate a vertical setting in which variables are divided among
different clients, we could only use benchmarks that involve multiple
variables. Table 1 provides details on the selected benchmarks. The input
variables are denoted by $x_{1}$ and $x_{2}$; each contains 20 random points
uniformly sampled between 0 and 1. The ground-truth expression is used to
compute the target output $y$ from the input variables. The training set and
test set are generated using different random seeds. While the training data
is utilized to compute the fitness for each candidate expression, the test
data is used at the end of the model training process to assess the best
optimal expression that has been discovered.

Benchmark | Expression
---|---
Nguyen-9 | $sin(x_{1})+sin(x_{2}^{2})$
Nguyen-10 | $2sin(x_{1})cos(x_{2})$
Nguyen-12 | $x_{1}^{4}-x_{1}^{3}+\frac{1}{2}x_{2}^{2}-x_{2}$
Friedman-2 | $10sin(\pi x_{1}x_{2})+20(x_{3}-0.5)^{2}+10x_{4}+5x_{5}$
Table 1. The selected benchmark suite.

The objective of the experiment is to compare the performance of PPSR with
that of the standard GPSR. To do that, we need to simulate a vertical scenario
where different clients possess different variables and then split data
accordingly. As our benchmark datasets only have two input variables, we
assume there are two clients, $C_{1}$ and $C_{2}$. While $C_{1}$ has $x_{1}$,
$C_{2}$ owns $x_{2}$ and $y$. For each benchmark, the generated dataset is
vertically divided into two hypothetical private datasets based on the
variable split. Only when training GPSR models these local datasets will be
re-merged to construct the centralized dataset. The same hyperparameter
settings are used for both methods and are described in Table 2.

Parameter | Value
---|---
Population size | 1000
Fitness function | MSE
Initialization method | Full
Selection type | Tournament
Tournament size | 5
Mutation probability | 0.25
Crossover probability | 0.95
Minimum subtree depth | 0
Maximum subtree depth | 2
Max depth | 15
Max length | 100
Non-terminals | $+,-,\times,sin,cos$
Terminals | $x_{1},x_{2},constants$
Table 2. Hyperparameters for the algorithms.

For each problem set, the experiment is repeated 100 times. We quantify the
accuracy using $MSE$ and $R^{2}$ measured on both the training and test sets.
In addition, the recovery rate achieved by each method will also be reported.
This rate provides a more faithful evaluation of an SR method’s ability to
uncover the data generation process compared to the accuracy metrics (La Cava
et al., 2021). We use the most stringent recovery criteria to compute the
recovery rate, i.e., exact symbolic equivalence. The equivalence of a model
and the ground-truth expression is determined using a computer algebra system
called SymPy (Meurer et al., 2017).

The implementation is written in Python and utilizes two libraries, CRYPTEN
(Knott et al., 2021), and DEAP (Fortin et al., 2012). While CRYPTEN supports
MPC operations, DEAP provides the basic structure for building GPSR.

###  4.2. Results

The $R^{2}$ and $MSE$ achieved by GPSR and PPSR are plotted in Figure 7 and
Figure 8, respectively. Within each of these figures, there are two subplots
showing the models’ performance on the training set and the test set.
Meanwhile Table 3 reports the recovery rate for each benchmark. Overall, the
results demonstrate that both algorithms performed effectively on the three
selected benchmarks, with particular success on the Nguyen-10.

Figure 7. $R^{2}$ scores attained by GPSR and PPSR on the training set (left)
and the test set (right). Figure 8. $MSE$ attained by GPSR and PPSR on the
training set (left) and the test set (right).

For the Nguyen-9, out of 100 runs, GPSR was able to discover the ground-truth
expression 34 times, while PPSR succeeded 31 times. The top 3 most frequently
found formulas for both algorithms are also very similar (see Table 4). The
Nguyen-10 problem is solved almost perfectly by both methods. For this
problem, PPSR’s recovery rate is 59%, while GPSR’s figure is even higher at
68%. For the Nguyen-12, although the algorithms could not find the exact data-
generating function, they could still produce highly accurate estimates for
the range in which the input features are generated.

Benchmark | GPSR | PPSR
---|---|---
Nguyen-9 | 34% | 31%
Nguyen-10 | 68% | 59%
Nguyen-12 | 0% | 0%
Friedman-2 | 0% | 0%
Table 3. Recovery rate comparison of GPSR and PPSR on the benchmark datasets. Benchmark | GPSR | PPSR
---|---|---
$sin(x_{1})+sin(x_{2}^{2})$ | 34 | 31
$sin(x_{1})+x_{2}^{2}$ | 7 | 3
$sin(x_{1})+x_{2}sin(x_{2})$ | 4 | 5
Table 4. Top 3 most frequently discovered expressions on the Nguyen-9
benchmark.

Even though the solutions that GPSR and PPSR yielded are not always the same,
their overall performance on the Nguyen benchmark suit is highly comparable.
The advantage of using PPSR over GPSR is that our proposed approach does not
require clients to expose their raw data to any entities, thus safeguarding
their privacy.

###  4.3. Discussions

As PPSR relies on MPC to compute fitness values, it confronts inherent
difficulties associated with this cryptographic technique. Even though MPC
protects the data during computation, eventually, the clients get to view the
fittest expression. Under some conditions, it might be possible for a client
to infer the data of others. Take the Nguyen-9 for example, if the discovered
expression is $y=x_{1}+sin(x_{2})$, $C_{2}$ can easily estimate $x_{1}$ since
it already knows $x_{2}$ and $y$, i.e., $x_{1}=y-sin(x_{2})$. A potential
mitigation for this problem is to combine MPC with Differential Privacy (DP)
(Pettai and Laud, 2015). As DP systematically injects noise into private data
before sharing, the best a malicious party can infer is the noisy values.
However, implementing DP is not trivial and might come at the cost of
performance.

Additionally, the current version of PPSR has to deal with numerical problems
which are frequently encountered in CRYPTEN-based machine-learning
implementations (Knott et al., 2021). This is due in part to the use of fixed-
point representation, which is more vulnerable to overflow or underflow than
floating-point representations. Additionally, rounding errors can accumulate
during computation and lead to inaccurate results. The debugging process for
these errors can be challenging as they may only occur in the multi-party
setting, in which no individual party has the ability to identify them.
Therefore, implementing some commonly used mathematical operations in SR, such
as $division$, $logarithm$, or $exponential$, can be difficult and requires
careful consideration.

##  5\. Conclusion and Future Work

In this paper, we propose a framework for training Symbolic Regression on
vertically distributed data in a privacy-preserving manner. In the proposed
framework, MPC is leveraged to evaluate the quality of candidate expressions
without requiring participating clients to expose their private data. The
preliminary experiments on simulated data indicate that our proposed method
could yield comparable performance to the centralized solution.

Although our focus in this work is the vertical setting, the proposed
framework can also handle the horizontal setting. It is because PPSR relies on
the 3PC scheme to conduct secure fitness computation, and 3PC has no
assumptions about how data is distributed. Besides, since there are no
constraints about the evolution operators, our method can be easily extensible
to other GPSR variations. For future work, we will explore these extensions.
Furthermore, we also plan to investigate the combination of MPC and DP to
strengthen the safety of the framework and to examine potential solutions for
the numerical issues to increase precision. Finally, we will conduct
experiments on more complex benchmarks that better reflect reality to obtain a
more comprehensive evaluation of the capability of the proposed method.

## References

  * (1)
  * Affenzeller et al. (2014) Michael Affenzeller, Stephan M Winkler, Gabriel Kronberger, Michael Kommenda, Bogdan Burlacu, and Stefan Wagner. 2014.  Gaining deeper insights in symbolic regression.  _Genetic Programming Theory and Practice XI_ (2014), 175–190.
  * Beaver (1992) Donald Beaver. 1992\.  Efficient multiparty protocols using circuit randomization. In _Advances in Cryptology—CRYPTO’91: Proceedings 11_. Springer, 420–432.
  * Demmler et al. (2015) Daniel Demmler, Thomas Schneider, and Michael Zohner. 2015\.  ABY-A framework for efficient mixed-protocol secure two-party computation.. In _NDSS_.
  * Dong et al. (2022) Junlan Dong, Jinghui Zhong, Wei-Neng Chen, and Jun Zhang. 2022\.  An Efficient Federated Genetic Programming Framework for Symbolic Regression.  _IEEE Transactions on Emerging Topics in Computational Intelligence_ (2022), 1–14.  https://doi.org/10.1109/TETCI.2022.3201299
  * Dwork et al. (2014) Cynthia Dwork, Aaron Roth, et al. 2014\.  The algorithmic foundations of differential privacy.  _Foundations and Trends® in Theoretical Computer Science_ 9, 3–4 (2014), 211–407.
  * Evans et al. (2018) David Evans, Vladimir Kolesnikov, Mike Rosulek, et al. 2018\.  A pragmatic introduction to secure multi-party computation.  _Foundations and Trends® in Privacy and Security_ 2, 2-3 (2018), 70–246.
  * Fortin et al. (2012) Félix-Antoine Fortin, François-Michel De Rainville, Marc-André Gardner, Marc Parizeau, and Christian Gagné. 2012.  DEAP: Evolutionary Algorithms Made Easy.  _Journal of Machine Learning Research_ 13 (jul 2012), 2171–2175.
  * Gascón et al. (2016) Adrià Gascón, Phillipp Schoppmann, Borja Balle, Mariana Raykova, Jack Doerner, Samee Zahur, and David Evans. 2016\.  Secure linear regression on vertically partitioned datasets.  _IACR Cryptol. ePrint Arch._ 2016 (2016), 892.
  * Gentry (2009) Craig Gentry. 2009\.  _A fully homomorphic encryption scheme_.  Stanford university.
  * Knott et al. (2021) Brian Knott, Shobha Venkataraman, Awni Hannun, Shubho Sengupta, Mark Ibrahim, and Laurens van der Maaten. 2021.  Crypten: Secure multi-party computation meets machine learning.  _Advances in Neural Information Processing Systems_ 34 (2021), 4961–4973.
  * Konečnỳ et al. (2016) Jakub Konečnỳ, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. 2016\.  Federated learning: Strategies for improving communication efficiency.  _arXiv preprint arXiv:1610.05492_ (2016).
  * Koza (1994) John R Koza. 1994\.  Genetic programming as a means for programming computers by natural selection.  _Statistics and computing_ 4 (1994), 87–112.
  * La Cava et al. (2021) William La Cava, Patryk Orzechowski, Bogdan Burlacu, Fabrício Olivetti de França, Marco Virgolin, Ying Jin, Michael Kommenda, and Jason H Moore. 2021\.  Contemporary symbolic regression methods and their relative performance.  _arXiv preprint arXiv:2107.14351_ (2021).
  * Liu et al. (2020) Yang Liu, Yingting Liu, Zhijie Liu, Yuxuan Liang, Chuishi Meng, Junbo Zhang, and Yu Zheng. 2020.  Federated forest.  _IEEE Transactions on Big Data_ 8, 3 (2020), 843–854.
  * Meurer et al. (2017) Aaron Meurer, Christopher P Smith, Mateusz Paprocki, Ondřej Čertík, Sergey B Kirpichev, Matthew Rocklin, AMiT Kumar, Sergiu Ivanov, Jason K Moore, Sartaj Singh, et al. 2017\.  SymPy: symbolic computing in Python.  _PeerJ Computer Science_ 3 (2017), e103.
  * Mohassel and Zhang (2017) Payman Mohassel and Yupeng Zhang. 2017.  Secureml: A system for scalable privacy-preserving machine learning. In _2017 IEEE symposium on security and privacy (SP)_. IEEE, 19–38.
  * Nguyen Duy et al. (2022) Du Nguyen Duy, David Gabauer, and Ramin Nikzad-Langerodi. 2022\.  Towards federated multivariate statistical process control (FedMSPC).  _arXiv preprint arXiv:2211.01645_ (2022).
  * Pettai and Laud (2015) Martin Pettai and Peeter Laud. 2015.  Combining differential privacy and secure multiparty computation. In _Proceedings of the 31st Annual Computer Security Applications Conference_. 421–430.
  * Uy et al. (2011) Nguyen Quang Uy, Nguyen Xuan Hoai, Michael O’Neill, Robert I McKay, and Edgar Galván-López. 2011.  Semantically-based crossover in genetic programming: application to real-valued symbolic regression.  _Genetic Programming and Evolvable Machines_ 12 (2011), 91–119.
  * Wagh et al. (2019) Sameer Wagh, Divya Gupta, and Nishanth Chandran. 2019.  SecureNN: 3-Party Secure Computation for Neural Network Training.  _Proc. Priv. Enhancing Technol._ 2019, 3 (2019), 26–49.
  * Yang et al. (2019) Qiang Yang, Yang Liu, Tianjian Chen, and Yongxin Tong. 2019\.  Federated machine learning: Concept and applications.  _ACM Transactions on Intelligent Systems and Technology (TIST)_ 10, 2 (2019), 1–19.