${\mathbb{E}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}}}[|(h_{-1}-f_{-1})({\mathcal{P}}(x),l_{p})-(h_{-1}-f_{-1})(x+{\mathcal{P}}(x),l_{p})|]\leq\tau$,
where $(h_{-1}-f_{-1})(x,y)=h_{-1}(x,y)-f_{-1}(x,y)$.

Since $(h_{-1}-f_{-1})(x,l_{p})=f_{l_{p}}(x)-h_{l_{p}}(x)$ for the
corresponding $h\in H$ and $f\in F$, by condition (3) in Lemma D.3, we get the
result.

Since the three conditions in Theorem D.2 stand for $H_{-1}$ and $F_{-1}$, the
lemma is proved. ∎

Second, we give three lemmas.

######  Lemma D.4.

For any $h\in{\mathcal{H}}_{W,D}$, we have
${\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}}[{\mathbf{1}}(\widehat{h}(x+{\mathcal{P}}(x))\neq
l_{p})]\leq
2{\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}}[1-h_{l_{p}}(x+{\mathcal{P}}(x))]$.

###### Proof.

When $\widehat{h}(x+{\mathcal{P}}(x))\neq l_{p}$, we have
$h_{l_{p}}(x+{\mathcal{P}}(x))<0.5$, which implies that
$0.5*{\mathbf{1}}(\widehat{h}(x+{\mathcal{P}}(x))\neq l_{p})\leq
1-h_{l_{p}}(x+{\mathcal{P}}(x))$. Then,
${\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}}[0.5*{\mathbf{1}}(\widehat{h}(x+{\mathcal{P}}(x))\neq
l_{p})]\leq{\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}}[1-h_{l_{p}}(x+{\mathcal{P}}(x))]$,
this is what we want. ∎

######  Lemma D.5 (Mohri et al. (2018)).

For any hypothesis space $F=\\{f:{\mathbb{R}}^{n}\to[0,1]\\}$ and distribution
${\mathcal{D}}$, $N>0$. Let $F_{1}=\\{1-f\|f\in F\\}$. Then
${\hbox{\rm{Rad}}}_{N}^{\mathcal{D}}(F_{-1})=Rad_{N}^{\mathcal{D}}(F)$.

######  Lemma D.6.

For any $x\in(0,1]$, we have $1-x\leq-\ln x$.

###### Proof.

Let $f(x)=1-x+\ln x$, then $f^{\prime}(x)=1/x-1\geq 0$ when $x\in[0,1]$.
Because $f(1)=0$, we have $f(x)\leq 0$ for all $x\in(0,1]$ ∎

Finally, we use Lemmas D.3, D.4, D.5, and D.6 to prove Theorem D.1.

###### Proof.

Firstly, it is easy to see that, conditions (1), (2), (3) in Lemma D.3 are the
same as (c1), (c2), (c3) in Theorem D.1. So by Lemma D.3, we have

${\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}}[1-h_{l_{p}}(x+{\mathcal{P}}(x))]\leq\lambda(2{{\mathbb{E}}_{(x,y)\in{\mathcal{D}}_{P}}[1-h_{y}(x)]/(\alpha\eta)}+2{\hbox{\rm{Rad}}}^{{\mathcal{D}}_{S}^{l_{p}}}_{N\alpha\eta/2}(H_{-1})+\sqrt{\frac{\ln(2/\delta)}{N\alpha\eta}}+\tau/\eta+\epsilon)\\\
+\tau+(\lambda-1)\eta.$

Then, by Lemma D.4, we further have

$\begin{array}[]{l}{\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}}[{\mathbf{1}}(h_{l_{p}}(x+{\mathcal{P}}(x))\neq
l_{p})]\leq\\\
2\lambda(2{{\mathbb{E}}_{(x,y)\in{\mathcal{D}}_{P}}[1-h_{y}(x)]/(\alpha\eta)}+2{\hbox{\rm{Rad}}}^{{\mathcal{D}}_{S}^{l_{p}}}_{N\alpha\eta/2}(H_{-1})+\sqrt{\frac{\ln(2/\delta)}{N\alpha\eta}}+\tau/\eta+\epsilon)+2\tau+2(\lambda-1)\eta.\end{array}$

We have
$H_{W,D,1}=\\{{\mathcal{F}}_{y}(x)\|{\mathcal{F}}\in{\mathcal{H}}_{W,D}\\}$
and $H\subset{\mathcal{H}}_{W,D}$. Then, by Lemma D.5 and considering that
under distribution ${\mathcal{D}}_{S}^{l_{p}}$, all samples have label
$l_{p}$, so we have
${\hbox{\rm{Rad}}}^{{\mathcal{D}}_{S}^{l_{p}}}_{N\alpha\eta/2}(H_{-1})\leq{\hbox{\rm{Rad}}}^{{\mathcal{D}}_{S}^{l_{p}}}_{N\alpha\eta/2}(H_{W,D,1})$.

Finally, using Lemma D.6 and the fact:
${\hbox{\rm{Rad}}}^{D}_{M}(H)\leq\frac{N}{M}{\hbox{\rm{Rad}}}^{D}_{N}(H)$ for
any $M\leq N$, distribution ${\mathcal{D}}$, and hypothesis space $H$, we
obtain

$\begin{array}[]{l}{\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}}[{\mathbf{1}}(h_{l_{p}}(x+{\mathcal{P}}(x))\neq
l_{p})]\leq\\\
2\lambda(\frac{2{{\mathbb{E}}_{(x,y)\in{\mathcal{D}}_{P}}[L_{CE}(f(x),y)]}}{\eta\alpha}+4{\hbox{\rm{Rad}}}^{{\mathcal{D}}_{S}^{l_{p}}}_{N}(H_{W,D,1})/(\alpha\eta)+\sqrt{\frac{\ln(2/\delta)}{N\alpha\eta}}+\tau/\eta+\epsilon)+2\tau+2(\lambda-1)\eta.\end{array}$

The theorem is proved. ∎

###  D.3 Estimate the Rademacher Complexity

In this section, we estimate
${\hbox{\rm{Rad}}}^{{\mathcal{D}}_{S}^{l_{p}}}_{N\alpha\eta/2}(H_{W,D,1})$.
Since all samples have label $l_{p}$ in distribution
${\mathcal{D}}_{S}^{l_{p}}$, without loss of generality, we let $l_{p}=1$. In
this section, we only need to consider the Radmacher complexity of the
following hypothesis space
${\mathcal{H}}_{W,D,0}=\\{{\mathcal{F}}_{1}(x):{\mathcal{F}}(x)\in{\mathcal{H}}_{W,D}\\}$.

We show that, if we bound the norm of the network parameters in
${\mathcal{H}}_{W,D,0}$, then we can calculate
${\hbox{\rm{Rad}}}_{N}^{\mathcal{D}}({\mathcal{H}}_{W,D,0})$ for any
distribution ${\mathcal{D}}$. Please note that the condition of bounded
network parameters is reasonable.

Some definitions and a lemma are required.

######  Definition D.7.

Let $F=\\{f:{\mathbb{R}}^{n}\to[0,1]\\}$ be a hypothesis space, and
$\\{x_{i}\\}_{i=1}^{N}$ be $N$ samples in ${\mathbb{R}}^{n}$. Then the
empirical Rademacher Complexity of ${\mathcal{F}}$ under
$\\{x_{i}\\}_{i=1}^{N}$ is defined as

${\hbox{\rm{Rad}}}^{\\{x_{i}\\}_{i=1}^{N}}(F)={\mathbb{E}}_{\sigma}[\sup_{f\in
F}\frac{1}{N}\sum_{i=1}^{N}\sigma_{i}f(x_{i})],$

where $\sigma=(\sigma_{i})_{i=1}^{N}$ is a set of random variables such that
${\mathbb{P}}(\sigma_{i}=1)={\mathbb{P}}(\sigma_{i}=-1)=0.5$.

It is easy to see that
${\hbox{\rm{Rad}}}^{{\mathcal{D}}}_{N}({\mathcal{F}})\leq\max_{\\{x_{i}\\}_{i=1}^{N}\sim{\mathcal{D}}}{\hbox{\rm{Rad}}}^{\\{x_{i}\\}_{i=1}^{N}}({\mathcal{F}})$,
so we can try to calculate the empirical Rademacher Complexity to bound
${\hbox{\rm{Rad}}}^{{\mathcal{D}}}_{N}({\mathcal{F}})$.

######  Definition D.8 (Covering Number,(Wainwright, 2019)).

Let $(T,L)$ be a metric space, $T$ be a space, and $L$ be the distance in $T$.
We say that a $K\subset T$ is an $\epsilon$ cover of $T$, if for any $x\in T$,
there is a $y\in K$, such that $L(x,y)\leq\epsilon$. The minimum $|K|$ is
defined as $C(K,L,\epsilon)$, that is $C(K,L,\epsilon)=\min|K|$ where
$K\subset T$ is an $\epsilon$ cover of $T$.

######  Lemma D.9 ((Wainwright, 2019)).

Let $F=\\{f:{\mathbb{R}}^{n}\to[0,1]\\}$ be a hypothesis space, and
$\\{x_{i}\\}_{i=1}^{N}$ be $N$ samples in ${\mathbb{R}}^{n}$. Define
$L(f,g)=\sqrt{1/N\sum_{i=1}^{N}(f(x_{i})-g(x_{i}))^{2}}$ for any $f,g\in F$.
Then

${\hbox{\rm{Rad}}}^{\\{x_{i}\\}_{i=1}^{N}}(F)\leq
O(\int_{0}^{1}\sqrt{\frac{\ln C(F,L,t)}{N}}dt).$

When network parameters are bounded, Lemma D.9 is often used to calculate the
Rademacher complexity. A classical result is given below.

######  Lemma D.10.

Let $T$ be a ball with radius $r$ in ${\mathbb{R}}^{p}$. Then for any $t$, we
have $C(T,L_{o},t)\leq(\frac{3r}{t})^{p}$, where $L_{o}$ is the Euclid
distance.

Now, we will try to calculate the covering number of ${\mathcal{H}}_{W,D,0}$.
First, we give a definition of the bound of the network parameters and the
relationship between the bound of the network parameters and the network
output.

######  Definition D.11.

Let ${\mathcal{F}}_{i}(i=1,2)$ be two networks, the $j$-th transition matrix
and bias vector are $W^{i}_{j}$ and $b^{i}_{j}$. Then let
$B({\mathcal{F}}_{i})=\sum_{j=1}^{D_{i}}(||W_{j}^{i}||_{2}+||b_{j}^{i}||_{2})$,
where $D_{i}$ is the depth of ${\mathcal{F}}_{i}$. If $D_{1}=D_{2}=D$ and the
widths of ${\mathcal{F}}_{i}$ are the same, then we can define
$B({\mathcal{F}}_{1}-{\mathcal{F}}_{2})=\sum_{j=1}^{D}(||W_{j}^{1}-W_{j}^{2}||_{2}+||b_{j}^{1}-b_{j}^{2}||_{2})$.

Then, we have the following existing result.

######  Lemma D.12 (Tsai et al. (2021)).

For networks ${\mathcal{F}}_{1}$ and ${\mathcal{F}}_{2}$ with depth $D$, with
Relu activation function, and output layers do not have activation function.
If $B({\mathcal{F}}_{1})\leq C$, $B({\mathcal{F}}_{2})\leq C$, and
$B({\mathcal{F}}_{1}-{\mathcal{F}}_{2})\leq\epsilon$, then
$||{\mathcal{F}}_{1}(x)-{\mathcal{F}}_{2}(x)||_{2}\leq D\epsilon
C^{D}||x||_{2}$ for any $x$.

It is easy to show that the Softamx function is a Liptschitz function:

######  Lemma D.13.

If $a,b\in{\mathbb{R}}^{m}$, then
$|{\hbox{\rm{Softmax}}}(a)_{1}-{\hbox{\rm{Softmax}}}(b)_{1}|\leq\sqrt{m}||a-b||_{2}$,
where ${\hbox{\rm{Softmax}}}(a)_{1}$ is the first weight of
${\hbox{\rm{Softmax}}}(a)$.

So using Lemmas D.12 and D.13, we have

######  Lemma D.14.

For networks ${\mathcal{F}}_{1},{\mathcal{F}}_{2}\in{\mathcal{H}}_{W,D}$ and
${\mathcal{F}}_{i}\in{\mathbb{R}}^{n}\to{\mathbb{R}}^{m}$. If
$B({\mathcal{F}}_{1})\leq C$, $B({\mathcal{F}}_{2})\leq C$ and
$B({\mathcal{F}}_{1}-{\mathcal{F}}_{2})\leq\epsilon$, then
$||{\mathcal{F}}_{1}(x)-{\mathcal{F}}_{2}(x)||_{2}\leq\sqrt{mn}D\epsilon
C^{D}$ for any $x\in[0,1]^{n}$.

Now, we calculate the covering number of ${\mathcal{H}}_{W,D,0}$.

######  Lemma D.15.

$L(f,g)$ is defined in Lemma D.9. Let
${\mathcal{H}}^{A}_{W,D,0}=\\{{\mathcal{F}}:{\mathcal{F}}\in{\mathcal{H}}_{W,D,0},B({\mathcal{F}})\leq
A\\}$. Then for any $t>0$, we have
$C({\mathcal{H}}^{A}_{W,D,0},L,t)\leq(3A^{D+1}D\sqrt{mn}/t)^{O(W^{2}D)}$.

###### Proof.

By Lemma D.14, when
${\mathcal{F}}_{1},{\mathcal{F}}_{2}\in{\mathcal{H}}^{A}_{W,D,0}$, if
$B({\mathcal{F}}_{1}-{\mathcal{F}}_{2})\leq\frac{t}{DA^{D}\sqrt{mn}}$, then we
have $||{\mathcal{F}}_{1}(x)-{\mathcal{F}}_{2}(x)||_{2}\leq t$, which implies
that $L({\mathcal{F}}_{1},{\mathcal{F}}_{2})\leq t$. So we just need to
minimize the number of the $\frac{t}{DA^{D}\sqrt{mn}}$ cover of the parameter
space. Using Lemma D.10, we get the result. ∎

Finally, using Lemmas D.9 and D.15, we can calculate the Rademacher
Complexity.

######  Lemma D.16.

Let
${\mathcal{H}}^{A}_{W,D,0}=\\{{\mathcal{F}}:{\mathcal{F}}\in{\mathcal{H}}_{W,D,0},B({\mathcal{F}})\leq
A\\}$ and $ADmn\geq e$. Then
${\hbox{\rm{Rad}}}_{N}^{\mathcal{D}}({\mathcal{H}}^{A}_{W,D,0})\leq{\frac{O(WD\ln(ADmn))}{\sqrt{N}}}$
for any distribution ${\mathcal{D}}$, which implies that
${\hbox{\rm{Rad}}}_{N}^{\mathcal{D}}({\mathcal{H}}^{A}_{W,D,0})$ approaches to
0 when $N$ is big enough.

###### Proof.

We just need to prove that, for any $N$ points $\\{x_{i}\\}_{i=1}^{N}$ in
$[0,1]^{N}$, we have
${\hbox{\rm{Rad}}}^{\\{x_{i}\\}_{i=1}^{N}}({\mathcal{H}}^{A}_{W,D,0})\leq{\frac{O(WD\ln(ADmn))}{\sqrt{N}}}$.

Using Lemmas D.9 and D.15, we have
${\hbox{\rm{Rad}}}^{\\{x_{i}\\}_{i=1}^{N}}({\mathcal{H}}^{A}_{W,D,0})\leq
O(\int_{0}^{1}\sqrt{\frac{O(W^{2}D^{2}\ln(ADmn/t))}{N}}dt)\leq
O(\int_{0}^{1}\frac{O(WD\ln(ADmn/t))}{\sqrt{N}}dt)=\frac{O(WD\ln(ADmn))}{\sqrt{N}}$.
Here, we use $\sqrt{\ln(q/t)}\leq lnq/t$ for all $q\geq e$ and $t\in(0,1)$. ∎

##  Appendix E Proof of Proposition 4.10

###  E.1 Strict

We first give a precise version of the proposition and definition in Section
4.3:

######  Definition E.1 (Binary Shortcut).

${\mathcal{P}}(x)$ is called a binary shortcut of the binary linear
inseparable classification dataset
${\mathcal{D}}=\\{(x_{i},1)\\}_{i=1}^{N_{1}}\cup\\{(\widehat{x}_{i},0)\\}_{i=1}^{N_{0}}$,
if
${\mathcal{D}}_{1}=\\{(x_{i},1)\\}_{i=1}^{N_{1}}\cup\\{(\hat{x}_{i}+{\mathcal{P}}(\widehat{x}_{i}),0)\\}_{i=1}^{N_{0}}$
is linear separable. Moreover, if there exists a linear function $h$ with a
unit normal vector and $0<\eta_{1}<0.5$ such that $h(x)\geq 1-\eta_{1}$ for
any $(x,0)\in{\mathcal{D}}_{1}$ and $h(x)\leq\eta_{1}$ for any
$(x,1)\in{\mathcal{D}}_{1}$. Then we say that ${\mathcal{P}}(x)$ is a binary
shortcut of ${\mathcal{D}}$ with bound $\eta_{1}$.

The strict version of the definition for the Simple Feature Recognition Space:
It is generally believed that networks learn simple features, and based on
this characteristic, adding shortcut to dataset affects network training, so
we use the following definition to describe this property:

######  Definition E.2 (Simple Features Recognition Space).

We say that ${\mathcal{H}}$ is a simple feature recognition space with a
constant $c$, if for any binary linear inseparable classification dataset
${\mathcal{D}}$ and a binary shortcut ${\mathcal{P}}(x)$ of ${\mathcal{D}}$
with bound $\eta_{1}$, ${\mathcal{H}}$ satisfies the following properties: Let
$k=\max_{(x,0),(z,0)\in D}\\{||{\mathcal{P}}(x)-{\mathcal{P}}(z)||_{2}\\}$.
Then for any $h\in{\mathcal{H}}$ that satisfies $h(x+{\mathcal{P}}(x))\geq
1-\eta_{1},\forall(x,0)\in{\mathcal{D}}$ and
$h(x)\leq\eta_{1},\forall(x,1)\in{\mathcal{D}}$, it holds
$h(x_{1}+{\mathcal{P}}(x_{0}))-h(x_{1})\geq c(1-2\eta_{1}-k)$ and
$h({\mathcal{P}}(x_{0}))\geq c(1-2\eta_{1}-k)$ for any
$(x_{0},0)\in{\mathcal{D}}$ and $(x_{1},y_{1})\in{\mathcal{D}}$.

As mentioned above, indiscriminate poison can be considered as a shortcut, and
we have two important conclusions that have been proved in the study of
indiscriminate poison (Zhu et al., 2023b): (1) The network trained on dataset
with indiscriminate poison will classify shortcut and (2) Adding shortcut to
samples will affect the output of network. The above definition mainly uses
mathematical methods to describe these two conclusions: we express that
“network will classify shortcut” by giving a lower bound to
$h({\mathcal{P}}(x_{0}))$; we express “shortcut effects the classification
results” by giving lower bound to $h(x_{1}+{\mathcal{P}}(x_{0}))-h(x_{1})$.
Moreover, we have considered the impact of differences in ${\mathcal{P}}(x)$
for different $x$ (i.e., $k$ in definition) on the output: the larger the
difference, the smaller the impact. Thus, our definition is valid for some
spaces, as shown below.

######  Proposition E.3.

Let $L$ be the set of linear functions with a normal unit vector and without
bias. Then $L$ is a simple feature recognition space with constant $1$.
Furthermore, if $f:{\mathbb{R}}\to{\mathbb{R}}$ is an increasing
differentiable function with derivatives in $[a,1]$ and $f(0)=0$, then the
hypothesis space ${\mathcal{H}}=\\{f(l(x))|l\in L\\}$ is a simple feature
recognition space with constant $a$.

The strict version of Proposition 4.10: Using the above definitions, we can
show how condition (c3) in Theorem 4.5 stands for a small $\tau$, the strict
version of Proposition 4.10 is given below.

######  Proposition E.4.

Use notation introduced in Theorem 4.1. For any distribution ${\mathcal{D}}$,
let ${\mathcal{D}}({\mathcal{P}})$ be the distribution of ${\mathcal{P}}(x)$
when $x\sim{\mathcal{D}}$, and ${\mathcal{D}}({\mathcal{P}}+x)$ be the
distribution of $x+{\mathcal{P}}(x)$ when $x\sim{\mathcal{D}}$.
${\mathcal{H}}_{W,D,1}$ is defined in Section 3. Define
${\hbox{\rm{Rad}}}2({\mathcal{H}}_{W,D})$ as:

$\begin{array}[]{ll}&{\hbox{\rm{Rad}}}2({\mathcal{H}}_{W,D})=\\\
&O({\hbox{\rm{Rad}}}_{N(1-\eta)}^{{\mathcal{D}}_{S}^{\neq
l_{p}}({\mathcal{P}})}({\mathcal{H}}_{W,D,1})+{\hbox{\rm{Rad}}}_{N(1-\eta)}^{{\mathcal{D}}_{S}^{\neq
l_{p}}(x+{\mathcal{P}})}({\mathcal{H}}_{W,D,1})+{\hbox{\rm{Rad}}}_{N\eta\alpha}^{D^{l_{p}}_{\mathcal{S}}({\mathcal{P}})}({\mathcal{H}}_{W,D,1})+{\hbox{\rm{Rad}}}_{N\eta\alpha}^{D^{l_{p}}_{\mathcal{S}}(x+{\mathcal{P}})}({\mathcal{H}}_{W,D,1}))\end{array}$
(17)

Let
$D^{\prime}_{P}=\\{(x,0)|(x,y)\in{\mathcal{D}}_{{{\rm{tr}}}}\setminus{\mathcal{D}}_{clean}\\}\cup\\{(x,1)|(x,y)\in{\mathcal{D}}_{clean}\\}$.
Assume that with probability $1-\delta_{1}$, $D^{\prime}_{P}$ is linear
inseparable. Let the hypothesis spaces $H,F\subset{\mathcal{H}}_{W,D}$ satisfy
that $h_{y}(x)$ and $f_{y}(x)$ have Lipschitz constant $L$ for any $h\in H$,
$f\in F$ and any $x$, $y$. Assume that trigger ${\mathcal{P}}(x)$ satisfies
the following three conditions for some $\epsilon,k>0$:
(t1) For any $f\in F$, we have
$f_{y}(x+{\mathcal{P}}(x))<\epsilon,\forall(x,y)\sim{\mathcal{D}}_{\mathcal{S}}$;
(t2) $||{\mathcal{P}}(x_{1})-{\mathcal{P}}(x_{2})||_{2}\leq k$ for all
$x_{1},x_{2}$;
(t3) ${\mathcal{P}}(x)$ is the shortcut of the dataset
${\mathcal{D}}^{\prime}_{P}$ with bound $2\epsilon$.
When the hypothesis space
$H-F=\\{h_{l_{p}}(x)-f_{l_{p}}(x)\in{\mathbb{R}}^{m}\to{\mathbb{R}}|f\in
F,h\in H\\}$ is a simple feature recognition space with constant $c$ where $c$
satisfies $1-2\epsilon\geq c(1-4\epsilon)+k(c+4L)\geq 2\epsilon$. Then with
probability
$1-\delta_{1}-\delta-\frac{4(1-\eta)}{4(1-\eta)+N\eta}-\frac{4\eta}{4\eta+N(1-\eta)}$,
for any $h\in\\{h\in
H|h_{y}(x)>1-\epsilon,\forall(x,y)\in{\mathcal{D}}_{P}\\}$ and any
$f\in\\{f\in
F|f_{y}(x)>1-\epsilon,\forall(x,y)\in{\mathcal{D}}_{{{\rm{tr}}}}\\}$, we have

$\begin{array}[]{ll}&{\mathbb{E}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}}}[|(f-h)_{l_{p}}({\mathcal{P}}(x))-(f-h)_{l_{p}}(x+{\mathcal{P}}(x))|]\\\
\leq&2(1-c(1-4\epsilon)+k(c+4L))+2\epsilon)+{\hbox{\rm{Rad}}}2({\mathcal{H}}_{W,D})+16\sqrt{\frac{\ln(1/\delta)}{N\alpha}}.\end{array}$
(18)

It is easy to see that, when $c$ close to 1 and $k$ is small, such value is
close to $\widetilde{O}(\epsilon)$.

######  Remark E.5.

Notice that (t1) is similar to (c1) in Theorem 4.5, which means the trigger is
adversarial; (t2) is similar to (c2) in Theorem 4.5, which means trigger
should be similar for different samples. And when $k$ tends to 0, $c$ tends to
1, and $N$ is big enough, it holds that
${\mathbb{E}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}}}[|(f-h)_{l_{p}}({\mathcal{P}}(x))-(f-h)_{l_{p}}(x+{\mathcal{P}}(x))|]$
tends to $O(\epsilon)$. Generally, we can consider that the hypothesis space
$F$ only contains the network that performs well on distribution
${\mathcal{D}}_{\mathcal{S}}$. Then, based on the transferability of
adversarial examples, condition (t1) can be established.

###  E.2 Prove Proposition E.4

We first prove the following more general proposition, where the hypothesis
spaces are replaced with more general hypothesis spaces, which will imply
Proposition E.4.

######  Proposition E.6.

Use notation introduced in Theorem A.2. Let
$D^{\prime}_{P}=\\{(x,0)|(x,y)\in{\mathcal{D}}_{{{\rm{tr}}}}\setminus{\mathcal{D}}_{clean}\\}\cup\\{(x,1)|(x,y)\in{\mathcal{D}}_{clean}\\}$.
Assume that with probability $1-\delta_{1}$, $D^{\prime}_{P}$ is linear
inseparable. Let the hypothesis spaces
$H=\\{h(x,y):{\mathbb{R}}^{n}\times[m]\to[0,1]\\}$ and
$F=\\{f(x,y):{\mathbb{R}}^{n}\times[m]\to[0,1]\\}$ satisfy
$h(x,y_{1})+h(x,y_{2})\geq 1$, $h(x,y_{1})+h(x,y_{2})\geq 1$, $h(x,y_{1})$ and
$f(x,y_{1})$ have Lipschitz constant $L$ about $x$ for any $h\in H$, $f\in F$,
$x\in{\mathbb{R}}^{n}$ and $y_{1}\neq y_{2}$. Assume that trigger
${\mathcal{P}}(x)$ satisfies the following three conditions for some
$\epsilon,k>0$:
(t1) For any $f\in F$, we have
$f(x+{\mathcal{P}}(x),y)>1-\epsilon,\forall(x,y)\sim{\mathcal{D}}_{\mathcal{S}}$;
(t2)$||{\mathcal{P}}(x_{1})-{\mathcal{P}}(x_{2})||_{2}\leq k$ for all
$x_{1},x_{2}\in{\mathbb{R}}^{n}$;
(t3) ${\mathcal{P}}(x)$ is the shortcut of the dataset
${\mathcal{D}}^{\prime}_{P}$ with bound $2\epsilon$.
When the hypothesis space
$F-H=\\{g_{f,h}(x)=f(x,l_{p})-h(x,l_{p})\in{\mathbb{R}}^{m}\to{\mathbb{R}}|f\in
F,h\in H\\}$ is a simple feature recognition space with constant $c$ where $c$
satisfies $1-2\epsilon\geq c(1-4\epsilon)-(c+4L)k\geq 2\epsilon$. Then with
probability
$1-\delta_{1}-\delta-\frac{4(1-\eta)}{4(1-\eta)+N\eta}-\frac{4\eta}{4\eta+N(1-\eta)}$,
for any $h\in\\{h\in H|h(x,y)<\epsilon,\forall(x,y)\in{\mathcal{D}}_{P}\\}$
and any $f\in\\{f\in
F|f(x,y)<\epsilon,\forall(x,y)\in{\mathcal{D}}_{{{\rm{tr}}}}\\}$, we have

$\begin{array}[]{ll}&{\mathbb{E}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}}}[|(f-h)({\mathcal{P}}(x),l_{p})-(f-h)(x+{\mathcal{P}}(x),l_{p})|]\\\
\leq&2(1-c(1-4\epsilon)+(c+4L)k+2\epsilon)+{\hbox{\rm{Rad}}}(H,F)+16\sqrt{\frac{\ln(1/\delta)}{N\alpha}}.\end{array}$
(19)

Here ${\hbox{\rm{Rad}}}(H,F)$ is a value depending on the Rademacher
complexity of $H$ and $F$, and the specific value of it is explained in the
following proof.

###### Proof.

Let ${\mathcal{D}}({\mathcal{P}})$ be the distribution of ${\mathcal{P}}(x)$
where $x\sim{\mathcal{D}}$, and ${\mathcal{D}}({\mathcal{P}}+x)$ be the
distribution of $x+{\mathcal{P}}(x)$ where $x\sim{\mathcal{D}}$. We define
$g_{f,h}(x)=f(x,l_{p})-h(x,l_{p})$.

Next, under “${\mathcal{D}}^{\prime}_{P}$ is linear inseparable”, we will
prove the inequality (19) with probability
$1-\delta-\frac{4(1-\eta)}{4(1-\eta)+N\eta}-\frac{4\eta}{4\eta+N(1-\eta)}$,
which will directly lead to the conclusion of the proposition.

To prove this, we just used the following three results:

Result one: If $h(x,y)<\epsilon$ for any $x\in{\mathcal{D}}_{P}$ and
$f(x,y)<\epsilon$ for any $x\in{\mathcal{D}}_{{{\rm{tr}}}}$, then we have
$|g_{f,h}({\mathcal{P}}(x))-g_{f,h}({\mathcal{P}}(x)+x)|\leq
1-c(1-4{\mathbf{\varepsilon}})+(c+4L)k$ for any
$(x,y)\in{\mathcal{D}}_{{{\rm{tr}}}}\setminus{\mathcal{D}}_{clean}$ and
$|g_{f,h}({\mathcal{P}}(x))-g_{f,h}({\mathcal{P}}(x)+x)|\leq
1+2\epsilon-c(1-4{\mathbf{\varepsilon}})+(c+4L)k$ for any
$(x,y)\in{\mathcal{D}}_{clean}$.

It is easy to see that when $h(x,y)<\epsilon$ for any $x\in{\mathcal{D}}_{P}$
and $f(x,y)<\epsilon$ for any $x\in{\mathcal{D}}_{{{\rm{tr}}}}$, we have
$|f(x,l_{p})-h(x,l_{p})|\leq 2\epsilon,\forall(x,y)\in{\mathcal{D}}_{clean}$,
where we use $h(x,y_{1})+h(x,y_{2})\geq 1$ and $f(x,y_{1})+f(x,y_{2})\geq 1$
for any $y_{1}\neq y_{2}$. Since $f(x+{\mathcal{P}}(x),y)>1-\epsilon$ for any
$x\in{\mathcal{D}}_{{{\rm{tr}}}}$, so $-h(x,l_{p})+f(x,l_{p})\geq
1-2\epsilon,\forall(x,y)\in{\mathcal{D}}_{poi}$. Then we get $g_{f,h}(x)\geq
1-2\epsilon,\forall(x,y)\in{\mathcal{D}}_{poi}$ and $|g_{f,h}(x)|\leq
2\epsilon,\forall(x,y)\in{\mathcal{D}}_{clean}$.

Because $F-H$ is a Simple Features recognition space, with conditions (t2) and
(t3), we know that $g_{f,h}({\mathcal{P}}(x))\geq c(1-4\epsilon-k)$ and
$g_{f,h}(x+{\mathcal{P}}(x))-g_{f,h}(x)\geq c(1-4\epsilon-k)$ for all
$x\in{\mathcal{D}}_{{{\rm{tr}}}}\setminus{\mathcal{D}}_{clean}$.

Considering that $h(x,l_{p})$ and $f(x,l_{p})$ have Lipschitz constant $L$,
and by condition (t2), we have
$||{\mathcal{P}}(x_{1})-{\mathcal{P}}(x_{2})||_{2}\leq k$ for all
$(x_{1},y_{1}),(x_{2},y_{2})\in{\mathcal{D}}^{\prime}_{P}$. Then we have
$g_{f,h}({\mathcal{P}}(x))\geq c(1-4\epsilon)-(c+4L)k$ and
$g_{f,h}(x+{\mathcal{P}}(x))-g_{f,h}(x)\geq
c(1-4{\mathbf{\varepsilon}})-(c+4L)k$ for all
$x\in{\mathcal{D}}_{{{\rm{tr}}}}$.

Using the above result, when
$x\in{\mathcal{D}}_{{{\rm{tr}}}}\setminus{\mathcal{D}}_{clean}$, we have
$1\geq g_{f,h}(x+{\mathcal{P}}(x))\geq 1-2\epsilon$ and
$g_{f,h}({\mathcal{P}}(x))\geq c(1-4{\mathbf{\varepsilon}})-(c+4L)k$, and
considering that $|a-b|\leq\max\\{|1-a|,|1-b|\\}$ when $a,b\in[-1,1]$, we have
$|g_{f,h}({\mathcal{P}}(x))-g_{f,h}({\mathcal{P}}(x)+x)|\leq\max\\{1-c(1-4{\mathbf{\varepsilon}})+(c+4L)k,2\epsilon\\}=1-c(1-4{\mathbf{\varepsilon}})+(c+4L)k$,
by $1-c(1-4{\mathbf{\varepsilon}})+(c+4L)k-2\epsilon\geq 0$.

Then, when $x\in{\mathcal{D}}_{clean}$, we have $1\geq
g_{f,h}(x+{\mathcal{P}}(x))\geq
g_{f,h}(x)+c(1-4{\mathbf{\varepsilon}})-(c+4L)k\geq
c(1-4{\mathbf{\varepsilon}})-(c+4L)k-2{\mathbf{\varepsilon}}>0$, so
considering that $g_{f,h}({\mathcal{P}}(x))\geq
c(1-4{\mathbf{\varepsilon}})-(c+4L)k$, we have
$|g_{f,h}({\mathcal{P}}(x))-g_{f,h}({\mathcal{P}}(x)+x)|\leq\max\\{1-g_{f,h}({\mathcal{P}}(x)),1-g_{f,h}(x+{\mathcal{P}}(x))\\}\leq
1-c(1-4{\mathbf{\varepsilon}})+(c+4L)k+2{\mathbf{\varepsilon}}$. So we get
result one.

Result Two: With probability $1-2\frac{4(1-\eta)}{4(1-\eta)+N\eta}-2\delta$,
we have $E_{x\sim
D^{l_{p}}_{\mathcal{S}}}|g_{f,h}({\mathcal{P}}(x))-g_{f,h}({\mathcal{P}}(x)+x)|\leq
2(1-c(1-4\epsilon)+(c+4L)k)+R_{1}(H,F)+8\sqrt{\frac{\ln(1/\delta)}{N\eta\alpha}}$,
where ${\hbox{\rm{Rad}}}_{1}(H,F)$ is a value of the Rademacher complexity of
$H$ and $F$.

By Result one, we can use
$\sum_{(x,y)\in{\mathcal{D}}_{{{\rm{tr}}}}\setminus{\mathcal{D}}_{clean}}|g_{f,h}({\mathcal{P}}(x))-g_{f,h}({\mathcal{P}}(x)+x)|$
to estimate $E_{x\sim
D^{l_{p}}_{\mathcal{S}}}[|g_{f,h}({\mathcal{P}}(x))-g_{f,h}({\mathcal{P}}(x)+x)|]$.

First, use Theorem A.1 and similar to the proof of Theorem A.2, with
probability $1-\frac{4(1-\eta)}{4(1-\eta)+N\eta}-\delta$, we have

$\begin{array}[]{ll}&E_{x\sim
D^{l_{p}}_{\mathcal{S}}}[g_{f,h}({\mathcal{P}}(x))-g_{f,h}({\mathcal{P}}(x)+x)]\leq
1-c(1-4\epsilon)+(c+4L)k+\\\
&2({\hbox{\rm{Rad}}}_{N\eta\alpha/2}^{D^{l_{p}}_{\mathcal{S}}({\mathcal{P}})}(H)+{\hbox{\rm{Rad}}}_{N\eta\alpha/2}^{D^{l_{p}}_{\mathcal{S}}({\mathcal{P}})}(F)+{\hbox{\rm{Rad}}}_{N\eta\alpha/2}^{D^{l_{p}}_{\mathcal{S}}(x+{\mathcal{P}})}(H)+{\hbox{\rm{Rad}}}_{N\eta\alpha/2}^{D^{l_{p}}_{\mathcal{S}}(x+{\mathcal{P}})}(F))+4\sqrt{\frac{\ln(1/\delta)}{N\eta\alpha}}.\end{array}$

Notice that, we use
${\hbox{\rm{Rad}}}_{k}^{D}(H_{1})+{\hbox{\rm{Rad}}}_{k}^{D}(H_{2})\geq{\hbox{\rm{Rad}}}_{k}^{D}(H_{1}-H_{2})$
for any hypothesis space $H_{1},H_{2}$ and $k\geq 0$, distribution $D$ here.

Second, similar as before, with probability
$1-\frac{4(1-\eta)}{4(1-\eta)+N\eta}-\delta$, we have

$\begin{array}[]{cc}&E_{x\sim
D^{l_{p}}_{\mathcal{S}}}[-g_{f,h}({\mathcal{P}}(x))+g_{f,h}({\mathcal{P}}(x)+x)]\leq
1-c(1-4\epsilon)+(c+4L)k+\\\
&2({\hbox{\rm{Rad}}}_{N\eta\alpha/2}^{D^{l_{p}}_{\mathcal{S}}({\mathcal{P}})}(H)+{\hbox{\rm{Rad}}}_{N\eta\alpha/2}^{D^{l_{p}}_{\mathcal{S}}({\mathcal{P}})}(F)+{\hbox{\rm{Rad}}}_{N\eta\alpha/2}^{D^{l_{p}}_{\mathcal{S}}(x+{\mathcal{P}})}(H)+{\hbox{\rm{Rad}}}_{N\eta\alpha/2}^{D^{l_{p}}_{\mathcal{S}}(x+{\mathcal{P}})}(F))+4\sqrt{\frac{\ln(1/\delta)}{N\eta\alpha}}.\end{array}$

Adding these two equations, we get the result, where

${\hbox{\rm{Rad}}}_{1}(H,F)=4({\hbox{\rm{Rad}}}_{N\eta\alpha/2}^{D^{l_{p}}_{\mathcal{S}}({\mathcal{P}})}(H)+{\hbox{\rm{Rad}}}_{N\eta\alpha/2}^{D^{l_{p}}_{\mathcal{S}}({\mathcal{P}})}(F)+{\hbox{\rm{Rad}}}_{N\eta\alpha/2}^{D^{l_{p}}_{\mathcal{S}}(x+{\mathcal{P}})}(H)+{\hbox{\rm{Rad}}}_{N\eta\alpha/2}^{D^{l_{p}}_{\mathcal{S}}(x+{\mathcal{P}})}(F)).$

Result Three: With probability $1-2\frac{4(1-\eta)}{4(1-\eta)+N\eta}-2\delta$,
we have $E_{x\sim{\mathcal{D}}_{S}^{\neq
l_{p}}}|g({\mathcal{P}}(x))-g({\mathcal{P}}(x)+x)|\leq
2(1-c(1-4\epsilon)+(c+4L)k+2{\mathbf{\varepsilon}})+{\hbox{\rm{Rad}}}_{2}(H,F)+8\sqrt{\frac{\ln(1/\delta)}{N(1-\eta)}}$,
where ${\hbox{\rm{Rad}}}_{2}(H,F)$ is a value of the Rademacher complexity of
$H$ and $F$.

By Result one, we can use
$\sum_{(x,y)\in{\mathcal{D}}_{clean}}|g_{f,h}({\mathcal{P}}(x))-g_{f,h}({\mathcal{P}}(x)+x)|$
to estimate $E_{x\sim{\mathcal{D}}_{S}^{\neq
l_{p}}}[|g_{f,h}({\mathcal{P}}(x))-g_{f,h}({\mathcal{P}}(x)+x)|]$.

First, using Theorem A.1 and similar as in proof of Theorem 4.1, with
probability $1-\frac{4\eta}{4\eta+N(1-\eta)}-\delta$, we have

$\begin{array}[]{ll}&E_{x\sim{\mathcal{D}}_{S}^{\neq
l_{p}}}[g_{f,h}({\mathcal{P}}(x))-g_{f,h}({\mathcal{P}}(x)+x)]\leq
1+2{\mathbf{\varepsilon}}-(c(1-4\epsilon)-(c+4L)k)+\\\
&2({\hbox{\rm{Rad}}}_{N(1-\eta)/2}^{{\mathcal{D}}_{S}^{\neq
l_{p}}({\mathcal{P}})}(H)+{\hbox{\rm{Rad}}}_{N(1-\eta)/2}^{{\mathcal{D}}_{S}^{\neq
l_{p}}({\mathcal{P}})}(F)+{\hbox{\rm{Rad}}}_{N(1-\eta)/2}^{{\mathcal{D}}_{S}^{\neq
l_{p}}(x+{\mathcal{P}})}(H)+{\hbox{\rm{Rad}}}_{N(1-\eta)/2}^{{\mathcal{D}}_{S}^{\neq
l_{p}}(x+{\mathcal{P}})}(F))+4\sqrt{\frac{\ln(1/\delta)}{N(1-\eta)}}\end{array}$

and then, similar as above, with probability
$1-\frac{4\eta}{4\eta+N(1-\eta)}-\delta$, we have

$\begin{array}[]{ll}&E_{x\sim{\mathcal{D}}_{S}^{\neq
l_{p}}}[-g_{f,h}({\mathcal{P}}(x))+g_{f,h}({\mathcal{P}}(x)+x)]\leq
1+2{\mathbf{\varepsilon}}-(c(1-4\epsilon)-(c+4L)k)+\\\
&2({\hbox{\rm{Rad}}}_{N(1-\eta)/2}^{{\mathcal{D}}_{S}^{\neq
l_{p}}({\mathcal{P}})}(H)+{\hbox{\rm{Rad}}}_{N(1-\eta)/2}^{{\mathcal{D}}_{S}^{\neq
l_{p}}({\mathcal{P}})}(F)+{\hbox{\rm{Rad}}}_{N(1-\eta)/2}^{{\mathcal{D}}_{S}^{\neq
l_{p}}(x+{\mathcal{P}})}(H)+{\hbox{\rm{Rad}}}_{N(1-\eta)/2}^{{\mathcal{D}}_{S}^{\neq
l_{p}}(x+{\mathcal{P}})}(F))+4\sqrt{\frac{\ln(1/\delta)}{N(1-\eta)}}.\end{array}$

Adding them, we get the result, and
${\hbox{\rm{Rad}}}_{2}(H,F)=4(Rad_{N(1-\eta)/2}^{{\mathcal{D}}_{S}^{\neq
l_{p}}({\mathcal{P}})}(H)+{\hbox{\rm{Rad}}}_{N(1-\eta)/2}^{{\mathcal{D}}_{S}^{\neq
l_{p}}({\mathcal{P}})}(F)+{\hbox{\rm{Rad}}}_{N(1-\eta)/2}^{{\mathcal{D}}_{S}^{\neq
l_{p}}(x+{\mathcal{P}})}(H)+{\hbox{\rm{Rad}}}_{N(1-\eta)/2}^{{\mathcal{D}}_{S}^{\neq
l_{p}}(x+{\mathcal{P}})}(F))$.

Summarize: Finally, considering that

$\begin{array}[]{ll}&{\mathbb{E}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}}}[|(f-h)({\mathcal{P}}(x),l_{p})-(f-h)(x+{\mathcal{P}}(x),l_{p})|]\\\
=&(1-\eta){\mathbb{E}}_{x\sim{\mathcal{D}}_{S}^{\neq
l_{p}}}[|(f-h)({\mathcal{P}}(x),l_{p})-(f-h)(x+{\mathcal{P}}(x),l_{p})|]\\\
&+\eta{\mathbb{E}}_{x\sim{\mathcal{D}}^{l_{p}}_{{\mathcal{S}}}}[|(f-h)({\mathcal{P}}(x),l_{p})-(f-h)(x+{\mathcal{P}}(x),l_{p})|]\\\
=&(1-\eta){\mathbb{E}}_{x\sim{\mathcal{D}}_{S}^{\neq
l_{p}}}[|g_{f,h}({\mathcal{P}}(x))-g_{f,h}(x+{\mathcal{P}}(x))|]+\eta{\mathbb{E}}_{x\sim{\mathcal{D}}^{l_{p}}_{{\mathcal{S}}}}[|g_{f,h}({\mathcal{P}}(x))-g_{f,h}(x+{\mathcal{P}}(x))|]\end{array}$
(20)

by using Result two and three in equation (20), defining
${\hbox{\rm{Rad}}}(H,F)={\hbox{\rm{Rad}}}_{1}(H,F)+{\hbox{\rm{Rad}}}_{2}(H,F)$
and using $\eta<1$, we get the result. ∎

Now, we use Proposition E.6 to prove the Proposition E.4:

###### Proof.

For $H$ in Proposition E.4, we define a new hypothesis space
$H_{1}=\\{h_{1}(x,y)=1-h_{y}(x)\|h\in H\\}$. Similarly, we define $F_{1}$.

We show that $H_{1}$ and $F_{1}$ satisfy the conditions in Proposition E.6:

(1): It is easy to see that for any $h_{1}\in H_{1}$, we have
$h_{1}(x,y_{1})+h_{1}(x,y_{2})=2-(h_{y_{1}}(x)+h_{y_{2}}(x))\geq 1$, and
similar for $F_{1}$. $1-h_{y}(x)$ and $h_{y}(x)$ have the same Lipschitz
constant.

(2): Condition (1) in Proposition E.6 stands for $F_{1}$. By condition (t1) in
Proposition E.4 and $F_{1}(x,y)=1-f_{y}(x)$, we can prove this.

(3): Condition (2) in Proposition E.6 and condition (t2) in E.4 are the same;
condition (3) in Proposition E.6 and condition (t3) in E.4 are the same.

So, $h_{1}$ and $F_{1}$ satisfy the conditions in Proposition E.6. We now use
the proposition for $h_{1}$ and $F_{1}$. Considering that
$h_{1}(x,y)-F_{1}(x,y)=f_{y}(x)-h_{y}(x)$, so we have

$\begin{array}[]{ll}&{\mathbb{E}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}}}[|(f-h)_{l_{p}}({\mathcal{P}}(x))-(f-h)_{l_{p}}(x+{\mathcal{P}}(x))|]\\\
\leq&2(1-c(1-4\epsilon)+k(c+4L))+2\epsilon)+{\hbox{\rm{Rad}}}(H_{1},F_{1})+16\sqrt{\frac{\ln(1/\delta)}{N\alpha}}.\end{array}$

${\hbox{\rm{Rad}}}(H_{1},F_{1})$ is the value of Radermacher complexity of
$H_{1}$ and $F_{1}$, mentioned in Proposition E.6. For such a Rademacher
complexity, using Lemma D.5 and
${\hbox{\rm{Rad}}}_{M}^{\mathcal{D}}(H)\leq\frac{N}{M}Rad_{N}^{\mathcal{D}}(H)$
for any $M<N$, distribution ${\mathcal{D}}$ and hypothesis space $H$, we have

$\begin{array}[]{ll}&{\mathbb{E}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}}}[|(f-h)_{l_{p}}({\mathcal{P}}(x))-(f-h)_{l_{p}}(x+{\mathcal{P}}(x))|]\\\
\leq&2(1-c(1-4\epsilon)+(c+4L)k+2\epsilon)+{\hbox{\rm{Rad}}}2({\mathcal{H}}_{W,D})+16\sqrt{\frac{\ln(1/\delta)}{N\alpha}}\\\
=&2(1-c+(c+4L)k+(2+4c)\epsilon)+{\hbox{\rm{Rad}}}2({\mathcal{H}}_{W,D})+16\sqrt{\frac{\ln(1/\delta)}{N\alpha}}.\end{array}$

${\hbox{\rm{Rad}}}2$ is defined in Definition E.4, and the proposition is
proved. ∎

###  E.3 Proof of Proposition E.3

###### Proof.

We first show that $L$ is a simple feature recognition space with constant 1.

If $w$ satisfies $w(x+{\mathcal{P}}(x))\geq 1-\eta_{1}$ for $\forall(x,0)\in
D$ and $wx\leq\eta_{1}$ for $\forall(x,1)\in D$, then we consider the linear
function $wx-\eta_{1}$. Because we have $wx\leq\eta_{1}$ for $\forall(x,1)\in
D$, so $wx-\eta_{1}\leq 0$ for $\forall(x,1)\in D$. Because $D$ is linearly
inseparable, and there must be a $(x_{0},0)\in D$ such that
$wx_{0}-\eta_{1}\leq 0$, but $w(x_{0}+{\mathcal{P}}(x_{0}))\geq 1-\eta_{1}$.
Thus, we have $w{\mathcal{P}}(x_{0})\geq 1-2\eta_{1}$.

Considering that $||{\mathcal{P}}(x)-{\mathcal{P}}(x_{0})||_{2}\leq k$ for all
$(x,0)\in D$, we have $w{\mathcal{P}}(x)\geq
1-2\eta_{1}-||w||_{2}||({\mathcal{P}}(x)-{\mathcal{P}}(x_{0}))||_{2}\geq
1-2\eta-k$. Moreover, $w(x_{1}+{\mathcal{P}}(x))-wx_{1}=w{\mathcal{P}}(x)$, so
as said above, when $(x,0)\in D$ we have $w(x_{1}+{\mathcal{P}}(x))-wx_{1}\geq
1-2\eta-k$, which is what we want.

Second, we show that $H$ is a simple feature recognition space with constant
$a$.

Because $f$ is an increasing function, similar as before, if
$h(l(x+{\mathcal{P}}(x)))\geq 1-\eta_{1}$ for $\forall(x,0)\in D$ and
$h(l(x))\leq\eta_{1}$ for $\forall(x,1)\in D$, then we have
$h(l(x_{0}))-\eta_{1}\leq 0$ for some $(x_{0},0)\in D$. As a consequence, we
have $1-2\eta_{1}\leq h(l(x_{0}+{\mathcal{P}}(x_{0})))-h(l(x_{0}))\leq
l(x_{0}+{\mathcal{P}}(x_{0}))-l(x_{0})$ by $f^{\prime}(x)\leq 1$. Because
$l(x)\in L$, let $l(x)=wx$, so $w{\mathcal{P}}(x_{0})\geq(1-2\eta_{1})$, and
considering that $h(0)=0$, we have $h(w{\mathcal{P}}(x_{0}))\geq
a(1-2\eta_{1})$.

Then, similar to Step one, we can get $w{\mathcal{P}}(x)\geq 1-2\eta_{1}-k$.
As a consequence, $h(l(x))=h(w{\mathcal{P}}(x))\geq a(1-2\eta_{1}-k)$, and
$h(l(x_{1}+{\mathcal{P}}(x_{0})))-h(l(x_{1}))\geq
a(w(x_{1}+{\mathcal{P}}(x_{0}))-w(x_{1}))=aw{\mathcal{P}}(x_{0})\geq
a(1-2\eta_{1}-k)$, so we get the result.

∎

##  Appendix F More Details on the Experiments

###  F.1 The Experiment Setting

We want to perform experiments in more practical settings:

1: The attacker only accesses part of the training set, so we only use a
portion of the training set data in the process of generating triggers.

2: The attacker cannot control the training process of the victim network, so
we use standard training models for the victim network.

3: The attacker does not know the structure of the victim network and does not
have great computing power, so we only use smaller networks independent of the
victim network in the process of generating triggers.

In previous backdoor attacks, some of these conditions have not been assumed.
For example, attackers are assumed to be able to access the entire network
training set (Gao et al., 2023); attackers know the structure of the network
(Zeng et al., 2022); attackers can control the training process (Gu et al.,
2017); and attackers have some additional information (Ning et al., 2021).

We use networks VGG16 (Simonyan & Zisserman, 2014), ResNet18, WRN34-10 (He et
al., 2016) and datasets CIFAR-10, CIFAR-100 (Krizhevsky et al., 2009), SVHN,
and TinyImagenet with 100 classes (Le & Yang, 2015). When we train victim
network, we use SGD, we have 150 epochs in the training, the learning rate is
0.01, and reduce to $80\%$ at 40-th,80-th, 120-th epochs, use weight decay
$10^{-4}$, momentum $0.9$, each data in the training set will flip or randomly
crop before inputting network in the training.

We will use Algorithm 1 to find the trigger ${\mathcal{P}}(x)$, and the basic
settings of Algorithm 1 are as follows. We randomly choose $50\%$ samples from
the original training set to be $T$.

We choose ${\mathcal{F}}_{1}$ as VGG9 for dataset CIFAR-10 (VGG16 for CIFAR100
or SVHN, Resnet34 for TinyImageNet), use adversarial training with PGD-10 and
$L_{\infty}$ norm budget $8/255$ for dataset CIFAR-10 or SVHN ($4/255$ for
CIFAR-100 and TinyImageNet) to train ${\mathcal{F}}_{1}$. There are 200 epochs
in the adversarial training, learning rate is 0.01, and reduce by half at
100-th and 150-th epochs; use weight decay $10^{-4}$, momentum $0.9$; each
data in the training set will flip or randomly crop after doing PGD-10.

We choose ${\mathcal{F}}_{2}$ to be a two layer network (structure is shown
below). There are 40 epochs in the training of ${\mathcal{F}}_{2}$; learning
rate is 0.01; use weight decay $10^{-4}$, momentum $0.9$; each data in the
training set will flip or randomly crop before inputting ${\mathcal{F}}_{2}$.
The budget of poison is $L_{\infty}$ norm $8/255$ to $32/255$.

Once we obtain the trigger ${\mathcal{P}}(x)$, we will randomly select some
samples with label $l_{p}$ in the training set and add the trigger to them.
Then, we will train the network by using the poisoned training set and measure
the accuracy and the attack success rate on the test set.

Running Time We do our experiments on Pytorch and GPU NVIDIA GeForce RTX 3090.
Under the above experimental setup, the time required for the experiment is
shown in Table 7. It can be seen that most of the time is spent on adversarial
training of the network ${\mathcal{F}}_{1}$.

Table 7: Training time (in minutes). Gp100 means generate poison for 100 samples by using ${\mathcal{F}}_{1}$ and ${\mathcal{F}}_{2}$. dataset | ${\mathcal{F}}_{1}$ | ${\mathcal{F}}_{2}$ | victim ${\mathcal{F}}$ | Gp100
---|---|---|---|---
CIFAR-10 | 400 | 30 | 120 | 2
CIFAR-100 | 600 | 30 | 140 | 3
SVHN | 1000 | 35 | 160 | 3
TinyImageNet | 1600 | 48 | 250 | 4

Reasons for ${\mathcal{F}}_{1}$. ${\mathcal{F}}_{1}$ is a network which is
used to create adversarial noise, and is trained on a small clean dataset. We
hope to conduct the experiment under the premise “Attacker does not about
victim network,” so we avoid using a network with the same structure as victim
network in the process of producing poison. On the other hand, we also hope to
do the experiment under premise “Attacker does not have great computing
power,” so we try to use a smaller network to generate the poison as much as
possible.

The structure of ${\mathcal{F}}_{2}$.

The first layer: with Channel 64 and $3\times 3$ convolution, padding=1, do
Relu and Maxpooling.

The second layer: shape to $16384(=64*16*16)$ dim vector ($65536(=64*32*32)$
for TinyImageNet), and do fully connected layer, and output a 2-dim vector.

Reasons for ${\mathcal{F}}_{2}$. ${\mathcal{F}}_{2}$ is a network that is used
to create shortcuts, and such shortcuts are used to make the clean and poison
dataset linear separable, and ${\mathcal{F}}_{2}$ is trained by Min-Min
method. Generally speaking, if the data is not too complex, the structure of
this network does not need to be particularly large, a two layer network is
enough to create short cut.

We do not choose ${\mathcal{F}}_{2}$ to be a linear function, because we
always use data enhancement in the training, consider that making the enhanced
data linearly separable is very difficult, so we let ${\mathcal{F}}_{2}$ to be
a two-layer network.

About PGD.

PGD-$N$ means using PGD with $N$ steps, and $1/255$ ($2/255$, $3/255$,
$4/255$) attacking rate to get adversarial with budget $8/255$ ($16/255$,
$24/255$, $32/255$).

###  F.2 More Experimental Result

Table 8 is the supplement of Tables 1 and 2, which is the result on CIFAR10
under backdoor attacks with various settings.

Table 8: Baseline evaluations on CIFAR-10. Poison model Accuracy ($A$), poison model target label accuracy ($A_{t}$), and attack success rate ($ASR$). Poison budget: | 0.6% | 1% | 2% | 0.6% | 1% | 2%
---|---|---|---|---|---|---
VGG16
Bound: | $8/255$ | $16/255$
$A$ | 91$\%$ | 91$\%$ | 93$\%$ | 92$\%$ | 91$\%$ | 91$\%$
$A_{t}$ | 92$\%$ | 92$\%$ | 90$\%$ | 92$\%$ | 91$\%$ | 90$\%$
$ASR$ | 13$\%$ | 48$\%$ | 51$\%$ | 82$\%$ | 91$\%$ | 94$\%$
Bound: | $24/255$ | $32/255$
$A$ | 91$\%$ | 90$\%$ | 91$\%$ | 90$\%$ | 92$\%$ | 91$\%$
$A_{t}$ | 92$\%$ | 91$\%$ | 92$\%$ | 92$\%$ | 89$\%$ | 90$\%$
$ASR$ | 97$\%$ | 99$\%$ | 99$\%$ | 99$\%$ | 99$\%$ | 99$\%$
ResNet18
Bound: | $8/255$ | $16/255$
$A$ | 93$\%$ | 92$\%$ | 90$\%$ | 93$\%$ | 91$\%$ | 93$\%$
$A_{t}$ | 92$\%$ | 92$\%$ | 93$\%$ | 93$\%$ | 93$\%$ | 92$\%$
$ASR$ | 14$\%$ | 33$\%$ | 47$\%$ | 86$\%$ | 93$\%$ | 94$\%$
Budget: | $24/255$ | $32/255$
$A$ | 92$\%$ | 92$\%$ | 91$\%$ | 92$\%$ | 92$\%$ | 90$\%$
$A_{t}$ | 92$\%$ | 92$\%$ | 91$\%$ | 91$\%$ | 92$\%$ | 90$\%$
$ASR$ | 96$\%$ | 99$\%$ | 99$\%$ | 98$\%$ | 99$\%$ | 99$\%$

Table 9 is the supplement of Table 3, which is the result on some datasets
under backdoor attacks with various budgets.

Table 9: Accuracy(A) and attack success rate ($ASR$) on CIFAR-100, SVHN and
TinyImageNet, target label $0$. CIFAR-100
---
Budget: | $8/255$ | $16/255$ | $32/255$
poison rate: | 0.6% | 0.8% | 0.6% | 0.8% | 0.6% | 0.8%
$A$ | 71$\%$ | 73$\%$ | 73$\%$ | 72$\%$ | 72$\%$ | 71$\%$
$ASR$ | 4$\%$ | 14$\%$ | 85$\%$ | 92$\%$ | 99$\%$ | 99$\%$
SVHN
Budget: | $8/255$ | $16/255$ | $32/255$
poison rate: | 1$\%$ | 2% | 1% | 2% | 1% | 2%
$A$ | 93$\%$ | 93$\%$ | 93$\%$ | 92$\%$ | 93$\%$ | 91$\%$
$ASR$ | 16$\%$ | 22$\%$ | 63$\%$ | 79$\%$ | 90$\%$ | 99$\%$
TinyImageNet
Budget: | $8/255$ | $16/255$ | $32/255$
poison rate: | 0.6% | 0.8% | 0.6% | 0.8% | 0.6% | 0.8%
$A$ | 61$\%$ | 62$\%$ | 60$\%$ | 60$\%$ | 59$\%$ | 60$\%$
$ASR$ | 2$\%$ | 9$\%$ | 61$\%$ | 82$\%$ | 99$\%$ | 99$\%$

Tables 10 and 11 follow Table 4, and more comparison is shown in it.

Table 10: Benchmark results of attack success rate on CIFAR-10 with VGG16 and ResNet18. Comparison of our method to popular clean-label attacks. Poison ratio is $1\%$ and perturbation have different $l_{\infty}$-norm bound from $8/255$ to $32/255$. Victim | VGG16 | ResNet18
---|---|---
Budget: | $\frac{8}{255}$ | $\frac{16}{255}$ | $\frac{32}{255}$ | $\frac{8}{255}$ | $\frac{16}{255}$ | $\frac{32}{255}$
Ours | 48$\%$ | 91$\%$ | 99$\%$ | 33$\%$ | 93$\%$ | 99$\%$
Clean Label | 18$\%$ | 44$\%$ | 84$\%$ | 12$\%$ | 22$\%$ | 80$\%$
Invisible Poison | 23$\%$ | 71$\%$ | 99$\%$ | 24$\%$ | 73$\%$ | 98$\%$
Hidden Trigger | 36$\%$ | 80$\%$ | 99$\%$ | 26$\%$ | 75$\%$ | 99$\%$
Narcissu | 20$\%$ | 60$\%$ | 92$\%$ | 16$\%$ | 50$\%$ | 92$\%$
Image-specific | 22$\%$ | 68$\%$ | 94$\%$ | 18$\%$ | 70$\%$ | 95$\%$
Reflection | 26$\%$ | 68$\%$ | 99$\%$ | 20$\%$ | 54$\%$ | 99$\%$
Sleeper-Agent | 20$\%$ | 61$\%$ | 97$\%$ | 29 $\%$ | 70$\%$ | 99$\%$
Table 11: Benchmark results of attack success rate on TinyImagenet with network WRN34-10. Comparison of our method to popular clean-label attacks. Poison ratio is $0.8\%$ and budget is $l_{\infty}$-norm bound $16/255$. You can see that our results are very outstanding. Attack methods | ASR
---|---
Ours | 82$\%$
Clean Label | 4$\%$
Invisible Poison | 27$\%$
Hidden Trigger | 44$\%$
Narcissu | 2$\%$
Image-specific | 8$\%$
Reflection | 11$\%$
Sleeper-Agent | 4$\%$

###  F.3 Detail of each Attack

This section shows the experiment settings of the attack methods in Section
6.3. For all attacks, we basically follow the algorithm in the original paper
for experimentation, but they have some different settings from ours in
creating poison and backdoor, which need to be slightly modified according to
our experimental settings.

Ensure Invisible. These attacks design the poison added to the training set as
invisible (i.e. ensure the $L_{\infty}$ norm not more than 8/255, 16/255 or
32/255), but some attack methods will design the trigger as a patch, which has
no norm limitation, as shown in Figure 4. This is unfair for the attacks that
design triggers as invisible. For greater fairness, we require that triggers
must also be invisible (i.e. bound by the $L_{\infty}$ norm) for all attacks,
and as compensation, triggers can be added to the whole image rather than a
patch. If the trigger of an attack method exceeds the norm limit, we use the
following method to compress its trigger within the norm of the limitation:
$x$ is a sample, $t(x)$ is the trigger of $x$ without norm constraint,
$\epsilon$ is the norm limitation. We will compress $t(x)$ to a trigger
$t_{wn}(x)$ satisfying $||t_{wn}(x)||\leq\epsilon$ as:

$t_{wn}(x)={\hbox{\rm{argmin}}}_{||t||<\epsilon}||F(x+t)-F(x+t(x))||$

where $F$ is a feature extraction network which has nine convolution hidden
layers.

Figure 4: When trigger is a patch without norm limitation, it is not
invisible. This figure is from (Souri et al., 2022).

Cost of Attack. For the sake of fairness, we try to ensure that all attack
methods use networks with similar scale in the process of generating poison
and trigger(VGG9 for Cifar10 and ResNet34 for TinyImagenet). Details about
these attack methods are as follows.

(Clean Label): Use PGD-40 to find adversarial of a VGG9, which is trained on
the clean training set.

(Invisible Poison): The auto-encoder architecture has the structure described
in paper (Ning et al., 2021). The original trigger is a disturbance with
$L_{0}$ norm 100 to the lower left part of the image.

(Hidden Trigger): The original trigger is a patch that disturbs 100 pixels to
the lower left part of the image. Use a VGG9 to be a feature extractor in
creating the poison of the training set.

(Narcissu): Use a VGG9 as the surrogate network.

(Image-specific): A U-net with depth 18 has been taken as Trigger Generator.

(Reflection): Select an image and use its reflection as a trigger, adding the
reflection to image through convolution.

(Sleeper-agent): The original trigger is a patch that disturbs 100 pixels to
the lower left part of the image. Use a $VGG9$ to be the proxy network in
creating poison.

###  F.4 Strengthen Attack

We try to strengthen our attack method to bypass the defense by using the
following methods.

Bypass (AT): Use the method (Fu et al., 2020)(min-min-max method, which can
create the shortcut for adversarial learning) to train ${\mathcal{F}}_{2}$,
and ${\mathcal{F}}_{2}$ expands to VGG9.

Bypass (Data Augmentation): Use strong data enhancement in the training
process ${\mathcal{F}}_{1}$ and ${\mathcal{F}}_{2}$ in algorithm 1, and
${\mathcal{F}}_{2}$ expands to VGG9.

Bypass (DPSGD): Use DPSGD in the training process ${\mathcal{F}}_{1}$ and
${\mathcal{F}}_{2}$ in Algorithm 1;

Bypass (Frequency Filter): Using the method in (Dabouei et al., 2020) to
control frequency domain of poison, making poison low frequency.

###  F.5 Some Others Attacks

The transferability of attacks.

Please note that we do experiment under the setting ‘the attacker does not
know the structure of the victim network’ as said in the experimental setup in
Appendix F.1. So, all surrogate networks we used during creating trigger will
not change based on the victim network, only change based on the dataset. What
is mentioned above is reflected in the experimental setup in Appendix F.1. So
the triggers which we used in table 1 for ResNet18, VGG16 and WRN are the
same, then table 1 naturally implies the transferability of our trigger
between different networks are good.

But the drawback of our trigger is that it cannot be transferred between
different datasets, for example, the trigger created for CIFAR-10 can not be
used on CIFAR-100.

Weather Victim Network learns the trigger feature? We will continue the
experiment in Table 1 and consider two special sets:
$D_{op}=\\{({\mathcal{P}}(x),0)|(x,y)\in{\mathcal{D}}_{test}\\}$ and
$D_{op1}=\\{(0.5+{\mathcal{P}}(x),0)|(x,y)\in{\mathcal{D}}_{test}\\}$, where
${\mathcal{D}}_{test}$ is the test set of CIFAR-10, and $0.5+{\mathcal{P}}(x)$
represents each weight of ${\mathcal{P}}(x)$ plus $0.5$. These are the sets of
poisons. We tested the accuracy of the victim network on them to measure
whether the network has learned noise features, and the result is given in
Table 12.

Table 12: Accuracies on ${\mathcal{D}}_{op}$ and ${\mathcal{D}}_{op1}$ for ResNet18 (R) and VGG16 (V). PN is the number of poisoned samples.  Budget: | $8/255$ | $16/255$
---|---|---
PN: | 0.6% | 1% | 2% | 0.6% | 1% | 2%
V, ${\mathcal{D}}_{op}$ | 84$\%$ | 95$\%$ | 98$\%$ | 100$\%$ | 100$\%$ | 100$\%$
R, ${\mathcal{D}}_{op}$ | 80$\%$ | 92$\%$ | 98$\%$ | 99$\%$ | 100$\%$ | 100$\%$
V, ${\mathcal{D}}_{op1}$ | 94$\%$ | 98$\%$ | 99$\%$ | 100$\%$ | 100$\%$ | 100$\%$
R, ${\mathcal{D}}_{op1}$ | 93$\%$ | 98$\%$ | 98$\%$ | 99$\%$ | 100$\%$ | 100$\%$

The victim network has a very high accuracy for the poisoned sets
${\mathcal{D}}_{op}$ and ${\mathcal{D}}_{op1}$, even with the budget $8/255$,
which means the victim network has learned the trigger feature. However, the
data in Table 1 are not as good as those in Table 12, because when the input
contains both original features and poison features, each of them will affect
the output of the network and the final result is decided by them together.
Therefore, when the network learns the original features well, it is also
necessary to increase the scale of poison, and this is why under the premise
of budget $8/255$, the effect does not appear to be good in Table 1. So, we
can reach the result: Victim network is very sensitive to poison features and
uses them for classification. But the victim network still focuses on original
image features, and it will make a choice on the stronger side of these two
features.

###  F.6 More Detail for Section 6.5

The construction details of the poison in Section 6.5 are as follows.

(RN($L_{\infty}$ budget)): ${\mathcal{P}}(x)$ is random noise with
$L_{\infty}$ budget $16/255$ or $32/255$. The method for random selection of
noise is: each pixel of noise is i.i.d. obeying the Bernoulli distribution in
$\\{-16/255,16/255\\}$ or $\\{-32/255,32/255\\}$. Please note that a noise
vector is selected as trigger for all samples, but not each sample selects a
noise as trigger.

(RN($L_{0}$ budget)) ${\mathcal{P}}(x)$ is random noise with $L_{0}$ budget
$200$ or $300$. The method for generating noise is: Randomly select 200 or 300
pixels and change their values to 0. Please note that the position of each
pixels that becomes 0 in each image is the same, but not each sample random
selects some pixel to become 0.

(UA) ${\mathcal{P}}(x)$ is universal adversarial disturbance with $L_{\infty}$
budget $16/255$ and $32/255$, we use the method (Moosavi-Dezfooli et al.,
2017) to find universal adversarial disturbance of a trained VGG9 (training
method is as same as ${\mathcal{F}}_{1}$ as mentioned in Section F.1).

(Adv) ${\mathcal{P}}(x)$ is adversarial disturbance with $L_{\infty}$ budgets
$16/255$ and $32/255$. We use PGD-40 to find adversarial disturbance of a
trained VGG9 (training method is as same as ${\mathcal{F}}_{1}$ as mentioned
in Section F.1).

(SCut) ${\mathcal{P}}(x)$ is shortcut noise with $L_{\infty}$ budgets $16/255$
and $32/255$. The method for generating shortcut noise is Min-Min method
(Huang et al., 2021), using a 2-depth neural network to find shortcut.

(Ours): Following Algorithm 1 and Section F.1.

The result on VGG is in the following table 13.

Table 13: The supplement of Tabel 6. The value of $V_{adv}$ and $V_{sc}$, and Accuracy (A) and attack success rate (ASR) on the test set. Use 12 different triggers. Poison Type | $V_{adv}(\uparrow)$ | $V_{sc}(\downarrow)$ | $ASR(\uparrow)$ | A |
---|---|---|---|---|---
RN $L_{\infty}$, $16/255$ | 2.72 | 0.014 | 16$\%$ | 91$\%$ |
RN $L_{\infty}$, $32/255$ | 6.31 | $10^{-4}$ | 98$\%$ | 90$\%$ |
RN $L_{0}$, $200$ | 4.64 | 0.004 | 76$\%$ | 91$\%$ |
RN $L_{0}$, $300$ | 6.20 | 0.003 | 92$\%$ | 90$\%$ |
UA $16/255$ | 3.19 | 0.002 | 63$\%$ | 91$\%$ |
UA $32/255$ | 17.92 | $10^{-4}$ | 93$\%$ | 90$\%$ |
Adv $16/255$ | 9.77 | 1.27 | 44$\%$ | 90$\%$ |
Adv $32/255$ | 18.63 | 0.35 | 84$\%$ | 90$\%$ |
SCut $16/255$ | 1.21 | $10^{-4}$ | 33$\%$ | 91$\%$ |
SCut $32/255$ | 4.02 | $10^{-5}$ | 91$\%$ | 90$\%$ |
Ours $16/255$ | 7.21 | 0.001 | 91$\%$ | 90$\%$ |
Ours $32/255$ | 15.95 | $10^{-4}$ | 99$\%$ | 92$\%$ |

###  F.7 Verify Theorem 4.1

In this section, we use experiments to verify Theorem 4.1.

We will show that: when ${\mathcal{P}}(x)$ is fixed, the poison rate  will
affect accuracy.

We use dataset CIFAR-10, network ResNet18, target label 0, and poison 1000,
2000, 3000 or 4000 randomly selected images with label 0. We use the follow
trigger ${\mathcal{P}}(x)$ to test our conclusion.

(PN): ${\mathcal{P}}(x)$ is random noise with $L_{\infty}$ budget $8/255$,
$16/255$ and $32/255$. The method for random select noise is: each pixel of
noise is i.i.d. obeying the Bernoulli distribution in $\\{-8/255,8/255\\}$ or
$\\{-16/255,16/255\\}$ or $\\{-32/255,32/255\\}$.

(MI): Mixed image poisoning method. $x+{\mathcal{P}}(x)$ is calculated as:
randomly find an $x_{1}$ without label $0$, and make
$x+{\mathcal{P}}(x)=(1-\lambda)x+\lambda x_{1}$, where
$\lambda=0.05,0.15,0.25$.

(Ours): ${\mathcal{P}}(x)$ is generated by Algorithm 1 with budgets $8/255$,
$16/255$ or $32/255$.

The following table shows the accuracy and accuracy of the image with label 0.

Table 14: Accuracy (A) and accuracy of image with label 0($A_{t}$) on the test set. The ones in parentheses are $A_{t}$. Use nine different triggers.  | 1000 | 2000 | 3000 | 4000
---|---|---|---|---
PN, $8/255$: | 92(91)$\%$ | 92(91)$\%$ | 91(90)$\%$ | 90(88)$\%$
PN, $16/255$: | 91(92)$\%$ | 91(91)$\%$ | 90(90)$\%$ | 90(88)$\%$
PN, $32/255$: | 91(92)$\%$ | 90(89)$\%$ | 89(89)$\%$ | 89(87)$\%$
MI:$\lambda=0.05$ | 92(91)$\%$ | 91(91)$\%$ | 92(90)$\%$ | 90(89)$\%$
MI:$\lambda=0.15$ | 91(92)$\%$ | 90(91)$\%$ | 90(90)$\%$ | 89(89)$\%$
MI:$\lambda=0.25$ | 92(90)$\%$ | 91(90)$\%$ | 89(89)$\%$ | 88(87)$\%$
Ours, $8/255$ | 92(93)$\%$ | 91(92)$\%$ | 91(91)$\%$ | 90(89)$\%$
Ours, $16/255$ | 92(92)$\%$ | 90(91)$\%$ | 90(89)$\%$ | 89(88)$\%$
Ours, $32/255$ | 90(90)$\%$ | 91(90)$\%$ | 90(89)$\%$ | 90(88)$\%$

We can see that the higher the poison rate, the greater the impact on
accuracy. However, the degree of decline is not significant: for more than
3,000 poisoned samples, the accuacy just decreases 4$\%$. This is because the
poison budget is controlled to be small.


lower bound for unweighted MDS. In particular, we will prove the following
theorem.

######  Theorem 41.

Any distributed algorithm in the $\mathsf{CONGEST}$ model which, given an
input graph $G$, produces a $c$-approximate solution to the minimum unweighted
dominating set problem on $G^{2}$ for $c<9/8$ requires $\tilde{\Omega}(n^{2})$
rounds.

The only modification we need is to the set gadgets $G_{MDS}$ and
$G^{\prime}_{MDS}$. In order to do this, we remove the vertices
$\alpha,\beta,\alpha^{\prime},\beta^{\prime}$. We connect each $S_{i}$ to a
new vertex $q_{i}$, each $S^{\prime}_{i}$ to a new vertex $q^{\prime}_{i}$,
each $\overline{S_{i}}$ to a new vertex $\overline{q_{i}}$, and each
$\overline{S^{\prime}_{i}}$ to a new vertex $\overline{q^{\prime}_{i}}$. The
vertices $q_{i},q^{\prime}_{i}$ are connected to $A_{*}[3]$, and the vertices
$\overline{q_{i}},\overline{q^{\prime}_{i}}$ are connected to $B_{*}[3]$ for
each $1\leq i\leq T$. Since the merged path gadgets in $H^{2}_{x,y}$ come from
only shared path gadgets, we can show the following variant of Lemma 33. Since
the proof is similar, we skip it.

######  Lemma 42.

We can assume w.l.o.g. that the vertices $A_{*}[4],A_{*}[5]$ of the merged
path gadget $A_{*}$, and the vertices $S[2]$ where
$S\in\\{A^{S}_{i},A^{a}_{i},A^{S^{\prime}}_{i},A^{a^{\prime}}_{i}\\}_{i=1}^{T}$
do not belong to the MDS of $H^{2}_{x,y}$. A similar statement holds for the
merged path gadget $B_{*}$

Therefore, we can show the following lemma which implies Theorem 41.

######  Lemma 43.

If $DISJ_{T^{2}}(x,y)=\mathrm{false}$ then $H^{2}_{x,y}$ has an MDS of weight
at most $8$ and otherwise any dominating set of $H^{2}_{x,y}$ has weight at
least $9$.

###### Proof.

Note that we can assume that $A_{*}[3]$ and $B_{*}[3]$ are in the dominating
set due to Lemma 36. The vertex $A_{*}[3]$ covers all the vertices
$\\{A_{*}[4]$, $A_{*}[5]$, $A^{a}_{i}[1,2]$, $A^{S}_{i}[1,2]$,
$A^{S^{\prime}}_{i}[1,2]$, $A^{a^{\prime}}_{i}[1,2]$, $S_{i}$,
$S^{\prime}_{i}$, $q_{i}$, $q^{\prime}_{i}\\}_{i=1}^{T}$ and the vertex
$B_{*}[3]$ covers all the vertices $\\{B_{*}[4]$, $B_{*}[5]$,
$B^{b}_{i}[1,2]$, $B^{\overline{S}}_{i}[1,2]$,
$B^{\overline{S^{\prime}}}_{i}[1,2]$, $B^{b^{\prime}}_{i}[1,2]$,
$\overline{S_{i}}$, $\overline{S^{\prime}_{i}}$, $\overline{q_{i}}$,
$\overline{q^{\prime}_{i}}\\}_{i=1}^{T}$.

If $DISJ_{T^{2}}(x,y)=\mathrm{false}$ then there is an index $(i,j)$ such that
$x_{ij}=y_{ij}=1$. Therefore, we add
$A^{a}_{i}[1],S_{i},B^{b}_{i}[1],\overline{S_{i}},S^{\prime}_{j},\overline{S^{\prime}_{j}}$
to the MDS incurring a total cost of $8$. The vertices $S_{i}$ and
$\overline{S_{i}}$ together cover all the uncovered vertices in the set gadget
$G_{MDS}$ along with all row vertices in $A,B$ except $a_{i}$ and $b_{i}$,
whereas the vertices $S^{\prime}_{j}$ and $\overline{S^{\prime}_{j}}$ cover
all the uncovered vertices in the set gadget $G^{\prime}_{MDS}$, along with
all row vertices in $A^{\prime},B^{\prime}$ except $a^{\prime}_{j}$ and
$b^{\prime}_{j}$. Since $x_{ij}=y_{ij}=1$, the vertex $A^{a}_{i}[1]$ covers
both $a_{i}$ and $a^{\prime}_{j}$, and the vertex $B^{b}_{i}[1]$ covers both
$b_{i}$ and $b^{\prime}_{j}$. This means all the vertices in $H^{2}_{x,y}$ are
dominated by a set of weight $6$ and hence the MDS of $H^{2}_{x,y}$ has weight
at most $8$ when $DISJ_{T^{2}}(x,y)=\mathrm{false}$.

Now we look at the case when $DISJ_{T^{2}}(x,y)=\mathrm{true}$. Consider the
uncovered set gadget vertices in $G_{MDS}$ which are
$U={\\{\alpha_{i},\beta_{i}\\}}_{i=1}^{\ell}$ and $G^{\prime}_{MDS}$ which are
$U^{\prime}={\\{\alpha^{\prime}_{i},\beta^{\prime}_{i}\\}}_{i=1}^{\ell}$.
Notice that by Lemma 42, we can assume that $U$ can only be covered by
vertices in $G_{MDS}$, and $U^{\prime}$ can only be covered by vertices in
$G^{\prime}_{MDS}$.

The sets $U,U^{\prime}$ can be covered using $4$ vertices:
$S_{i},\overline{S_{i}},S^{\prime}_{j},\overline{S^{\prime}_{j}}$ for some
$i,j\in\\{1,\dots,T\\}$. We cannot cover all the vertices of $G_{MDS}$ and
$G^{\prime}_{MDS}$ using fewer than $4$ vertices, as it would require using at
most one vertex to cover all vertices in either $G_{MDS}$ or
$G^{\prime}_{MDS}$. This is not possible since no single vertex covers all
vertices ${\\{\alpha_{i},\beta_{i}\\}}_{i=1}^{\ell}$ in $G_{MDS}$, and
${\\{\alpha^{\prime}_{i},\beta^{\prime}_{i}\\}}_{i=1}^{\ell}$ in
$G^{\prime}_{MDS}$ by the construction and the $r$-covering property.

Note that there are other ways of covering $G_{MDS}$, and $G^{\prime}_{MDS}$
using exactly $2$ vertices each. If we pick $q_{i}$ (or $\overline{q_{i}}$),
it is better to pick $S_{i}$ (or $\overline{S_{i}}$) since it covers more
vertices of $U$. The $r$-covering property guarantees that no single set
covers all the $\ell$ elements. But we can also cover $U$ by picking a vertex
$S\in\\{S_{i},\overline{S_{i}}_{i=1}^{T}\\}$ which covers all but one element
$j\in\\{1,\dots,\ell\\}$ along with either $\alpha_{j}$ or $\beta_{j}$. But
this is equivalent to picking $S$ and $\overline{S}$ because $\overline{S}$
will cover both $\alpha_{j}$ and $\beta_{j}$, along with many other row
vertices.

Therefore, we can assume w.l.o.g. that the $4$ vertices used to cover the set
gadgets are $S_{i},\overline{S_{i}},S^{\prime}_{j},\overline{S^{\prime}_{j}}$
for some $i,j\in\\{1,\dots,T\\}$.

Now, the only vertices that are left uncovered are
$a_{i},a^{\prime}_{j},b_{i}$, and $b^{\prime}_{j}$. Note that since
$DISJ_{T^{2}}(x,y)=\mathrm{true}$, there is no $(i,j)$ such that both $x_{ij}$
and $y_{ij}$ are $1$. Without loss of generality, assume $x_{ij}=0$, therefore
there is no vertex in $H^{2}_{x,y}$ that has an edge to both $a_{i}$ and
$a^{\prime}_{j}$. Therefore, we need to pick at least $2$ vertices in
$H^{2}_{x,y}$ to cover $a_{i}$ and $a^{\prime}_{j}$. Neither of these two
vertices will have an edge to $b_{i}$ and $b^{\prime}_{j}$ so we need to pick
at least $3$ vertices to cover all the four vertices. Therefore, every
dominating set has to have size at least $9$. ∎

###### Proof of Theorem 41.

Let $V_{A}=A\cup A^{\prime}\cup S\cup S^{\prime}\cup\\{\alpha_{i}\mid 1\leq
i\leq\ell\\}\cup A_{*}$ and $V_{B}=V\setminus V_{A}$. With these definitions
of $V_{A}$ and $V_{B}$, the size of the cut $E(V_{A},V_{B})$ is at most
$O(\ell)=O(\log T)$. Let $P$ be the predicate that a graph has a minimum
dominating set of size at least $9$. Lemma 43 implies that $H^{2}_{x,y}$ is a
family of lower bound graphs with respect to the function $DISJ$ and the
predicate $P$.

Therefore, Theorem 19 gives an $\tilde{\Omega}(T^{2})$ lower bound for the
problem of distinguishing between the case when a graph with $O(T)$ vertices
has a dominating set of size at least $9$ and the case when it has a
dominating set of size at most $8$. This gives a lower bound for approximation
factor $c<9/8$ which completes the proof of Theorem 41. ∎

##  8 Centralized Hardness Results for $G^{2}$-MVC and $G^{2}$-MDS

In the following theorem we show that using a dangling-path gadget as in
Theorem 20 gives that MVC is NP-complete on $G^{2}$, and a simplified version
of the proof of Theorem 26 gives that there is no FPTAS for MVC on $G^{2}$
unless $P=NP$.

######  Theorem 44.

[No FPTAS for $G^{2}$-MVC] Given input graph $G$, solving $G^{2}$-MVC exactly
is NP-complete. Moreover, there is no FPTAS for $G^{2}$-MVC unless $P=NP$,
i.e., there is no family of algorithms
$\\{A_{\varepsilon}\mid\varepsilon>0\\}$ such that algorithm $A_{\varepsilon}$
runs in time $\operatorname{\text{{\rm poly}}}(n,\frac{1}{\varepsilon})$ and
yields a $(1+\varepsilon)$-approximation for MVC on $G^{2}$, unless $P=NP$.

###### Proof.

For the first part of the theorem, we use a reduction from MVC on $G$. Given a
graph $G=(V_{G},E_{G})$, we construct a graph $H=(V_{H},E_{H})$ by replacing
each edge $e\in E_{G}$ with a dangling path gadget $DP_{e}$ which is a path on
three vertices $p_{e}^{1},p_{e}^{2},p_{e}^{3}$ where $p_{e}^{1}$ is connected
to both the end points of $e$ (as is defined in the proof of Theorem 26). Note
that $V_{H}$ contains the vertices in $V_{G}$ plus the vertices in the
dangling path gadget $DP_{e}$ for each $e\in E_{G}$. Therefore, the size of
$H$ is polynomial in the size of $G$. Now we show that $G$ has a vertex cover
of size $c$ iff $H^{2}$ has a vertex cover of size $c+2|E_{G}|$.

For the forward direction, consider a vertex cover $S_{G}$ of $G$ having size
$c$. We construct a vertex cover $S_{H}$ of $H^{2}$ by taking all the vertices
in $S_{G}$ and adding the two vertices $p_{e}^{1},p_{e}^{2}$ in the dangling
path gadget $DP_{e}$ for all $e\in E_{G}$. The two vertices
$p_{e}^{1},p_{e}^{2}$ cover all the edges in $H^{2}$ incident on $DP_{e}$, and
$S_{G}$ covers all the $H^{2}$ edges that are incident between two vertices in
$V_{G}$. Therefore, $S_{H}$ is a valid vertex cover of $H^{2}$ with
$c+2|E_{G}|$ vertices.

For the reverse direction, consider a vertex cover $S_{H}$ of $H^{2}$ having
size $c^{\prime}$. Lemma 23 implies that an exact MVC $S_{H}$ for $H^{2}$
takes all vertices of $DP_{e}$ except $p_{e}^{3}$ for every dangling path
gadget $DP_{e}$ and that the set of nodes in $S_{H}\cap V_{G}$ is a vertex
cover for $G$. This in particular implies $c^{\prime}\geq 2|E_{G}|$. Let $c$
be the number of vertices in $S_{H}\cap V_{G}$. These vertices have to form a
valid vertex cover of $G$ because the subgraph of $H^{2}$ induced by $V_{G}$
is exactly $G$.

For the second part of the theorem, we follow a line similar to that of
Theorem 26, as follows. Let $ALG$ be a $(1+\varepsilon)$-approximation scheme
for MVC on $G^{2}$ that completes in $\operatorname{\text{{\rm
poly}}}(n,\frac{1}{\varepsilon})$ time. We construct the same graph $H$ from
$G$ as before by adding a dangling path gadget $DP_{e}$ for each edge $e\in
E_{G}$. We run $ALG$ on $H^{2}$ with $\varepsilon=1/(3|E_{G}|)$. Note that by
the previous argument the size of the minimum vertex cover of $H^{2}$ is
$c+2|E_{G}|$ where $c$ is the size of the minimum vertex cover in $G$.
Therefore, $ALG$ will find a vertex cover of size at most
$(1+\varepsilon)(c+2|E_{G}|)=c+2|E_{G}|+(c+2|E_{G}|)/(3|E_{G}|)=c+2|E_{G}|+\alpha$
where $\alpha<1$. Therefore, $ALG$ runs in polynomial time and we can find the
MVC of $G$ by taking the solution returned by $ALG$ and taking all the
corresponding $V_{G}$ vertices in the cover. This contradicts the
$NP$-hardness of vertex cover in $G$ (assuming $P\neq NP$). ∎

We also show that one cannot efficiently compute good approximations of
$G^{2}$-MDS unless one obtains a major breakthrough result.

######  Theorem 45 (No better-than-$\ln n$-approximation for MDS on $G^{2}$).

Given input graph $G$, solving MDS exactly on $G^{2}$ is NP-complete.
Moreover, if there is some $\varepsilon>0$ such that a polynomial-time
algorithm can solve MDS on $G^{2}$ to within an approximation factor of
$(1-\varepsilon)\ln n$, then $NP\subseteq DTIME\left(n^{O(\log\log
n)}\right)$.

###### Proof.

We prove this by showing a polynomial time reduction from MDS in $G$ to MDS in
$G^{2}$. The theorem follows by the hardness of approximation result for $G$
[Fei98]. The reduction is that for each edge $e$ in $G=(V_{G},E_{G})$, we add
a dangling path gadget $DP_{e}$ and merge all the dangling path gadgets in $G$
to form the merged path gadget $DP_{E}$. We call this new graph
$H=(V_{H},E_{H})$. Note that $H$ has $O(m)$ vertices where $m=|E_{G}|$ which
is polynomial in the size of $G$. The vertices in $V_{H}$ can be partitioned
into two sets, namely the vertices in $DP_{E}$ and the vertices corresponding
to $V_{G}$, which we call the $G$-vertices. Now we show that the size of the
MDS in $H^{2}$ is $W+1$, iff the size of the MDS in $G$ is $W$.

We start with the forward direction, let $S_{H}$ be an MDS of $H^{2}$ having
size $W+1$. By Lemma 36 we know that $DP_{E}[3]$ has to belong to $S_{H}$ (and
therefore $W\geq 0$) and it covers all the vertices in the merged path gadget
$DP_{E}$. Note that given $DP_{E}[3]$ is in $S_{H}$, we can assume that no
other vertex of $DP_{E}$ can belong to $S_{H}$ by arguing along similar lines
as the proof of Lemma 33. Now $S_{H}$ needs to cover the $G$-vertices in $H$,
without using any vertices in $DP_{E}$. The subgraph of $H^{2}$ induced by the
$G$-vertices is exactly the graph $G$. So $S_{H}\setminus\\{DP_{E}[3]\\}$ must
form an MDS of $G$ because if $G$ has a dominating set $S$ of size $<W$, then
it contradicts the optimality of $S_{H}$ because $S\cup\\{DP_{E}[3]\\}$ is a
valid dominating set of $H^{2}$ having size $<W+1$.

To prove the reverse direction, let $S_{G}$ be an MDS of $G$ of size $W$. We
construct $S_{H}$ by taking the $G$-vertices in $H^{2}$ corresponding to
$S_{G}$ along with the vertex $DP_{E}[3]$. The set $S_{H}$ has size $W+1$ and
it covers all the vertices in $H^{2}$ because the vertices corresponding to
$S_{G}$ dominate all the $G$-vertices in $H^{2}$, and $DP_{E}[3]$ dominates
all the vertices in $DP_{E}$. Therefore, $S_{H}$ is a dominating set of
$H^{2}$ of size $W+1$. Note that $H^{2}$ cannot have a smaller dominating set
because then we can use the argument for the forward direction to extract a
dominating set of $G$ of size $<W$, which contradicts the assumption that
$S_{G}$ is an MDS of $G$. ∎

## Acknowledgement

This project was partially supported by the European Union’s Horizon 2020
Research and Innovation Programme under grant agreement no. 755839 (Keren
Censor-Hillel, Yannic Maus).

## References

  * [ACK16] Amir Abboud, Keren Censor-Hillel, and Seri Khoury.  Near-linear lower bounds for distributed distance computations, even in sparse networks.  In Proceedings of the 30th International Symposium on Distributed Computing, DISC, pages 29–42, 2016.
  * [Bak94] Brenda S. Baker.  Approximation algorithms for np-complete problems on planar graphs.  J. ACM, 41(1):153–180, 1994.
  * [BBiKS19] Ran Ben-Basat, Ken ichi Kawarabayashi, and Gregory Schwartzman.  Parameterized Distributed Algorithms.  In 33rd International Symposium on Distributed Computing (DISC 2019), pages 6:1–6:16, 2019.
  * [BCD+19] Nir Bachrach, Keren Censor-Hillel, Michal Dory, Yuval Efron, Dean Leitersdorf, and Ami Paz.  Hardness of distributed optimization.  In PODC, pages 238–247, 2019.
  * [BCS17] Reuven Bar-Yehuda, Keren Censor-Hillel, and Gregory Schwartzman.  A distributed (2 + $\epsilon$)-approximation for vertex cover in $O(\log\Delta/\epsilon\log\log\Delta)$ rounds.  J. ACM, 64(3):23:1–23:11, 2017.
  * [BE83] Reuven Bar-Yehuda and Shimon Even.  A local-ratio theorem for approximating the weighted vertex cover problem.  In Proceedings of the WG ’83, International Workshop on Graph theoretic Concepts in Computer Science, pages 17–28, 1983.
  * [BEKS18] Ran Ben-Basat, Guy Even, Ken-ichi Kawarabayashi, and Gregory Schwartzman.  A deterministic distributed 2-approximation for weighted vertex cover in ${O}(\log N\log\Delta/\log^{2}\log\Delta)$ rounds.  In SIROCCO, 2018, 2018.
  * [CD18] Keren Censor-Hillel and Michal Dory.  Distributed spanner approximation.  In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, Egham, United Kingdom, July 23-27, 2018, pages 139–148, 2018.
  * [CK00] Jianer Chen and Iyad Kanj.  On approximating minimum vertex cover for graphs with perfect matching.  In Proceedings of the 11th International Conference on Algorithms and Computation, ISAAC ’00, page 132–143, Berlin, Heidelberg, 2000\. Springer-Verlag.
  * [CK18] Artur Czumaj and Christian Konrad.  Detecting cliques in CONGEST networks.  In 32nd International Symposium on Distributed Computing, DISC, pages 16:1–16:15, 2018.
  * [CKP17] Keren Censor-Hillel, Seri Khoury, and Ami Paz.  Quadratic and near-quadratic lower bounds for the CONGEST model.  In 31st International Symposium on Distributed Computing, DISC 2017, October 16-20, 2017, Vienna, Austria, pages 10:1–10:16, 2017.
  * [CKPY18] Keren Censor-Hillel, Telikepalli Kavitha, Ami Paz, and Amir Yehudayoff.  Distributed construction of purely additive spanners.  Distributed Computing, 31(3):223–240, 2018.
  * [DKM19] Janosch Deurer, Fabian Kuhn, and Yannic Maus.  Deterministic distributed dominating set approximation in the CONGEST model.  In Proc. ACM Symp. on Principles of Distributed Computing (PODC), 2019.
  * [DZ10] Amir Dembo and Ofer Zeitouni.  Large Deviations Techniques and Applications, volume 95.  01 2010.
  * [Elk04] Michael Elkin.  Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem.  In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004, pages 331–340, 2004.
  * [Fei98] Uriel Feige.  A threshold of ln n for approximating set cover.  J. ACM, 45(4):634–652, July 1998.
  * [FGKO18] Orr Fischer, Tzlil Gonen, Fabian Kuhn, and Rotem Oshman.  Possibilities and impossibilities for distributed subgraph detection.  In Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, SPAA, pages 153–162, 2018.
  * [FHW12] Silvio Frischknecht, Stephan Holzer, and Roger Wattenhofer.  Networks cannot compute their diameter in sublinear time.  In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1150–1162, 2012.
  * [FKP13] Pierre Fraigniaud, Amos Korman, and David Peleg.  Towards a complexity theory for local distributed computing.  J. ACM, 60(5):35:1–35:26, 2013.
  * [FPPS99] Dimitris Fotakis, Grammati Pantziou, George Pentaris, and Paul Spirakis.  Frequency assignment in mobile and radio networks.  DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 1999.
  * [GHK18] Mohsen Ghaffari, David G. Harris, and Fabian Kuhn.  On derandomizing local distributed algorithms.  In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 662–673, Los Alamitos, CA, USA, oct 2018. IEEE Computer Society.
  * [GJ79] Michael R. Garey and David S. Johnson.  Computers and Intractability: A Guide to the Theory of NP-Completeness.  W. H. Freeman, 1979.
  * [GK18] Mohsen Ghaffari and Fabian Kuhn.  Derandomizing distributed algorithms with small messages: Spanners and dominating set.  In 32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15-19, 2018, pages 29:1–29:17, 2018.
  * [GKM17] Mohsen Ghaffari, Fabian Kuhn, and Yannic Maus.  On the complexity of local distributed graph problems.  In Proc. ACM Symp. on Theory of Computing (STOC), pages 784–797. ACM, 2017.
  * [Hal95] Magnús M. Halldórsson.  Approximating discrete collections via local improvements.  In Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 22-24 January 1995. San Francisco, California, USA, pages 160–169, 1995.
  * [JRS02] Lujun Jia, Rajmohan Rajaraman, and Torsten Suel.  An efficient distributed algorithm for constructing small dominating sets.  Distributed Computing, 15(4):193–205, 2002.
  * [KMW16] Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer.  Local computation: Lower and upper bounds.  J. ACM, 63(2):17:1–17:44, 2016.
  * [KN97] Eyal Kushilevitz and Noam Nisan.  Communication Complexity.  Cambridge University Press, New York, NY, USA, 1997.
  * [KR08] Subhash Khot and Oded Regev.  Vertex cover might be hard to approximate to within 2-epsilon.  J. Comput. Syst. Sci., 74(3):335–349, 2008.
  * [LPPP03] Zvi Lotker, Elan Pavlov, Boaz Patt-Shamir, and David Peleg.  MST construction in o(log log n) communication rounds.  In SPAA, pages 94–100, 2003.
  * [LY94] Carsten Lund and Mihalis Yannakakis.  On the hardness of approximating minimization problems.  J. ACM, 41(5):960–981, September 1994.
  * [MS06] Damon Mosk-Aoyama and Devavrat Shah.  Computing separable functions via gossip.  In Proceedings of the Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing, PODC 2006, Denver, CO, USA, July 23-26, 2006, pages 113–122, 2006.
  * [Nis02] Noam Nisan.  The communication complexity of approximate set packing and covering.  In Automata, Languages and Programming, pages 868–875, Berlin, Heidelberg, 2002. Springer Berlin Heidelberg.
  * [Pel00] David Peleg.  Distributed Computing: A Locality-Sensitive Approach.  SIAM, 2000.
  * [PPS16] Gopal Pandurangan, David Peleg, and Michele Scquizzato.  Message lower bounds via efficient network synchronization.  In SIROCCO, pages 75–91, 2016.
  * [PR00] David Peleg and Vitaly Rubinovich.  A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction.  SIAM J. Comput., 30(5):1427–1442, 2000.
  * [RG20] Vaclav Rozhoň and Mohsen Ghaffari.  Polylogarithmic-time deterministic network decomposition and distributed derandomization.  In Proc. ACM Symp. on Theory of Computing (STOC), 2020.
  * [SHK+12] Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer.  Distributed verification and hardness of distributed approximation.  SIAM J. Comput., 41(5):1235–1265, 2012.
  * [SYZ08] Zhendong Shao, Roger K. Yeh, and David Zhang.  The l(2,1)-labeling on graphs and the frequency assignment problem.  Applied Mathematics Letters, 21(1):37 – 41, 2008.
  * [Vaz01] Vijay V. Vazirani.  Approximation Algorithms.  Springer-Verlag, Berlin, Heidelberg, 2001.
  * [WS11] David P. Williamson and David B. Shmoys.  The Design of Approximation Algorithms.  Cambridge University Press, USA, 1st edition, 2011.