$|D_{2}|>\gamma\ell/3$, then we get a contribution of $\Omega(\ell)$ by Case
6. So, assuming $\mu^{\prime}(i)\neq i$, we are left with the case that

$|\\{v\\!=\\!2(i-1)\ell+j\in F_{i}\setminus
D:j\in\Delta_{i,\mu^{\prime}(i)}\\}|\geq\gamma\ell-2\gamma\ell/3.$

In this case, assuming $\mu^{\prime}(i)=\mu^{\prime\prime}(i)$, we get a
contribution of at least $\gamma\ell/3$ to the difference between $G_{n}$ and
$\mu(G_{n})$. This contribution is due to the difference in the edges that
match $F_{\mu^{\prime}(i)}$ and $S_{\mu^{\prime}(i)}$ in $G_{n}$ and the edges
that match $F_{i}$ and $S_{i}$ in $G_{n}$, where edges that have an endpoint
(or its $\phi_{i}$-mate) in $D$ were discarded. Specifically, letting
$k=\mu^{\prime}(i)=\mu^{\prime\prime}(i)\neq i$, the pair
$(v,w)=(2(i-1)\ell+j,2(i-1)\ell+\ell+\pi_{i}(j))\in F_{i}\times S_{i}$
contributes to the difference if $j\in\Delta_{i,k}$ and both
$\mu(v)=2(k-1)\ell+j\in F_{k}$ and $\mu(w)=2(k-1)\ell+\ell+\pi_{i}(j)\in
S_{k}$ hold (i.e., $v\not\in D_{1}$ and $v,\phi_{i}^{-1}(w)\not\in
D_{2}$).202020Recall that
$\phi_{i}^{-1}(w)=\phi^{-1}((2(i-1)\ell+\ell+\pi_{i}(j)))=2(i-1)\ell+j=v$.
Indeed, in this case $\\{v,w\\}$ is an edge in $G_{n}$ but $\\{v,w\\}$ is not
an edge in ${\mu^{-1}}(G_{n})$. (Hence, if the number of vertices of this case
is $\Omega(|\\{u\in[n]:\mu(u)\neq u\\}|)$, then the difference between $G_{n}$
and ${\mu^{-1}}(G_{n})$ is $\Omega(|\\{u\in[n]:\mu(u)\neq u\\}|)$, and the
same holds with respect to the difference between $\mu(G_{n})$ and $G_{n}$.)

Combining all these cases, we get a total contribution that is proportional to
$|\\{v\in[n]:\mu(v)\neq v\\}|$, where we might have counted the same
contribution in several different cases. Since the number of cases is a
constant, the theorem follows.

###### Digest: Using large collections of pairwise far apart permutations.

The construction presented in the proof of Theorem 4.2 utilizes a collection
of $(\ell!)^{\Omega(1)}$ permutations over $[\ell]$ that are pairwise far-
apart (i.e., every two permutations differ on $\Omega(\ell)$ inputs). Such a
collection is constructed in ${\widetilde{O}}(\ell!)$-time by an iterative
exhaustive search, where the permutations are selected iteratively such that
in each iteration we find a permutation that is far from permutations that
were included in previous iterations. We mention that in Section 4.3 we shall
use a collection of $\exp(\Omega(\ell))$ such permutations that is locally
computable (i.e., given the index of a permutation we find its explicit
description in polynomial time). We also mention that, in follow-up work [22],
we provided a locally computable collection of $(\ell!)^{\Omega(1)}$ that are
pairwise far-apart.

###### Digest: Combining two robustly self-ordered graphs.

One ingredient in the proof of Theorem 4.2 is forming connected components
that consist of two robustly self-ordered graphs that have different vertex
degrees and are connected by a bounded-degree bipartite graph. Implicit in the
proof is the fact that such the resulting graph is robustly self-ordered
graph.

###### Claim 4.3

(combining two $\Omega(1)$-robustly self-ordered graphs): For $i\in\\{1,2\\}$
and constant $\gamma>0$, let $G_{i}=(V_{i},E_{i})$ be an $\gamma$-robustly
self-ordered graph, and consider a graph $G=(V_{1}\cup V_{2},E_{1}\cup
E_{2}\cup E)$ of maximum degree $d$ such that $E$ contain edges with a single
vertex in each $V_{i}$; that is, $G$ consists of $G_{1}$ and $G_{2}$ and an
arbitrary bipartite graph that connects them. If the maximun degree in $G$ of
each vertex in $V_{1}$ is strictly smaller than the minimum degree of each
vertex in $V_{2}$, then $G$ is $\gamma/(2d+3)$-robustly self-ordered.

Proof Sketch: For an arbitrary permutation $\mu:V\to V$, let $T$ denote the
set of its non-fixed-points, and consider the following two cases.

Case 1:

More than $t=\gamma^{\prime}\cdot|T|$ vertices are mapped by $\mu$ from
$G_{1}$ to $G_{2}$, where $\gamma^{\prime}=\gamma/(2d+3)$.

In this case, we get a contribution of at least one unit per each such vertex,
due to the difference in the degrees between $V_{1}$ and $V_{2}$.

Case 2:

at most $t$ vertices are mapped by $\mu$ from $G_{1}$ to $G_{2}$.

In this case, letting $T_{i}$ denote the set of non-fixed vertices in $G_{i}$
that are mapped by $\mu$ to $G_{i}$, we get a contribution of at least
$\sum_{i=1,2}(\gamma\cdot|T_{i}|-d\cdot t)$ units, where the negative term is
due to possible change in the incidence with vertices in $T\setminus T_{i}$.
Hence, the total contribution in this case is at least
$\gamma\cdot(|T|-2t)-2d\cdot t=\gamma^{\prime}\cdot|T|$.

The claim follows.

###### Regaining regularity and expansion.

While Theorem 4.2 achieves our main objective, it useful towards some
applications (see, e.g., the proof of Theorem 4.5) to obtain this objective
with graphs that are both regular and expanding. This is achieved by applying
Theorem 2.6. Hence, we have.

###### Theorem 4.4

(Theorem 4.2, revised): For any sufficiently large constant $d$, there exists
an efficiently constructable family $\\{G_{n}\\}_{n\in\mathbb{N}}$ of robustly
self-ordered $d$-regular expander graphs. That is, there exists a polynomial-
time algorithm that on input $1^{n}$ outputs the $n$-vertex graph $G_{n}$.

####  4.3 Strong (i.e., local) constructions

While Theorem 4.4 provides an efficient construction of robustly self-ordered
$d$-regular expander graphs, we seek a stronger notion of constructability.
Specifically, rather than requiring that the graph be constructed in time that
is polynomial in its size, we require that the neighbors of any given vertex
can be found in time that is polynomial in the vertex’s name (i.e., time that
is polylogarithmic in the size of the graph). We call such graphs locally
constructable (and comment that the term “strongly explicit” is often used in
the literature).

###### Theorem 4.5

(locally constructing robustly self-ordered graphs): For any sufficiently
large constant $d$, there exists a locally constructable family
$\\{G_{n}=([n],E_{n})\\}_{n\in\mathbb{N}}$ of robustly self-ordered
$d$-regular graphs. That is, there exists a polynomial-time algorithm that on
input $n$ and $v\in[n]$ outputs the list of neighbours of vertex $v$ in
$G_{n}$. Furthermore, the graphs are either expanders or consist of connected
components of logarithmic size.

(Indeed, this establishes Theorem 1.3.) We comment that using the result of
[22], we can also get connected components of sub-logarithmic size, as in
Theorem 4.2.212121Specifically, the result of [22] provides a construction of
a collection of $L=\exp(\Omega(\ell\log\ell))$ permutations over $[\ell]$ that
are pairwise far-apart along with a polynomial-time algorithm that, on input
$i\in[L]$, returns a description of the $i^{\rm th}$ permutation (i.e., the
algorithm should run in ${\rm poly}(\log L)$-time). Using this algorithm, we
can afford to set $\ell=\frac{O(\log n)}{\log\log n}$ as in Theorem 4.2.

Proof: We employ the idea that underlies the proof of Theorem 4.2, while
starting with an efficiently constructable family of robustly self-ordered
graphs (as provided by Theorem 4.4) rather than with the mere existence of a
family of such graphs (equiv., with $\ell$-vertex graphs that can be
constructed in ${\rm poly}(\ell!)$-time). We use a slightly larger setting of
$\ell$, which allows us to use a collection of $\exp(\Omega(\ell))$ pairwise-
far-apart permutations (rather than a collection of
$\exp(\Omega(\ell\log\ell))$ such permutations). Lastly, we apply the same
transformation as in the proof of Theorem 4.4 (so to regain regularity and
expansion). Details follow.

Given a generic $n$, let $\ell=O(\log n)$, which implies that $\exp(\ell)={\rm
poly}(n)$. By Theorem 4.4, for all sufficiently large $d^{\prime}$, we can
construct $\ell$-vertex $d^{\prime}$-regular expander graphs that are robustly
self-ordered (with respect to the robustness parameter $c$) in ${\rm
poly}(\ell)$-time. Again, we shall use two such graphs: a $d^{\prime}$-regular
graph, denoted $G^{\prime}_{\ell}=([\ell],E^{\prime}_{\ell})$, and a
$d^{\prime\prime}$-regular graph, denoted
$G^{\prime\prime}_{\ell}=([\ell],E^{\prime\prime}_{\ell})$, where
$d^{\prime\prime}=d^{\prime}+1$.

Using $G^{\prime}_{\ell}$ and $G^{\prime\prime}_{\ell}$, we construct an
$n$-vertex robustly self-ordered graph, denoted $G_{n}$, that consists of
$n/2\ell$ connected components that are pairwise far from being isomorphic to
one another. This is done by picking $m=n/2\ell$ permutations, denoted
$\pi_{1},...,\pi_{m}:[\ell]\to[\ell]$, that are pairwise far-apart, and
constructing $2\ell$-vertex graphs such that the $i^{\rm th}$ such graph
consist of a copy of $G^{\prime}_{\ell}$ and a copy of
$G^{\prime\prime}_{\ell}$ that are connected by a matching as determined by
the permutation $\pi_{i}$. (as detailed in Eq. (8)).

Using the fact that $m<2^{\ell}$ (rather that $m=\exp(\Theta(\ell\log\ell))$),
we can construct each of these permutations in ${\rm poly}(\ell)$-time by
using sequences of disjoint traspositions determined via a good error
correcting code. Specifically, for $k=\log_{2}m<\log_{2}n$, we use an error
correcting code $C:\\{0,1\\}^{k}\to\\{0,1\\}^{\ell}$ of constant rate (i.e.,
$\ell=O(k)$) and linear distance (i.e., the codewords are $\Omega(\ell)$ bits
apart from each other), and let $\pi_{i}(2j-1)=2j-1+C(i)_{j}$ and
$\pi_{i}(2j)=2j-C(i)_{j}$, where $i\in[m]=[2^{k}]\equiv\\{0,1\\}^{k}$ and
$j\in[\ell/2]$. (That is, the $i^{\rm th}$ permutation switches the pair
$(2j-1,2j)\in[\ell]^{2}$ if and only if the $j^{\rm th}$ bit in the $i^{\rm
th}$ codeword is 1, where $C(i)$ is considered the $i^{\rm th}$ codeword.)

Like in the proof of Theorem 4.2, the $i^{\rm th}$ connected component of
$G_{n}$ is isomorphic to a graph with the vertex set $[2\ell]$ and the edge
set

$E^{\prime}_{\ell}\;\cup\;\\{\\{\ell+u,\ell+v\\}:\\{u,v\\}\in
E^{\prime\prime}_{\ell}\\}\;\cup\;\\{\\{v,\ell+\pi_{i}(v)\\}:v\\!\in\\![\ell]\\}.$
(8)

The key observation is that, for every $i\in[m]$ and $j\in[\ell]$, the
neighborhood of the $j^{\rm th}$ (resp., $(\ell+j)^{\rm th}$) vertex in the
$i^{\rm th}$ connected component of the $n$-vertex graph $G_{n}$ is determined
by $G^{\prime}_{\ell}$ and $\pi_{i}(j)$ (resp., by $G^{\prime\prime}_{\ell}$
and $\pi_{i}^{-1}(j)$), which means that it can be found in ${\rm
poly}(\ell)$-time. This implies local constructability, since $\ell=O(\log
n)$.

The fact that $G_{n}$ is robustly self-ordered was already established in the
proof of Theorem 4.2, which is oblivious of the permutations used as long as
any pair of permutations disagrees on $\Omega(\ell)$ points. Lastly, we may
obtain regularity and expansion by applying Theorem 2.6.

####  4.4 Local self-ordering

Recall that by Definition 1.1 a graph $G=([n],E)$ is called self-ordered if
for every graph $G^{\prime}=(V^{\prime},E^{\prime})$ that is isomorphic to $G$
there exists a unique bijection $\phi:V^{\prime}\to[n]$ such that
$\phi(G^{\prime})=G$. One reason for our preferring the term “self-ordered”
over the classical term “asymmetric” is that we envision being given such an
isomorphic copy $G^{\prime}=(V^{\prime},E^{\prime})$ and asked to find its
unique isomorphism to $G$, which may be viewed as ordering the vertices of
$G^{\prime}$ according to (their name in) $G$. The task of finding this unique
isomorphism will be called self-ordering $G^{\prime}$ according to $G$ or
self-ordering $G^{\prime}$ (when $G$ is clear from the context).

Evidently, the task of self-ordering a given graph $G^{\prime}$ according to a
self-ordered graph $G$ that can be efficiently constructed reduces to testing
isomorphism. When the graphs have bounded-degree the latter task can be
performed in polynomial-time [29]. These are general facts that do apply also
to the robustly self-ordered graph $G_{n}$ constructed in the proof of Theorem
4.5. However, in light of the fact that the graph $G_{n}$ is locally
constructable, we can hope for more. Specifically, it is natural to ask if we
can perform self-ordering of a graph $G^{\prime}$ that is isomorphic to
$G_{n}$ in a local manner; that is, given a vertex in $G^{\prime}$ (and oracle
access to the incidence function of $G^{\prime}$), can we find the
corresponding vertex in $G_{n}$ in ${\rm poly}(\log n)$-time? Let us define
this notion formally.

###### Definition 4.6

(locally self-ordering a self-ordered graph): We say that a self-ordered graph
$G=([n],E)$ is locally self-ordered if there exists a polynomial-time
algorithm that, given a vertex $v$ in any graph
$G^{\prime}=(V^{\prime},E^{\prime})$ that is isomorphic to $G$ and oracle
access to the incidence function of $G^{\prime}$, finds $\phi(v)\in[n]$ for
the unique bijection $\phi:V^{\prime}\to[n]$ such that $\phi(G^{\prime})=G$
(i.e., the unique isomorphism of $G^{\prime}$ to $G$).

Indeed, the isomorphism $\phi$ orders the vertices of $G^{\prime}$ in
accordance with the original (or target) graph $G$. We stress that the
foregoing algorithm works in time that is polynomial in the description of a
vertex (i.e., ${\rm poly}(\log n))$-time), which is polylogarithmic in the
size of the graph (i.e., $n$). We show that such algorithms exist for the
graphs constructed in the proof of Theorem 4.5.

###### Theorem 4.7

(locally self-ordering the graphs of Theorem 4.5): For any sufficiently large
constant $d$, there exists a locally constructable family
$\\{G_{n}=([n],E_{n})\\}_{n\in\mathbb{N}}$ of robustly self-ordered
$d$-regular graphs that are locally self-ordered. Furthermore, the graphs are
either expanders or consist of connected components of logarithmic size.

As in Theorem 4.5, we can obtain connected components of sub-logarithmic size
by using [22].

Proof: We first consider the version that yields $n$-vertex graphs that
consist of connected components of logarithmic size. The basic idea is that it
we can afford reconstructing the connected component in which the input vertex
reside, and this allows us both to determine the index of the vertex in this
connected component as well as the index of the component in the graph.
Specifically, on input a vertex $v$ in a graph $G^{\prime}$ that is isomorphic
to $G_{n}$, we proceed as follows.

  1. 1.

Using queries to the incidence function of $G^{\prime}$, we explore and
retrieve the entire $2\ell$-vertex connected component in which $v$ resides,
where $\ell=\log_{2}n$.

Recall that this connected component consists of (copies of) two $\ell$-vertex
regular graphs, denoted $G^{\prime}_{\ell}$ and $G^{\prime\prime}_{\ell}$,
that are connected by a matching. Furthermore, these graphs have different
degrees and are each (robustly) self-ordered.

  2. 2.

Relying on the different degrees, we identify the foregoing partition of this
$2\ell$-vertex component into two $\ell$-vertex (self-ordered) graphs, denoted
$A_{v}$ and $B_{v}$, where $A_{v}$ (resp., $B_{v}$) is isomorphic to
$G^{\prime}_{\ell}$ (resp., $G^{\prime\prime}_{\ell}$).

  3. 3.

Relying on the self-ordering of $G^{\prime}_{\ell}$ (resp.,
$G^{\prime\prime}_{\ell}$), we order the vertices of $A_{v}$ (resp.,
$G^{\prime\prime}_{v}$). This is done by constructing $G^{\prime}_{\ell}$
(resp., $G^{\prime\prime}_{\ell}$), and using an isomorphism tester. The order
of the vertices in $A_{v}$ and $B_{v}$ also determines the permutation that
defines the matching between the two graphs.

  4. 4.

Relying on the correspondence between the permutations used in the
construction and codewords of a good error-correcting code, we decode the
relevant codeword (i.e., this is decoding without error). This yields the
index of the permutation in the collection, which equals the index of the
connected component.

Note that this refers to the basic construction that was presented in the
proof of Theorem 4.5, before it was transformed to a regular graph and to an
expander. Recall that both transformations are performed by augmenting the
graph with auxiliary edges that are assigned a different color than the
original edges, and that edges with different colors are later replaced by
copies of different (constant-size) gadgets. These transformations do not
hinder the local self-ordering procedure described above, since it may
identify the original graph (and ignore the gadgets that replace other edges).
The claim follows.

###### Local reversed self-ordering.

While local self-ordering a (self-ordered) graph seems the natural local
version of self-ordering the graph, an alternative notion called local
reversed self-ordering will be defined and studied next (and used in Section
5). Both notions refer to a self-ordered graph, denoted $G=([n],E)$, and to an
isomorphic copy of it, denoted $G^{\prime}=(V^{\prime},E^{\prime})$; that is,
$G=\phi(G^{\prime})$ for a (unique) bijection $\phi:V^{\prime}\to[n]$. While
local self-ordering is the task of finding the index of a given vertex of
$G^{\prime}$ according to $G$ (i.e., given $v\in V^{\prime}$, find
$\phi(v)\in[n]$), local reversed self-ordering is the task of finding the
vertex of $G^{\prime}$ that has a given index in $G$ (i.e., given $i\in[n]$,
find $\phi^{-1}(i)\in V^{\prime}$). In both cases, the graph $G$ is locally
constructible and we are given oracle access to the incidence function of
$G^{\prime}$. In addition, in the reversed task, we assume that the algorithm
is given an arbitrary vertex in $G^{\prime}$, since otherwise there is no hope
to hit any element of $V^{\prime}$.222222Needless to say, this is not needed
in case $V^{\prime}=[n]$, which is the case that is used in Section 5.

###### Definition 4.8

(locally reversed self-ordering): We say that a self-ordered graph $G=([n],E)$
is locally reversed self-ordered if there exists a polynomial-time algorithm
that, given $i\in[n]$ and oracle access to the incidence function of a graph
$G^{\prime}=(V^{\prime},E^{\prime})$ that is isomorphic to $G$ and an
arbitrary vertex $s\in V^{\prime}$, finds $\phi^{-1}(i)\in V^{\prime}$ for the
unique bijection $\phi:V^{\prime}\to[n]$ such that $\phi(G^{\prime})=G$ (i.e.,
the unique isomorphism of $G^{\prime}$ to $G$).

We stress that the foregoing algorithm works in time that is polynomial in the
description of a vertex (i.e., ${\rm poly}(\log n))$-time), which is
polylogarithmic in the size of the graph (i.e., $n$). We show that such
algorithms exist for variants of the graphs constructed in the proof of
Theorem 4.5. In fact, we show a more general result that refers to any graph
that is locally self-ordered and for which short paths can be locally found
between any given pair of vertices.

###### Theorem 4.9

(sufficient conditions for locally reversed self-ordering of graphs): Suppose
that $\\{G_{n}=([n],E_{n})\\}_{n\in\mathbb{N}}$ is a family of bounded degree
graphs that is locally self-ordered. Further suppose that given $v,u\in[n]$,
one can find in polynomial-time a path from $u$ to $v$ in $G_{n}$. Then,
$\\{G_{n}=([n],E_{n})\\}_{n\in\mathbb{N}}$ is locally reversed self-ordered.

We mention that a family of robustly self-ordered graphs that is locally self-
ordered can be transformed into one that also supports locally finding short
paths. This is done by superimposing the graphs of this family with graphs
that supports locally finding short paths, while using different colors for
the edges of the two graphs and later replacing these colored edges by gadgets
(as done in Section 2.1). We also mention that applying degree reduction to
the hyper-cube (i.e., replacing the original vertices with simple cycles)
yields a graph that supports locally finding short paths.232323For any
$\ell\in\mathbb{N}$, the resulting graph consists of the vertex-set
$\\{{\langle{x,i}\rangle}\\!:\\!x\\!\in\\!\\{0,1\\}^{\ell}\,\&\,i\\!\\!\in\\![\ell]\\}$
and edges that connect ${\langle{x,i}\rangle}$ to ${\langle{x\oplus
0^{i-1}10^{\ell-i},i}\rangle}$ and to ${\langle{x,i+1}\rangle}$, where
$\ell+1$ stands for 1. For simplicity of exposition, we also add self-loops on
all vertices. Then, given ${\langle{x,i}\rangle}$ and ${\langle{y,j}\rangle}$,
we can combine the $2\ell$-path that goes from ${\langle{x,i}\rangle}$ to
${\langle{y,i}\rangle}$ with the $|j-i|$-path that goes from
${\langle{y,i}\rangle}$ to ${\langle{y,j}\rangle}$, where the odd steps on the
first path move from ${\langle{z,k}\rangle}$ to ${\langle{z\oplus
0^{i-1}10^{\ell-i},k}\rangle}$ (or stay in place) and the even steps (on this
path) move from ${\langle{z,k}\rangle}$ to ${\langle{z,k+1}\rangle}$.

Proof: On input $i\in[n]$ and $s\in V^{\prime}$, and oracle access to the
incidence function of a graph $G^{\prime}=(V^{\prime},E^{\prime})$ that is
isomorphic to $G_{n}$, we proceeds as follows.

  1. 1.

Using the local self-ordering algorithm, we find $i_{0}=\phi(s)$, where
$\phi:V^{\prime}\to[n]$ is the unique bijection satisfying
$\phi(G^{\prime})=G$.

  2. 2.

Using the path-finding algorithm for $G$, we find a ${\rm poly}(\log n)$-long
path from $i_{0}$ to $i$ in $G$.

Let $\ell$ denote the length of the path, and denote its intermediate vertices
by $i_{1},...,i_{\ell-1}$; that is, the full path is
$i_{0},i_{1},...,i_{\ell-1},i_{\ell}=i$.

  3. 3.

For $j=1,...,\ell$, we find $v_{j}\stackrel{{\scriptstyle\rm
def}}{{=}}\phi^{-1}(i_{j})$ as follows. First, using queries to the incidence
function of $G^{\prime}$, we find all neighbors (in $G^{\prime}$) of
$v_{j-1}$, where $v_{0}\stackrel{{\scriptstyle\rm def}}{{=}}s$ (and, indeed,
$v_{0}=\phi^{-1}(i_{0})$). Next, using the local self-ordering algorithm, we
find the indices of all these vertices in $G$; that is, for every vertex $w$
that neighbors $v_{j-1}$, we find $\phi(w)$. Last, we set $v_{j}$ to be the
neighbor that has index $i_{j}$ in $G$; that is, $v_{j}$ satisfies
$\phi(v_{j})=i_{j}$.

Hence, $v_{\ell}$ is the desired vertex; that is, $v_{\ell}$ satisfies
$\phi(v_{\ell})=i_{\ell}=i$.

Assuming that the local self-ordering algorithm has query complexity $q(n)$,
that the paths found in $G$ have length at most $\ell(n)$, and that $d$ is the
degree bound, the query complexity of our reversed self-ordering algorithm is
$(1+\ell(n)\cdot d)\cdot(q(n)+1)$, where we count both our direct queries to
the incidence function of $G$ and the queries performed by the local self-
ordering algorithm. Similar considerations apply to its time complexity.

###### Corollary 4.10

(a version of Theorem 4.7 supporting local reversed self-ordering): For any
sufficiently large constant $d$, there exists a locally constructable family
$\\{G_{n}=([n],E_{n})\\}_{n\in\mathbb{N}}$ of robustly self-ordered graphs of
maximum degree $d$ that are both locally self-ordered and locally reversed
self-ordered.

The corollary follows by combining Theorem 4.7 with Theorem 4.9, while using
the augmentation outlined following the statement of Theorem 4.9. We mention
that Corollary 4.10 will be used in Section 5.

###  5 Application to Testing Bounded-Degree Graph Properties

Our interest in efficiently constructable bounded-degree graphs that are
robustly self-ordered was triggered by an application to property testing.
Specifically, we observed that such constructions can be used for proving a
linear lower bound on the query complexity of testing an efficiently
recognizable graph property in the bounded-degree graph model.

It is well known that 3-Colorability has such a lower bound [3], but this set
is NP-complete. On the other hand, linear lower bounds on the query complexity
of testing efficiently recognizable properties of functions (equiv.,
sequences) are well known (see [18, Sec. 10.2.3]). So the idea was to
transport the latter lower bounds from the domain of functions to the domain
of bounded-degree graphs, and this is where efficient constructions of
robustly self-ordered bounded-degree graphs come into play. (We mention that
an alternative way of obtaining the desired lower bound was outlined in [17,
Sec. 1], see details below.)

More generally, the foregoing transportation demonstrates a general
methodology of transporting lower bounds that refer to testing binary strings
to lower bounds regarding testing graph properties in the bounded-degree graph
model. The point is that strings are ordered objects, whereas graphs
properties are effectively sets of unlabeled graphs, which are unordered
objects. Hence, we need to make the graphs (in the property) ordered, and
furthermore make this ordering robust in the very sense that is reflected in
Definition 1.2. Essentially, we provide a reduction of testing a property of
strings to testing a (related) property of graphs.

We apply this methodology to obtain a subexponential separation between the
complexities of testing and tolerant testing of graph properties in the
bounded-degree graph model. This result is obtained by transporting an
analogous result that was known for testing binary strings [15]. In addition
to using a reduction from tolerantly testing a property of strings to
tolerantly testing a property of graphs, this trasportation also uses a
reduction in the opposite direction, which relies on the local computation
features asserted in Corollary 4.10.

###### Organization of this section.

We start with a brief review of the bounded-degree graph model for testing
graph properties. Next, we prove the aforementioned linear lower bound on the
query complexity of testing an efficiently recognizable property, and later we
abstract the reduction that underlies this proof. Observing that this
reduction applies also to tolerant testing, and presenting a reduction in the
opposite direction, we derive the aforementioned separation between testing
and tolerant testing.

###### Background.

Property testing refers to algorithms of sublinear query complexity for
approximate decision; that is, given oracle access to an object, these
algorithms (called testers) distinguish objects that have a predetermined
property from objects that are far from the property. Different models of
property testing arise from different query access and different distance
measures.

In the last couple of decades, the area of property testing has attracted
significant attention (see, e.g., [16]). Much of this attention was devoted to
testing graph properties in a variety of models including the dense graph
model [18], and the bounded-degree graph model [20] (surveyed in [16, Chap. 8]
and [16, Chap. 9], resp.). In this section, we refer to the bounded-degree
graph model, in which graphs are represented by their incidence function and
distances are measured as the ratio of the number of differing incidences to
the maximal number of edges.

Specifically, for a degree bound $d\in\mathbb{N}$, we represent a graph
$G=([n],E)$ of maximum degree $d$ by the incidence function
$g:[n]\times[d]\to[n]\cup\\{0\\}$ such that $g(v,i)$ indicates the $i^{\rm
th}$ neighbor of $v$ (where $g(v,i)=0$ indicates that $v$ has less than $i$
neighbors). The distance between the graphs $G=([n],E)$ and
$G^{\prime}=([n],E^{\prime})$ is defined as the size of the symmetric
difference between $E$ and $E^{\prime}$ over $dn/2$.

A tester for a property $\Pi$ is given oracle access to the tested object,
where here oracle access to a graph means oracle access to its incidence
function. In addition, such a tester is given a size parameter $n$ (i.e., the
number of vertices in the graph), and a proximity parameter, denoted
$\epsilon>0$. Tolerant testers, introduced in [30] (and briefly surveyed in
[16, Sec. 12.1]), are given an additional parameter, $\eta<\epsilon$, which is
called the tolerance parameter.

###### Definition 5.1

(testing and tolerant testing graph properties in the bounded-degree graph
model): For a fixed degree bound $d$, a tester for a graph property $\Pi$ is a
probabilistic oracle machine that, on input parameters $n$ and $\epsilon$, and
oracle access to an $n$-vertex graph $G=([n],E)$ of maximum degree $d$,
outputs a binary verdict that satisfies the following two conditions.

  1. 1.

If $G\in\Pi$, then the tester accepts with probability at least $2/3$.

  2. 2.

If $G$ is $\epsilon$-far from $\Pi$, then the tester accepts with probability
at most $1/3$, where $G$ is $\epsilon$-far from $\Pi$ if for every $n$-vertex
graph $G^{\prime}=([n],E^{\prime})\in\Pi$ of maximum degree $d$ it holds that
the size of the symmetric difference between $E$ and $E^{\prime}$ has
cardinality that is greater than $\epsilon\cdot dn/2$.

A tolerant tester is also given a tolerance parameter $\eta$, and is required
to accept with probability at least $2/3$ any graph that is $\eta$-close to
$\Pi$ (i.e., not $\eta$-far from $\Pi$).242424Of course, a tolerant tester is
also required to reject with probability at least $2/3$ any graph that is
$\epsilon$-far from $\Pi$.

We stress that a graph property is defined as a property that is preserved
under isomorphism; that is, if $G=([n],E)$ is in the graph property $\Pi$,
then all its isomorphic copies are in the property (i.e., $\pi(G)\in\Pi$ for
every permutation $\pi:[n]\to[n]$). The fact that we deal with graph
properties (rather than with properties of functions) is the source of the
difficulty (of transporting results from the domain of functions to the domain
of graphs) and the reason that robust self-ordering is relevant.252525As noted
in Section 1.1.1, this is a special case of the general phenomenon pivoted at
the difference between ordered and unordered structures, which arises in many
contexts (in complexity and logic).

The query complexity of a tester for $\Pi$ is a function (of the parameters
$d,n$ and $\epsilon$) that represents the number of queries made by the tester
on the worst-case $n$-vertex graph of maximum degree $d$, when given the
proximity parameter $\epsilon$. Fixing $d$, we typically ignore its effect on
the complexity (equiv., treat $d$ as a hidden constant). Also, when stating
that the query complexity is $\Omega(q(n))$, we mean that this bound holds for
all sufficiently small $\epsilon>0$; that is, there exists a constant
$\epsilon_{0}>0$ such that distinguishing between $n$-vertex graphs in $\Pi$
and $n$-vertex graphs that are $\epsilon_{0}$-far from $\Pi$ requires
$\Omega(q(n))$ queries.

###### Our first result.

With the foregoing preliminaries in place, we state the first result of this
section, which is proved using Theorem 4.2.

###### Theorem 5.2

(linear query complexity lower bound for testing an efficiently recognizable
graph property in the bounded-degree graph model): For any sufficiently large
constant $d$, there exists an efficiently recognizable graph property $\Pi$
such that testing $\Pi$ in the bounded-degree graph model (with degree bound
$d$) has query complexity $\Omega(n)$. Furthermore, each $n$-vertex graph in
$\Pi$ consists of connected components of size $o(\log n)$.

The main part of the theorem was known before: As observed in [17, Sec. 1],
there exists graph properties that are recognizable in polynomial-time and yet
are extremely hard to test in the bounded-degree graph model. This follows
from the fact that the local reduction from testing 3LIN (mod 2) to testing
3-Colorability used by Bogdanov, Obata, and Trevisan [3] is invertible in
polynomial-time (which is a common feature of reductions used in the context
of NP-completeness proofs).262626Of course, 3LIN (i.e., the satisfiability of
linear equations (with three variables each) over ${\rm GF}(2)$) is easily
solvable in polynomial-time. Nevertheless, Bogdanov et al. [3] use a reduction
of 3LIN to 3-Colorability (via 3SAT) that originates in the theory of NP-
completeness in order to reduce between the testing problems. Indeed, their
reduction actually demonstrates that the set of (3-colorable) graphs that are
obtained by applying this reduction to satisfiable 3LIN (mod 2) instances is
hard to test (i.e., requires linear query complexity in the bounded-degree
graph model).272727Like almost all reductions of this type, the analysis of
the reduction actually refers to the promise problem induced by the image of
the reduction (i.e., the image of both the yes- and no-instances). We note
that the resulting property contains only connected graphs, which means that
Theorem 5.2 has some added value: The fact that it applies to graphs with tiny
connected components is interesting, since testing properties of such graphs
may seem easy (or at least not extremely hard) at first thought.

Proof: Our starting point is a property $\Phi$ of (binary) strings (equiv.,
Boolean functions) that is recognizable in polynomial-time but has a linear
query complexity lower bound (see, e.g., [19, Sec. 7]). This refers to a model
in which one makes queries to bits of the tested string, and the distance
between strings is the (relative) Hamming distance. Such lower bounds were
transported to the dense graph model in [18, 10.2.3] (see also [19]), but – to
the best of own knowledge – no such transportation were performed before in
the context of the bounded-degree graph model. Using robustly self-ordered
graphs of bounded degree, we present such a transportation.

###### Construction 5.2.1

(from properties of strings to properties of bounded-degree graphs): Suppose
that $\\{G_{n}=([n],E_{n})\\}_{n\in\mathbb{N}}$ is a family of robustly self-
ordered graphs of maximum degree $d-2$.

  * •

For every $n\in\mathbb{N}$ and $s\in\\{0,1\\}^{n}$, we define the graph
$G^{\prime}_{s}=([3n],E^{\prime}_{s})$ such that

$E^{\prime}_{s}=E_{n}\cup\\{\\{i,n+i\\},\\{i,2n+i\\}:i\in[n]\\}\cup\\{\\{n+i,2n+i\\}:i\in[n]\wedge
s_{i}=1\\}$ (9)

That is, $G^{\prime}_{s}$ consists of a copy of $G_{n}$ augmented by $2n$
vertices such that vertex $i\in[n]$ forms a triangle with $n+i$ and $2n+i$ is
$s_{i}=1$, and forms a wedge with $n+i$ and $2n+i$ otherwise.

  * •

For a set of strings $\Phi$, we define $\Pi=\bigcup_{n\in\mathbb{N}}\Pi_{n}$
as the set of all graphs that are isomorphic to some graph $G^{\prime}_{s}$
such that $s\in\Phi$; that is,

$\Pi_{n}=\\{\pi(G^{\prime}_{s}):s\in(\Phi\cap\\{0,1\\}^{n})\wedge\pi\in{\rm
Sym}_{3n}\\}$ (10)

where ${\rm Sym}_{3n}$ denote the set of all permutations over $[3n]$.

We may assume, without loss of generality, that $G_{n}$ has no isolated
vertices. Hence, given a graph of the form $\pi(G^{\prime}_{s})$, the vertices
of $G_{n}$ are easily identifiable as having degree at least three (since
vertices outside $G_{n}$ have degree at most two). The foregoing construction
yields a local reduction of $\Phi$ to $\Pi$, where locality means that each
query to $G^{\prime}_{s}$ can be answered by making a constant number of
queries to $s$, and the (standard) validity of the reduction is based on the
fact that $G_{n}$ is asymmetric.282828Standard validity means that $s\in\Phi$
if and only if $G^{\prime}_{s}\in\Pi$. Evidently, $s\in\Phi$ is mapped to
$G^{\prime}_{s}\in\Pi$; the asymmetry of $G_{n}$ is used to show that
$s\not\in\Phi$ is mapped to $G^{\prime}_{s}\not\in\Pi$, since $G^{\prime}_{s}$
can not be isomorphic to any graph $G^{\prime}_{w}$ such that $w\neq s$. This,
by itself, does not mean that if $s$ is far from $\Phi$ then $G^{\prime}_{s}$
is far from $\Pi$.

In order to be useful towards proving lower bounds on the query complexity of
testing $\Pi$, we need to show that the foregoing reduction is “distance
preserving” (i.e., strings that are far from $\Phi$ are transformed into
graphs that are far from $\Pi$). The hypothesis that $G_{n}$ is robustly self-
ordered is pivotal to showing that if the string $s$ is far from $\Phi$, then
the graph $G^{\prime}_{s}$ is far from $\Pi$.

###### Claim 5.2.2

(preserving distances): If $s\in\\{0,1\\}^{n}$ is $\epsilon$-far from $\Phi$,
then the $3n$-vertex graph $G^{\prime}_{s}$ (as defined in Construction 5.2.1)
is $\Omega(\epsilon)$-far from $\Pi$.

Proof: We prove the contrapositive. Suppose that $G^{\prime}_{s}$ is
$\delta$-close to $\Pi$. Then, for some $r\in\Phi$ and a permutation
$\pi:[3n]\to[3n]$, it holds that $G^{\prime}_{s}$ is $\delta$-close to
$\pi(G^{\prime}_{r})$. (The possible use of a non-trivial permutation arises
from the fact that $\Pi$ is closed under isomorphism.) If $\pi(i)=i$ for every
$i\in[n]$, then $s$ must be $(3d\delta/2)$-close to $r$, where $d$ is the
degree bound (of the model), since $s_{i}=1$ (resp., $r_{i}=1$) if and only if
$i$ forms a triangle with $n+i$ and $2n+i$ in $G^{\prime}_{s}$ (resp., in
$\pi(G^{\prime}_{r})=G^{\prime}_{r}$).292929Hence, $G^{\prime}_{s}$ is
$\delta$-close to $G^{\prime}_{r}$ implies that
$|\\{i\\!\in\\![n]\\!:\\!s_{i}\neq r_{i}\\}|\leq\delta\cdot 3dn/2$, which
means that $s$ is $\frac{3\delta dn/2}{n}$-close to $r$. Unfortunately, the
foregoing condition (i.e., $\pi(i)=i$ for every $i\in[n]$) need not hold in
general.

In general, the hypothesis that $\pi(G^{\prime}_{r})$ is $\delta$-close to
$G^{\prime}_{s}$ implies that $\pi$ maps at most $3\delta dn/2$ vertices of
$[n]$ to $\\{n+1,...,3n\\}$. This is the case since each vertex of $[n]$ has
degree at least three in $G^{\prime}_{r}$, whereas the other vertices have
degree at most two in $G^{\prime}_{s}$ (or in any other graph
$G^{\prime}_{s^{\prime}}$). Hence, if
$t=|\\{i\\!\in\\![n]\\!:\\!\pi(i)\\!\in\\!\\{n+1,...,3n\\}|$, then
$\pi(G^{\prime}_{r})$ and $G^{\prime}_{s}$ differ on at least $t$ edges,
whereas the hypothesis is that the difference is at most $\delta\cdot 3dn/2$.

Turning to the vertices $i\in[n]$ that $\pi$ maps to $[n]\setminus\\{i\\}$, we
upper-bound their number by $O(\delta d^{2}n)$, since the difference between
$\pi(G^{\prime}_{r})$ and $G^{\prime}_{s}$ is at most $\delta\cdot 3dn/2$,
whereas the hypothesis that $G_{n}$ is $c$-robustly self-ordered implies that
the difference between $\pi(G^{\prime}_{r})$ and $G^{\prime}_{s}$ (or any
other graph $G^{\prime}_{w}$) is at least

$\Delta=c\cdot|\\{i\\!\in\\![n]\\!:\\!\pi(i)\neq
i\\}|-d\cdot|\\{i\\!\in\\![n]\\!:\\!\pi(i)\not\in[n]\\}|.$

(Compare Case 6 in the proof of Theorem 4.2.)303030Hence,
$\Delta\leq\delta\cdot 3dn/2$ implies that
$\displaystyle|\\{i\in[n]:\pi(i)\neq i\\}|$ $\displaystyle=$
$\displaystyle\frac{\Delta+d\cdot|\\{i\in[n]:\pi(i)\not\in[n]\\}|}{c}$
$\displaystyle\leq$ $\displaystyle\frac{3\delta dn/2+d\cdot 3\delta dn/2}{c}$
which is $O(\delta d^{2}n)$.

Letting $I=\\{i\\!\in\\![n]\\!:\\!\pi(i)\\!=\\!i\\}|$, observe that
$D\stackrel{{\scriptstyle\rm def}}{{=}}|\\{i\in I:r_{i}\neq s_{i}\\}|\leq
3\delta dn/2$, since $r_{i}\neq s_{i}$ implies that, for every $i\in I$, the
subgraph induced by $\\{i,n+i,2n+1\\}$ is different in $\pi(G^{\prime}_{r})$
and $G^{\prime}_{s}$ (i.e., it is a triangle in one graph and contains two
edges in the other), whereas by the hypothesis $\pi(G^{\prime}_{r})$ and
$G^{\prime}_{s}$ differ on at most $\delta\cdot 3dn/2$ edges. Recalling that
$|I|=n-O(\delta d^{2}n)$, it follows that $|\\{i\in[n]:r_{i}\neq
s_{i}\\}|\leq(n-|I|)+D=O(\delta d^{2}n)$. Recalling that $d$ is a constant, we
infer that $s$ is $O(\delta)$-close to $r\in\Phi$, and the claims follows.

Conclusion. Starting with Theorem 4.2 (i.e., an efficient construction of
robustly self-ordered graphs of bounded degree), using Construction 5.2.1, and
applying Claim 5.2.2, the theorem follows. Specifically, we need to verify the
following facts.

  * •

The set $\Pi$ is polynomial-time recognizable.

Given an $3n$-vertex graph $G^{\prime}$, an adequate algorithm first tries to
identify and order the vertices of the corresponding graph $G_{n}$, which
means that it finds $s\in\\{0,1\\}^{n}$ such that $G^{\prime}$ is isomorphic
to $G^{\prime}_{s}$ (or determines that no such $s$ exists). (Note that once
the vertices of $G_{n}$ are identified, their unique ordering, whenever it
exists, can be found in polynomial time by running an isomorphism tester on
the subgraph induced by them (while relying on the fact that the degree of the
graph is bounded [29]).) Having found $s$, the algorithm accepts if and only
if $s\in\Phi_{n}$, where $\Phi$ is polynomial-time recognizable by our
starting hypothesis.

  * •

Testing $\Pi$ requires linear query complexity.

This is shown by reducing testing $\Phi$ to testing $\Pi$, while recalling
that testing $\Phi$ requires linear query complexity. Given (proximity
parameter $\epsilon$ and) oracle access to a string $s\in\\{0,1\\}^{n}$, we
invoke the tester for $\Pi$ (with proximity parameter $\Omega(\epsilon)$)
while emulating oracle access to $G^{\prime}_{s}$ in a straightforward manner
(i.e., each query to $G^{\prime}_{s}$ is answered by making at most one query
to $s$). Recall that $s\in\Phi$ implies $G^{\prime}_{s}\in\Pi$, whereas by
Claim 5.2.2 if $s$ is $\epsilon$-far from $\Phi$ then $G^{\prime}_{s}$ is
$\Omega(\epsilon)$-far from $\Pi$.

This completes the proof, since the $n$-vertex graphs of Theorem 4.2 have
connected components of size $o(\log n)$.

###### Digest: Reducing testing properties of strings to testing graph
properties.

We wish to highlight the fact that the proof of Theorem 5.2 is based on a
general reduction of testing any property $\Phi$ of strings to testing a
corresponding (bounded-degree) graph property $\Pi$. This reduction is
described in Construction 5.2.1 and its validity is proved in Claim 5.2.2.
Recall that, for any $n$, the graph property $\Pi$ consists of $3n$-vertex
graphs (of bounded-degree) that encode the different $n$-bit long strings in
$\Phi$. This reduction is local and preserves distances:

Locality:

Each string $s\in\\{0,1\\}^{n}$ is encoded by a graph $G^{\prime}_{s}$ such
that each query to $G^{\prime}_{s}$ can be answered by making at most one
query to $s$.

Preserving distances:

If $s\in\Phi$ then $G^{\prime}_{s}\in\Pi$, whereas if $s$ is $\epsilon$-far
from $\Phi$ then $G^{\prime}_{s}$ is $\Omega(\epsilon)$-far from $\Pi$.

Recall that $G^{\prime}_{s}$ consists of a fixed robustly self-ordered
$n$-vertex graph $G_{n}$ augmented by ($n$ two-vertex) gadgets that encode
$s$. Let us spell out the effect of this reduction.

###### Corollary 5.3

(implicit in the proof of Theorem 5.2): For $\Phi$ and $\Pi$ as in
Construction 5.2.1, let $Q_{\Phi}$ and $Q_{\Pi}$ denote the query complexities
of testing $\Phi$ and $\Pi$, respectively. Then, $Q_{\Phi}(n,\epsilon)\leq
Q_{\Pi}(3n,\Omega(\epsilon))$. Likewise, letting $Q^{\prime}_{\Phi}$ (resp.,
$Q^{\prime}_{\Pi}$) denote the query complexity of tolerantly testing $\Phi$
(resp., $\Pi$), it holds that $Q^{\prime}_{\Phi}(n,\eta,\epsilon)\leq
Q^{\prime}_{\Pi}(3n,\eta/3,\Omega(\epsilon))$.

The tolerant testing part requires an additional justification. Specifically,
we observe that strings $s$ that are $\eta$-close to $\Phi$ yield graphs
$G^{\prime}_{s}$ that are $\eta/3$-close to $\Pi$. This is the case because,
if the $n$-bit long strings $s$ and $r$ differ on $k$ bits, then the
$3n$-vertex graphs $G^{\prime}_{s}$ and $G^{\prime}_{r}$ differ on $k$ vertex
pairs. In preparation to proving the separation between the complexities of
testing and tolerant testing, we show a reduction in the opposite direction.
This reduction holds provided that the robustly self-ordered graphs used in
the definition of $\Pi$ are locally reversed self-ordered (see Definition
4.8).

###### Proposition 5.4

(reducing testing $\Pi$ to testing $\Phi$): Suppose that the graphs used in
Construction 5.2.1 are locally self-ordered and locally reversed self-ordered,
and let $\Phi,\Pi$ and $Q_{\Phi},Q_{\Pi}$ be as in Corollary 5.3. Then,
$Q_{\Pi}(3n,\epsilon)\leq{\rm poly}(\log
n)\cdot(Q_{\Phi}(n,2\epsilon)+O(1/\epsilon))$. Furthermore, one-sided error
probability is preserved.313131A tester is said to have one-sided error
probability if it always accepts objects that have the property.

Recall that the hypothesis can be met by using Corollary 4.10.

Proof: Given oracle access to a graph $G^{\prime}=([3n],E^{\prime})$, we first
test that $G^{\prime}$ is isomorphic to $G^{\prime}_{s}$, for some
$s\in\\{0,1\\}^{n}$, and then invoke the tester for $\Phi$ while providing it
with oracle access to $s$. Specifically, when the latter tester queries the
bit $i$, we use the local reversed self-order algorithm in order to locate the
$i^{\rm th}$ vertex of $G_{n}$ in $G^{\prime}$, and then determine the bit
$s_{i}$ accordingly. Details follow.

Let $V$ denote the set of vertices of the graph $G^{\prime}=([3n],E^{\prime})$
that have degree greater than 2 and neighbor two vertices that have degree at
most 2 and neighbor each other if they have degree 2. Evidently, the vertices
of $V$ are easy to identify by querying $G^{\prime}$ for their neighbors and
their neighbors’ neighbors. Furthermore, $|V|\leq n$, since each vertex in $V$
has two neighbors that are not connected to any other vertex in $V$, and
equality holds in case $G^{\prime}\in\Pi$. We try to find a (“pivot”) vertex
$p\in V$ by picking an arbitrary vertex in $G^{\prime}$ and checking it and
its neighbors. If none of these is in $V$, then we reject. Otherwise, we
continue; we shall be using $p$ as an auxiliary input in all (future)
invocations of the local reversed self-ordering algorithm, denoted $A$.

Using the foregoing algorithm $A$ and the pivot $p\in V$, we define
$A^{\prime}(i)=A(p,i)$ if $A(p,i)\in V$ and invoking the local self-ordering
algorithm on input $A(p,i)$ yields $i$. Otherwise $A^{\prime}(i)$ is
undefined. Hence, evaluating $A^{\prime}$ amounts to evaluating $A$ as well as
evaluating the local self-ordering algorithm. Letting $I^{\prime}\subseteq[n]$
denote the set of “indices” (i.e., vertices of $G_{n}$) on which $A^{\prime}$
is defined, we note that $A^{\prime}$ is a bijection from $I^{\prime}$ to
$V^{\prime}\stackrel{{\scriptstyle\rm
def}}{{=}}\\{A^{\prime}(i)\\!:\\!i\in\\!I^{\prime}\\}$, and that
$I^{\prime}=[n]$ if $G^{\prime}\in\Pi$. Hence, our first test is testing
whether $I^{\prime}=[n]$, which is done by selecting at random $O(1/\epsilon)$
elements of $[n]$, and rejecting if $A^{\prime}$ is undefined on any of them.
Otherwise, we proceed, while assuming that
$|I^{\prime}|\geq(1-0.1\epsilon)\cdot n$.

Next, we test whether the subgraph of $G_{n}$ induced by $I^{\prime}$ is
isomorphic to the subgraph of $G^{\prime}$ induced by $V^{\prime}$, where the
isomorphism is provided by $A^{\prime}$ (which maps $I^{\prime}$ to
$V^{\prime}$). This can be done by sampling $O(1/\epsilon)$ vertices of
$G_{n}$ and comparing their neighbors to the neighbors of the corresponding
vertices in $G^{\prime}$, which are found by $A^{\prime}$. Specifically, for
every sampled vertex $i\in[n]$, we determine its set of neighbors $S_{i}$ in
$G_{n}$, obtain both $A^{\prime}(i)$ and
$A^{\prime}(S_{i})=\\{A^{\prime}(j)\\!:\\!j\\!\in\\!S_{i}\\}$, which are
supposedly the corresponding vertices in $G^{\prime}$, and check whether
$A^{\prime}(S_{i})$ is the set of neighbors of $A^{\prime}(i)$ in
$G^{\prime}$. We reject if $A^{\prime}$ is undefined on any of these vertices
(i.e., on sampled vertices or their neighbors in $G_{n}$). Needless to say, we
also reject if any of the foregoing neighborhood checks fails.

Assuming that we did not reject so far, we may assume that $G^{\prime}$ is
$\epsilon/2$-close to being isomorphic to some $G^{\prime}_{s}$, where the
isomorphism is consistent with the inverse of $A^{\prime}$. At this point, we
invoke the tester for $\Phi$, denoted $T$, in order to test whether
$s\in\Phi$. This is done by providing $T$ with oracle access to $s$ as
follows. When $T$ makes a query $i\in[n]$, we determine $A^{\prime}(i)$, and
use our query access to $G^{\prime}$ in order to determine the two neighbors
of $A^{\prime}(i)$ that have degree at most 2. If this fails, we reject.
Otherwise, we answer 1 if and only if these two neighbors are connected in
$G^{\prime}$.

To summarize, we employ three tests to $G^{\prime}$: An initial test of the
size $I^{\prime}$ (which also includes finding a pivot $p\in V$), an
isomorphism test between the subgraph of $G^{\prime}$ induced by $I^{\prime}$
and the subgraph of $G_{n}$ induced by $V^{\prime}$, and an emulation of the
testing of $\Phi$. (In all tests, if we encounter an index in $[n]\setminus
I^{\prime}$, we suspend the execution and reject.) For simplicity and without
loss of generality, we may assume that $T$ is correct with high (constant)
probability.

Note that if $G^{\prime}\in\Pi$, then it holds that
$G^{\prime}=\pi(G^{\prime}_{s})$ for some $s\in\Phi$ and some permutation
$\pi\in{\rm Sym}_{3n}$. In this case, it holds that $|I^{\prime}|=n$ and we
always find a pivot $p\in V$. Furthermore, $A^{\prime}$ equals the restriction
of $\pi$ to $[n]$, the isomorphism test always succeeds, and the emulation of
oracle access to $s$ is perfect. Hence, we accept with high probability (or
always, if $T$ has one-sided error probability).

On the other hand, suppose that $G^{\prime}$ is $\epsilon$-far from $\Pi$. If
either $|I^{\prime}|<(1-0.1\epsilon)\cdot n$ or the subgraph of $G^{\prime}$
induced by $V^{\prime}$ is $0.1\epsilon$-far from
$A^{\prime}(G_{I^{\prime}})$, where $G_{I^{\prime}}$ denotes the subgraph of
$G_{n}$ induced by $I^{\prime}$, then we reject with high probability due to
one of the first two tests. Otherwise, letting $\pi$ be an arbitrary bijection
of $[3n]$ to $[3n]$ that extends $A^{\prime}$, it follows that for some
$s\in\\{0,1\\}^{n}$ the graph $G^{\prime}$ is $0.2\epsilon$-close to
$\pi(G^{\prime}_{s})$, since we may obtain $\pi(G^{\prime}_{s})$ from
$G^{\prime}$ by modifying the neighborhood of $0.1n$ vertices in $I^{\prime}$
as well as of the vertices in $[n]\setminus I^{\prime}$. Furthermore, for
every $i\in[n]$ on which $A^{\prime}$ is defined, it holds that $s_{i}=1$ if
and only if the two neighbors of $A^{\prime}(i)$ that have degree at most 2
are connected. By the hypothesis regarding $G^{\prime}$, the string $s$ must
be $2.4\epsilon$-far from $\Phi$, and $A^{\prime}(i)=\pi(i)$ whenever
$A^{\prime}$ is defined on $i\in[n]$. It follows that either the emulation of
$T$ was abruptly terminated (leading to rejection) or the answers provided to
$T$ are according to $s$. Hence, we reject with high probability.

###### Separating tolerant testing from testing.

Using Corollary 5.3 and Proposition 5.4, we transport the separation of
tolerant testing from testing, which has been established in [15], from the
domain of testing strings to the domain of testing graph properties in the
bounded-degree graph model.

###### Theorem 5.5

(in the bounded-degree graph model, tolerant testing is harder than testing):
For any sufficiently large constant $d$ and any constant $c\in(0,1)$, there
exists a graph property $\Pi$ such that testing $\Pi$ in the bounded-degree
graph model (with degree bound $d$) has query complexity $O({\rm poly}(\log
n)/\epsilon)$, but tolerantly testing $\Pi$ has query complexity
$\Omega(n^{\Omega(1-c)})$, provided that the tolerance parameter is not
smaller than $n^{-c}$. Furthermore, $\Pi$ is efficiently recognizable.

Proof: A small variant on the proof of [15, Thm. 1.3] yields an efficiently
recognizable set of strings $\Phi$ that is testable in $O(1/\epsilon)$ queries
but tolerantly testing it requires $\Omega(n^{\Omega(1-c)})$
queries.323232Basically, the construction of [15] consists of repeating some
$m$-bit long string ${\rm poly}(m)$ times and augmenting it with a PCP of
Proximity (PCPP) [2, 11] of membership in some polynomial-time recognizable
set that is hard to test. Essentially, the PCPP helps the tester, but it may
be totally useless (when corrupted) in the tolerant testing setting. While
[15] lets the PCPP occupy an $o(1/\log\log n)$ fraction of the final $n$-bit
string, we let it occupy just a $n^{-c}$ fraction (and use
$m=n^{\Omega(1-c)}$). This requires using a different PCPP than the one used
in [15]; e.g., using a strong PCPP with linear detection probability [10, Def.
2.2] will do, and such a PCPP is available [10, Thm. 3.3]. Using Construction
5.2.1 with graphs that are locally self-ordered and locally reversed self-
ordered (as provided by Corollary 4.10), we obtain the desired graph property
$\Pi$. By Corollary 5.3 tolerantly testing $\Pi$ requires
$\Omega(n^{\Omega(1)})$ queries, whereas by Proposition 5.4 (non-tolerant)
testing $\Pi$ has query complexity ${\rm poly}(\log n)\cdot O(1/\epsilon)$.
The claim follows.

###### Digest: Tightly reducing testing properties of strings to testing graph
properties.

In continuation to (the main part of) Corollary 5.3, we highlight the fact
that Construction 5.2.1 not only reduces testing the string property $\Phi$ to
testing the graph property $\Pi$, but rather does so in a rather tight manner.
Specifically, for $\Phi,\Pi$ and $Q_{\Phi},Q_{\Pi}$ as in Corollary 5.3, it
holds that $Q_{\Phi}(n,\epsilon)$ and $Q_{\Pi}(\Theta(n),\Theta(\epsilon))$
agree up to a ${\rm poly}(\log n)$ factor. In other words, for any property of
strings $\Phi$, there exists a property of bounded-degree graphs $\Pi$ such
that the (query and time) complexity of testing $\Phi$ is reflected in the
(query and time) complexity of testing $\Pi$, where our notion of reflection
allows for a polylogarithmic slackness. Recall that the transformation of
strings in $\Phi$ to graphs in $\Pi$ is (strongly/locally) efficient.

###  6 Random Regular Graphs are Robustly Self-Ordered

While Theorem 4.1 only asserts the existence of robustly self-ordered
$d$-regular graphs, we next show that almost all $d$-regular graphs are
robustly self-ordered. This extends work in probabilistic graph theory, which
proves a similar result for the weaker notion of self-ordered (a.k.a
asymmetric) graphs [4, 5].

###### Theorem 6.1

(random $d$-regular graphs are robustly self-ordered): For any sufficiently
large constant $d$, a random $2d$-regular $n$-vertex graph is robustly self-
ordered with probability $1-o(1)$.

Recall that, with very high probability, these graphs are expanders. We
mention that the proof of Theorem 4.1 actually established that $n$-vertex
graphs drawn from a weird distribution (which has min-entropy $\Omega(n)$) are
robustly self-ordered with probability $1-o(1)$. However, this is established
by using the edge-coloring variant, and requires employing the transformation
presented in Section 2.1. In contrast, the following proof works directly with
the original (uncolored) variant, and is completely self-contained.

Proof: The proof is quite similar to the proof Claim 4.1.1, but it faces
complications that were avoided in the prior proof by using edge-colors and
implicitly directed edges. Specifically, for candidate permutations
$\pi_{1},...,\pi_{d}:[n]\to[n]$ (to be used in the construction) and all (non-
trivial) permutations $\mu:[n]\to[n]$, the proof of Claim 4.1.1 considered
events of the form $(\forall
j\\!\in\\![d])\;\pi_{j}(i)=\mu(\pi_{j}({\mu^{-1}}(i)))$, whereas here we shall
consider events of the form
$\\{\pi^{b}_{j}(i):j\\!\in\\![d]\,\&\,b\\!\in\\!\\{\pm
1\\}\\}=\\{\mu(\pi_{j}^{b}({\mu^{-1}}(i))):j\\!\in\\![d]\,\&\,b\\!\in\\!\\{\pm
1\\}\\}$. These multi-set equalities will be reduced to equalities among
sequences by considering all possible ordering of these multi-sets. This
amounts to taking a union bound over all possible ordering and results in a
more complicated analysis (due to the $\pi_{j}^{-1}$’s) and much more
cumbersome notation.

To facilitate the proof, we use the standard methodology (cf. [13, Apdx. 2])
of first proving the result in the random permutation model, then transporting
it to the configuration model (by using a general result of [24]), and finally
conditioning on the event that the generated graph is simple (which occurs
with positive constant probability). Indeed, both models generate multi-graphs
that are not necessarily simple graphs (i.e., these multi-graphs may have
self-loops and parallel edges). We also use the fact that the simple graphs
that are generated by the configuration model (for degree $d^{\prime}$) are
uniformly distributed among all $d^{\prime}$-regular graphs.

Recall that in the random permutation model a $2d$-regular $n$-vertex multi-
graph is generated by selecting uniformly and independently $d$ permutations
$\pi_{1},...,\pi_{d}:[n]\to[n]$. The multi-graph, denoted
$G_{(\pi_{1},...,\pi_{d})}$, consists of the edge multi-set
$\bigcup_{j\in[d]}\\{\\{i,\pi_{j}(i)\\}:i\in[n]\\}$, where the $2j^{\rm th}$
(resp., $(2j-1)^{\rm st}$) neighbor of vertex $i$ is $\pi_{j}(i)$ (resp.,
$\pi_{j}^{-1}(i)$). Note that this multi-graph may have self-loops (due to
$\pi_{j}(i)=i$), which contributed two units to the degree of a vertex, as
well as parallel edges (due to $\pi_{j}(i)=\pi_{k}(i)$ for $j\neq k$ and
$\pi_{j}(i)=\pi_{k}^{-1}(i)$ for any $j,k$). We denote the $j^{\rm th}$
neighbor of vertex $i$ by $g_{j}(i)$; that is, $g_{j}(i)=\pi_{j/2}(i)$ if $j$
is even, and $g_{j}(i)=\pi_{(j+1)/2}^{-1}(i)$ otherwise.

Consider an arbitrary permutation $\mu:[n]\to[n]$, and let
$T=\\{i\\!\in\\![n]\\!:\\!\mu(i)\neq i\\}$ be its set of non-fixed-point. We
shall show that, with probability $1-\exp(-\Omega(d\cdot|T|\cdot\log n))$ over
the choice of ${\overline{\pi}}=(\pi_{1},...,\pi_{d})$, the size of the
symmetric difference between $G_{\overline{\pi}}$ and
$\mu(G_{\overline{\pi}})$ is $\Omega(|T|)$. Note that this difference is
(half) the sum over $i\in[n]$ of the size of the symmetric difference between
the multi-set of neighbors of vertex $i$ in $G_{\overline{\pi}}$ and the
multi-set of neighbors of vertex $i$ in $\mu(G_{\overline{\pi}})$. We refer to
the latter difference by the phrase the contribution of vertex $i$ to the
difference between $G_{\overline{\pi}}$ and $\mu(G_{\overline{\pi}})$.

As a warm-up, we first show that each element of $T$ contributes a non-zero
number of units to the difference (between $G_{\overline{\pi}}$ and
$\mu(G_{\overline{\pi}})$) with probability $1-O({\rm poly}(d)/n)^{d/3}$ over
the choice of $\overline{\pi}$. Consider the event that for some $j,k\in[2d]$,
the $j^{\rm th}$ neighbor of $i\in[n]$ in $\mu(G_{\overline{\pi}})$ is
different from the $k^{\rm th}$ neighbor of $i$ in $G_{\overline{\pi}}$. Note
that $x$ is the $j^{\rm th}$ neighbor of $i$ in $\mu(G_{\overline{\pi}})$ if
and only if ${\mu^{-1}}(x)$ is the $k^{\rm th}$ neighbor of ${\mu^{-1}}(i)$ in
$G_{\overline{\pi}}$, which holds if and only if
${\mu^{-1}}(x)=g_{k}({\mu^{-1}}(i))$ (equiv., $x=\mu(g_{k}({\mu^{-1}}(i)))$).
Recalling that $i\in T$ contributes to the difference (between
$G_{\overline{\pi}}$ and $\mu(G_{\overline{\pi}})$) if the multi-sets of its
neighbors in $G_{\overline{\pi}}$ and $\mu(G_{\overline{\pi}})$ differ, it
follows that $i\in T$ contributes to the difference if and only if for every
permutation $\sigma:[2d]\to[2d]$ there exists $j\in[2d]$ such that
$g_{j}(i)\neq\mu(g_{\sigma(j)}({\mu^{-1}}(i)))$. Thus, the probability of the
complementary event (i.e., $i$ does not contribute to the difference) is given
by

$\displaystyle{\rm Pr}_{\overline{\pi}}\left[\exists\sigma\\!\in\\!{\rm
Sym}_{2d}\;(\forall
j\\!\in\\![2d])\;\;g_{j}(i)=\mu(g_{\sigma(j)}({\mu^{-1}}(i)))\right]$ (11)
$\displaystyle=$ $\displaystyle(2d)!\cdot\max_{\sigma\in{\rm
Sym}_{2d}}\left\\{{\rm Pr}_{\overline{\pi}}\left[(\forall
j\\!\in\\![2d])\;\;g_{j}(i)=\mu(g_{\sigma(j)}({\mu^{-1}}(i)))\right]\right\\}.$

Fixing $\sigma$ that maximizes the probability, and denoting it $\sigma_{i}$,
consider any $J_{i}\subseteq[d]$ such that for the $j$’s in $J_{i}$ the multi-
sets $\\{j,{\lceil\sigma_{i}(2j)/2\rceil}\\}$’s are disjoint (i.e.,
$\\{j,{\lceil\sigma_{i}(2j)/2\rceil}\\}\cap\\{k,{\lceil\sigma_{i}(2k)/2\rceil}\\}=\emptyset$
for any $j\neq k\in J_{i}$). Note that we may select $J_{i}$ such that
$|J_{i}|\geq d/3$, since taking $j$ to $J_{i}$ only rules out taking (to
$J_{i}$) any $k$ such that
${\lceil\sigma_{i}(2k)/2\rceil}=v\stackrel{{\scriptstyle\rm
def}}{{=}}{\lceil\sigma_{i}(2j)/2\rceil}$ (equiv., $k$ such that
$\sigma_{i}(2k)\in\\{2v-1,2v\\}$). Using this proerty of $J_{i}$, we prove –

###### Claim 6.1.1

(warm-up):333333One may obtain a better bound of $O(d/n)^{2d}$ by analyzing
Eq. (11) directly, by considering all the $2d$ events and accounting for their
small dependency. On the other hand, we can obtain higher robustness parameter
by considering smaller sets $J_{i}$’s (say of size $d/4$), which suffice for
counting vertices that contribute (say) $d/4$ units to the difference between
$G_{\overline{\pi}}$ and $\mu(G_{\overline{\pi}})$. Eq. (11) is upper-bounded
by $(2d)^{2d}\cdot(2/n)^{|J_{i}|}$.

Proof: We upper-bound Eq. (11) by

$\displaystyle(2d)!\cdot\max_{\sigma}\left\\{{\rm
Pr}_{\overline{\pi}}\left[(\forall
j\\!\in\\!J_{i})\;\;g_{2j}(i)=\mu(g_{\sigma(2j)}({\mu^{-1}}(i)))\right]\right\\}$
(12) $\displaystyle=$ $\displaystyle(2d)!\cdot\prod_{j\in J_{i}}{\rm
Pr}_{\pi_{j},\pi_{{\lceil\sigma_{i}(2j)/2\rceil}}}\left[g_{2j}(i)=\mu(g_{\sigma_{i}(2j)}({\mu^{-1}}(i)))\right]$

where the equality uses the disjointness of the multi-sets
$\\{j,{\lceil\sigma_{i}(2j)/2\rceil}\\}$ for the $j$’s in $J_{i}$. Next, we
upper-bound Eq. (12) by

$(2d)!\cdot\prod_{j\in J_{i}}{\rm
Pr}_{\pi_{j},\pi_{{\lceil\sigma_{i}(2j)/2\rceil}}}\left[\pi_{j}(i)=\mu(\pi^{(-1)^{\sigma_{i}(2j)\bmod
2}}_{{\lceil\sigma_{i}(2j)/2\rceil}}({\mu^{-1}}(i)))\right]\;<\;(2d)^{2d}\cdot(2/n)^{|J_{i}|},$
(13)

where ${\rm Pr}_{\pi_{j},\pi_{j}}[\cdot]$ stands for ${\rm
Pr}_{\pi_{j}}[\cdot]$ and $\pi^{1}$ stands for $\pi$, while the inequality is
justified by considering the following three cases (w.r.t each $j\in J_{i}$).

  1. 1.

If $k\stackrel{{\scriptstyle\rm def}}{{=}}{\lceil\sigma_{i}(2j)/2\rceil}\neq
j$, then, letting $b=(-1)^{\sigma_{i}(2j)\bmod 2}$, the corresponding factor
in the l.h.s of Eq. (13) is

${\rm
Pr}_{\pi_{j},\pi_{k}}\left[\pi_{j}(i)=\mu(\pi^{b}_{k}({\mu^{-1}}(i)))\right]$

which equals $1/n$ by fixing $\pi_{k}$, letting
$v=\mu(\pi^{b}_{k}({\mu^{-1}}(i)))$, and using ${\rm
Pr}_{\pi_{j}}[\pi_{j}(i)\\!=\\!v]=1/n$.

  2. 2.

If $\sigma_{i}(2j)=2j$, then the corresponding factor in the l.h.s of Eq. (13)
is

${\rm Pr}_{\pi_{j}}\left[\pi_{j}(i)=\mu(\pi_{j}({\mu^{-1}}(i)))\right]$

which is at most $1/(n-1)$ since $\mu(i)\neq i$; specifically, fixing the
value of $\pi_{j}({\mu^{-1}}(i))$, and denoting this value by $v$, leaves
$\pi_{j}(i)$ uniformly distributed in $[n]\setminus\\{v\\}$, which means that
${\rm Pr}_{\pi_{j}}[\pi_{j}(i)\\!=\\!\mu(v)|v=\pi_{j}({\mu^{-1}}(i))]\leq
1/(n-1)$ (where equality holds if $\mu(v)\neq v$).

  3. 3.

If $\sigma_{i}(2j)=2j-1$, then the corresponding factor in the l.h.s of Eq.
(13) is

${\rm Pr}_{\pi_{j}}\left[\pi_{j}(i)=\mu(\pi_{j}^{-1}({\mu^{-1}}(i)))\right]$

which is less than $2/n$. In this case, we consider two sub-cases depending on
whether or not $\pi_{j}(i)={\mu^{-1}}(i)$, while noting that the first case
occurs with probability $1/n$ whereas ${\rm
Pr}_{\pi_{j}}[\pi_{j}(i)=\mu(\pi_{j}^{-1}({\mu^{-1}}(i)))|\pi_{j}(i)\neq{\mu^{-1}}(i)]\leq
1/(n-1)$.

Hence, each of the factors in the l.h.s of Eq. (13) is upper-bounded by $2/n$,
and the claim follows.

The general case. The same argument generalizes to a set $I\subseteq T$ such
that $I\cap\mu(I)=\emptyset$. In such a case we get

$\displaystyle{\rm Pr}_{\overline{\pi}}\left[(\forall
i\\!\in\\!I)\,(\exists\sigma_{i}\\!\in\\!{\rm Sym}_{2d})\,(\forall
j\\!\in\\![2d])\;\;g_{j}(i)=\mu(g_{\sigma_{i}(j)}({\mu^{-1}}(i)))\right]$ (14)
$\displaystyle=$
$\displaystyle(2d)!^{|I|}\cdot\max_{\sigma_{1},...,\sigma_{n}}\left\\{{\rm
Pr}_{\overline{\pi}}\left[(\forall i\\!\in\\!I)\,(\forall
j\\!\in\\![2d])\;\;g_{j}(i)=\mu(g_{\sigma_{i}(j)}({\mu^{-1}}(i)))\right]\right\\}$

###### Claim 6.1.2

(actual analysis): Eq. (14) is upper-bounded by

$(2d)^{2d\cdot|I|}\cdot(2/(n-2(|I|-1)))^{|I|\cdot d/3}.$ (15)

Proof: For every $i\in I=\\{i_{1},...,i_{m}\\}$, we fixed a set $J_{i}$ of
size at least $d/3$ such that the multi-sets
$\\{j,{\lceil\sigma_{i}(2j)/2\rceil}\\}$’s are disjoint, and upper-bound Eq.
(14) by

$\displaystyle(2d)!^{m}\cdot\prod_{k\in[m]~{}}\prod_{~{}j\in J_{i_{k}}}{\rm
Pr}_{\pi_{1},...,\pi_{2d}}\left[g_{2j}(i_{k})=\mu(g_{\sigma_{i_{k}}\\!(2j)}({\mu^{-1}}(i_{k})))\left|E_{j,k}(\pi_{1},....,\pi_{2d})\right.\right]$
(16) $\displaystyle=$
$\displaystyle(2d)!^{m}\cdot\prod_{k\in[m]~{}}\prod_{~{}j\in J_{i_{k}}}{\rm
Pr}_{\pi_{1},...,\pi_{2d}}\left[\pi_{j}(i_{k})=\mu(\pi^{\sigma^{\prime\prime}_{i_{k}}\\!(2j)}_{\sigma^{\prime}_{i_{k}}\\!(2j)}({\mu^{-1}}(i_{k})))\left|E_{j,k}(\pi_{1},....,\pi_{2d})\right.\right]$

where $\sigma^{\prime}_{i}(2j)\stackrel{{\scriptstyle\rm
def}}{{=}}{{\lceil\sigma_{i}(2j)/2\rceil}}$, and
$\sigma^{\prime\prime}_{i}(2j)\stackrel{{\scriptstyle\rm
def}}{{=}}(-1)^{\sigma_{i}(2j)\bmod 2}$, whereas
$E_{j,k}(\pi_{1},...,\pi_{2d})$ is an event that depends only on the value of
$\pi_{j}$ and
$\pi^{\sigma^{\prime\prime}_{i_{k}}\\!(2j)}_{\sigma^{\prime}_{i_{k}}\\!(2j)}$
on the points $i_{1},...,i_{k-1}$ and
${\mu^{-1}}(i_{1}),...,{\mu^{-1}}(i_{k-1})$, respectively. Specifically,
$E_{j,k}(\pi_{1},...,\pi_{2d})$ is the event

$(\forall
k^{\prime}\\!\in\\![k-1])\;\;g_{2j}(i_{k^{\prime}})=\mu(g_{\sigma_{i_{k^{\prime}}}\\!(2j)}({\mu^{-1}}(i_{k^{\prime}})))$

which can be written as

$(\forall
k^{\prime}\\!\in\\![k-1])\;\;\pi_{j}(i_{k^{\prime}})=\mu(\pi^{\sigma^{\prime\prime}_{i_{k^{\prime}}}\\!(2j)}_{\sigma^{\prime}_{i_{k^{\prime}}}\\!(2j)}({\mu^{-1}}(i_{k^{\prime}}))).$

Now, when analyzing the foregoing conditional probability in Eq. (16), we
consider two cases. If $j\neq\sigma^{\prime}_{i_{k}}\\!(2j)$, then we fix the
value of each of these two permutations (i.e., $\pi_{j}$ and
$\pi_{\sigma^{\prime}_{i_{k}}\\!(2j)}$) on the corresponding $k-1$ points that
occur in the condition $E_{j,k}$, and the value of these permutations on the
$k^{\rm th}$ points (i.e., $i_{k}$ and ${\mu^{-1}}(i_{k})$) is restricted
accordingly (i.e., to the remaining $n-(k-1)$ values). Otherwise (i.e.,
$j=\sigma^{\prime}_{i_{k}}\\!(2j)$), we fix the value of $\pi_{j}$ on these
$2(k-1)$ points. Hence, the argument in the warm-up analysis applies with $n$
replaces by either $n-(k-1)$ or $n-2(k-1)$. It follows that Eq. (16) is upper-
bounded by

$(2d)!^{m}\cdot\prod_{k\in[m]~{}}(2/(2-2(m-1)))^{|J_{i_{k}}|}.$

Using $|J_{i_{k}}|\geq d/3$ for every $k\in[m]$, the claim follows.

Recall that Eq. (15) refers to a fixed set $I\subseteq T$ such that
$I\cap\mu(I)=\emptyset$, and that it constitutes an upper bound on the
probability (over the choice of $\overline{\pi}$) that, for each $i\in I$
there exists a permutation $\sigma_{i}:[2d]\to[2d]$ such that
$g_{j}(i)=\mu(g_{\sigma_{i}(j)}({\mu^{-1}}(i)))$ holds for all $j\in[2d]$.
This upper bound (i.e., $(2d)^{2d\cdot|I|}\cdot(2/(n-2(|I|-1)))^{|I|\cdot
d/3}$) simplifies to $(2d)^{2d\cdot|I|}\cdot(6/n)^{|I|\cdot d/3}$, provided
that $|I|\leq n/3$.

Recalling that $t\stackrel{{\scriptstyle\rm def}}{{=}}|T|\in[n]$, we shall
upper-bound the probability (over the choice of $\overline{\pi}$) that $T$
contains a ${\lceil t/2\rceil}$-subset $T^{\prime}$ such that for each $i\in
T^{\prime}$ there exists a permutation $\sigma_{i}:[2d]\to[2d]$ such that
$g_{j}(i)=\mu(g_{\sigma_{i}(j)}({\mu^{-1}}(i)))$ holds for all $j\in[2d]$. We
do so by taking a union bound over all ${\lceil t/6\rceil}$-subsets $I$ such
that $I\cap\mu(I)=\emptyset$ and for each $i\in I$ there exists a permutation
$\sigma_{i}:[2d]\to[2d]$ such that
$g_{j}(i)=\mu(g_{\sigma_{i}(j)}({\mu^{-1}}(i)))$ holds for all $j\in[2d]$.
(Note that such a ${\lceil t/6\rceil}$-subset $I$ exists in each ${\lceil
t/2\rceil}$-subset $T^{\prime}$, and that ${\lceil t/6\rceil}<n/3$.) Using the
aforementioned simplified form of Eq. (15), we conclude that, with probability
at most

${t\choose{{\lceil t/6\rceil}}}\cdot(2d)^{2d\cdot{\lceil
t/6\rceil}}\cdot(6/n)^{{\lceil
t/6\rceil}\cdot{d/3}}\;<\;2^{t}\cdot(6\cdot(2d)^{6}/n)^{{\lceil
t/6\rceil}\cdot d/3}\;=\;\exp(-\Omega(dt\log n))$

over the choice of $\overline{\pi}$, the set $T$ contains no ${\lceil
t/6\rceil}$-subset $I$ as above. This means that, with probability at most
$\exp(-\Omega(dt\log n))$, less than ${t/2}$ of the indices $i\in T$
contribute a non-zero number of units to the difference (between
$G_{\overline{\pi}}$ and $\mu(G_{\overline{\pi}})$).

Letting $c^{\prime}=1/2$ and considering all (non-trivial) permutations
$\mu:[n]\to[n]$, we conclude that the probability, over the choice of
$\overline{\pi}$, that $G_{\overline{\pi}}$ is not $c^{\prime}$-robustly self-
ordered is at most

$\displaystyle\sum_{t\in[n]}{{n}\choose t}\cdot\exp(-\Omega(dt\log n))$
$\displaystyle=$ $\displaystyle\sum_{t\in[n]}\exp(-\Omega((d-O(1))\cdot t\log
n))$ $\displaystyle=$ $\displaystyle\exp(-\Omega((d-O(1))\cdot\log n)),$

and the claim follows for the permutation model (and for any sufficiently
large $d$).

As stated upfront, using the general result of [24, Thm. 1.3], we infer that a
uniformly distributed $2d$-regular $n$-vertex multi-graph fails to be
$c^{\prime}$-robustly self-ordered with probability $o(1)$. Lastly, recalling
that such a $2d$-regular multi-graph is actually a simple graph with
probability $\exp(-((2d)^{2}-1)/4)$, the theorem follows.

###### Digest.

The proof of Theorem 6.1 is quite similar to the proof Claim 4.1.1, but it
faces two complications that were avoided in the prior proof (by using edge-
colors and implicitly directed edges). Most importantly, the current proof has
to handle equality between multi-sets instead of equality between sequences.
This is done by considering all possible ordering of these multi-sets, which
amounts to taking a union bound over all possible ordering and results in more
complicated analysis and notation. (Specifically, see the introduction of
$\sigma_{i}$’s and $J_{i}$’s and the three cases analyzed in the warm-up.) In
addition, since edges are defined by permutations over the vertex-set rather
than by perfect matching, we have to consider both the forward and backward
direction of each permutation, which results in further complicating the
analysis and the notation. (Specifically, see the introduction of
$\sigma^{\prime}_{i}$’s and $\sigma^{\prime\prime}_{i}$’s and the three cases
analyzed in the warm-up.)

###### An alternative proof of Theorem 4.2.

We mention that combining an extension of Theorem 6.1 with some of the ideas
underlying the proof of Theorem 4.2 yields an alternative proof of Theorem 4.2
(i.e., an alternative construction of robustly self-ordered bounded-degree
graphs).

###### Remark 6.2

(an alternative construction of $d$-regular robustly self-ordered graphs): On
input $1^{n}$, we set $\ell=\frac{O(\log n)}{\log\log n}$, and proceeds in
three steps.

  1. 1.

Extending the proof of Theorem 6.1, we show that for all sufficiently large
constant $d$, for any set $\cal G$ of $t=t(\ell)<n=\ell^{\Omega(\ell)}$
($2d$-regular) $\ell$-vertex graphs, with probability $1-o(1)$, a random
$2d$-regular $\ell$-vertex graph is both robustly self-ordered and far from
being isomorphic to any graph in $\cal G$. Note that, with probability
$1-o(1)$, such a graph is also expanding.

Here two $\ell$-vertex graphs are said to be far apart if they disagree on
$\Omega(\ell)$ vertex-pairs.

The proof of Theorem 6.1 is extended by considering, for a random graph, the
event that it is either not robustly self-ordered or is not far from an
isomorphic copy of one of the $t$ (fixed) graphs. The later event (i.e., being
close to isomorphic to one of these graphs) occurs with probability $o(t/n)$.

  2. 2.

Relying on Step 1, we find a sequence of $n/\ell$ robustly self-ordered
$2d$-regular $\ell$-vertex graphs that are expanding and pairwise far from
being isomorphic to one another.

This is done by iteratively finding robustly self-ordered $2d$-regular
$\ell$-vertex expanding graphs that are far from being isomorphic to all prior
ones, where scanning all possible graphs and checking the condition can be
done in time $n\cdot\ell^{d\ell/2}\cdot(\ell!)={\rm poly}(n)$.

  3. 3.

Using the sequence of $n/\ell$ graphs found in Step 2, we consider the
$n$-vertex graph that consists of these $\ell$-vertex graphs as its connected
components, and use parts of the proof of Theorem 4.2 to show that this graph
is robustly self-ordered. Specifically, we only need to consider cases that
are analogous to Cases 2, 6 and 7. The treatment of the analogous cases is
slightly simpler than in the proof of Theorem 4.2, since the graphs are
somewhat simpler.

Note that the resulting graphs are not locally constructable.

##  Part II The Case of Dense Graphs

Recall that when considering graphs of unbounded degree, we ask whether we can
obtain unbounded robustness parameters. In particular, we are interested in
$n$-vertex graphs that are $\Omega(n)$-robustly self-ordered, which means that
they must have $\Omega(n^{2})$ edges.

In Section 7 we prove the existence of $\Omega(n)$-robustly self-ordered
$n$-vertex graphs, and show that they imply $\Omega(1)$-robustly self-ordered
bounded-degree $O(n^{2})$-vertex graphs. In Section 8, we reduce the
construction of the former (dense) $n$-vertex graphs to the construction of
non-malleable two-source extractors (with very mild parameters). We actually
show two reductions: The first reduction (presented in Section 8.1) requires
the extractors to have an additional natural feature, called quasi-
orthogonality, and yields a construction of such $n$-vertex graphs that runs
in ${\rm poly}(n)$-time. The second reduction (presented in Section 8.2) does
not make this requirement, and yields an algorithm that computes the adjacency
predicate of such $n$-vertex graphs in ${\rm poly}(\log n)$-time.

In Section 9 we demonstrate the applicability of $\Omega(n)$-robustly self-
ordered $n$-vertex graphs to property testing; specifically, to proving lower
bounds (on the query complexity) for the dense graph testing model. Lastly, in
Section 10, we consider the construction of $\Omega(d(n))$-robustly self-
ordered $n$-vertex graphs of maximum degree $d(n)$, for every
$d:\mathbb{N}\to\mathbb{N}$ such that $d(n)\in[\Omega(1),n]$.

###  7 Existence and Transformation to Bounded-Degree Graphs

It seems easier to prove that random $n$-vertex graphs are
$\Omega(n)$-robustly self-ordered (see Proposition 7.1) than to prove that
random bounded-degree graphs are $\Omega(1)$-robustly self-ordered (or even
just prove that such bounded-degree graphs exist). In contrast, it seems
harder to construct $\Omega(n)$-robustly self-ordered $n$-vertex graphs than
to construct $\Omega(1)$-robustly self-ordered bounded-degree graphs. In
particular, we show that $\Omega(n)$-robustly self-ordered $n$-vertex graphs
can be easily transformed into $O(n^{2})$-vertex bounded-degree graphs that
are $\Omega(1)$-robustly self-ordered (see Proposition 7.2). We stress that
the construction of robustly self-ordered bounded-degree graphs that is
obtained by combining the foregoing transformation with Theorem 1.4 is
entirely different from the constructions presented in the first part of the
paper.

###### Random graphs are robustly self-ordered.

We first show that, with very high probability, a random $n$-vertex graph
$G_{n}=([n],E_{n})$, where $E_{n}$ is a uniformly distributed subset of
${[n]}\choose 2$, is $\Omega(n)$-robustly self-ordered.

###### Proposition 7.1

(robustness analysis of a random graph): A random $n$-vertex graph
$G_{n}=([n],E_{n})$ is $\Omega(n)$-robustly self-ordered with probability
$1-\exp(-\Omega(n))$.

As stated above, the following proof is significantly easier than the proof
provided for the bounded-degree analogue (i.e., Theorem 6.1).

Proof: For each (non-trivial) permutation $\mu:[n]\to[n]$, letting
$T\stackrel{{\scriptstyle\rm def}}{{=}}\\{i\\!\in\\![n]\\!:\\!\mu(i)\neq i\\}$
denote its (non-empty) set of non-fixed-points, we show that, with probability
$1-\exp(-\Omega(n\cdot|T|))$, the size of the symmetric different between a
random $n$-vertex graph $G_{n}=([n],E_{n})$ and $\mu(G_{n})$ is
$\Omega(n\cdot|T|)$.

For every $u,v\in[n]$ such that $u<v$, let
$\chi_{u,v}=\chi_{u,v}^{\mu}(G_{n})$ represent the event that the pair
$(\mu(u),\mu(v))$ contributes to the symmetric difference between $G_{n}$ and
$\mu(G_{n})$; that is, $\chi_{u,v}=1$ if exactly one of the edges
$\\{\mu(u),\mu(v)\\}$ and $\\{u,v\\}$ is in $G_{n}$, since $\\{u,v\\}$ is an
edge of $G_{n}$ if and only if $\\{\mu(u),\mu(v)\\}$ is an edge of
$\mu(G_{n})$. We shall prove that

${\rm
Pr}_{G_{n}}\left[\sum_{u<v\in[n]}\chi_{u,v}^{\mu}(G_{n})\,<\,\frac{n\cdot|T|}{20}\right]\;=\;\exp(-\Omega(n\cdot|T|)).$
(17)

We prove Eq. (17) by using a ${\lceil|T|/3\rceil}$-subset $I\subseteq T$ such
that $I\cap\mu(I)=\emptyset$. Let $T^{\prime}=T\setminus(I\cup{\mu^{-1}}(I))$,
which implies $T^{\prime}\cap I=\emptyset$ and $\mu(T^{\prime})\cap
I=\emptyset$. Let $J=([n]\setminus T)\cup T^{\prime}$, and note that
$|J|=n-|T|+(|T|-2\cdot{\lceil|T|/3\rceil})\geq n-(2|T|/3)-2\geq(n/3)-2$.
Observe that, for every $(u,v)\in J\times I$, it holds that $u\neq v$ and
${\rm Pr}[\chi_{u,v}\\!=\\!1]\,=\,1/2$, where the equality is due to
$\\{u,v\\}\neq\\{\mu(u),\mu(v)\\}$, which holds since $(u,v)\\!\in\\!J\times
I$ but $\mu(u),\mu(v)\in[n]\setminus I$. Furthermore, the events the
correspond to the pairs in $J\times I$ are independent, because the sets
$\\{\\{u,v\\}\\!:\\!(u,v)\\!\in\\!J\times I\\}$ and
$\\{\\{\mu(u),\mu(v)\\}\\!:\\!(u,v)\\!\in\\!J\times I\\}$ are disjoint; that
is, $(u,v)\in J\times I$ implies $(\mu(u),\mu(v))\in([n]\setminus
I)\times([n]\setminus I)$. Hence (using $n\leq 3(|J|+2)$ and $|T|\leq 3|I|$
(as well as $3(|J|+2)\cdot 3|I|<9.9\cdot|J|\cdot|I|$)), the l.h.s. of Eq. (17)
is upper-bounded by

$\displaystyle{\rm Pr}_{G_{n}}\left[\sum_{(u,v)\in J\times
I}\chi_{u,v}^{\mu}(G_{n})\,<\,\frac{3(|J|+2)\cdot 3|I|}{20}\right]$
$\displaystyle\leq$ $\displaystyle{\rm Pr}_{G_{n}}\left[\sum_{(u,v)\in J\times
I}\chi_{u,v}^{\mu}(G_{n})\,<\,\frac{0.99\cdot|J|\cdot|I|}{2}\right]$
$\displaystyle=$ $\displaystyle\exp(-\Omega(|J|\cdot|I|))$

which is $\exp(-\Omega(n\cdot|T|))$. Having established Eq. (17), the claim
follows by a union bound (over all non-trivial permutations $\mu:[n]\to[n]$);
specifically, denoting the set of non-trivial permutations by $P_{n}$, we
upper-bound the probability that $G_{n}$ is not $\frac{n}{20}$-robust by

$\displaystyle\sum_{\mu\in P_{n}}\hbox to0.0pt{$\displaystyle{\rm
Pr}_{G_{n}}\left[\mbox{\rm$\mu$ violates the condition in {\rm
Eq.~{}(\ref{T-claim:eq})}}\right]$\hss}$ $\displaystyle\leq$
$\displaystyle\sum_{t\in[n]}{n\choose t}\cdot(t!)\cdot\exp(-\Omega(n\cdot t))$
$\displaystyle<$ $\displaystyle
n\cdot\max_{t\in[n]}\\{n^{t}\cdot\exp(-\Omega(n\cdot t))\\}$ $\displaystyle=$
$\displaystyle\exp(-\Omega(n))$

where $t$ represents the size of the set of non-fixed-points (w.r.t $\mu$).

###### Obtaining bounded-degree robustly self-ordered graphs.

We next show how to transform $\Omega(n)$-robustly self-ordered $n$-vertex
graphs to $O(n^{2})$-vertex bounded-degree graphs that are
$\Omega(1)$-robustly self-ordered. Essentially, we show that the standard
“degree reduction via expanders” technique works (when using a different color
for the expanders’ edges, and then using gadgets to replace colored edges).
Specifically, we replace each vertex in $G_{n}=([n],E_{n})$ by an
$(n-1)$-vertex expander graph and connect each of these vertices to at most
one vertex in a different expander, while coloring the edges of the expanders
with 1, and coloring the other edges by 2. Actually, the vertex $v$ is
replaced by the vertex-set
$C_{v}=\\{{\langle{v,u}\rangle}:u\\!\in\\![n]\setminus\\{v\\}\\}$ and in
addition to the edges of the expander, colored 1, we connect each vertex
${\langle{v,u}\rangle}\in C_{v}$ to the vertex ${\langle{u,v}\rangle}\in
C_{u}$ and color this edge 2 if $\\{u,v\\}\in E_{n}$ and 0
otherwise.343434This is equivalent to first converting $G_{n}$ into a
$n$-vertex clique while coloring an edge 2 if and only if it is in $E_{n}$.
This yields an $n\cdot(n-1)$-vertex $O(1)$-regular graph, denoted
$G^{\prime}_{n}$, coupled with an edge-coloring, denoted $\chi^{\prime}$,
which uses three colors. Using the hypothesis that $G_{n}$ is
$\Omega(n)$-robustly self-ordered, we prove that
$(G^{\prime}_{n},\chi^{\prime})$ is $\Omega(1)$-robustly self-ordered (in the
colored sense).

###### Proposition 7.2

(robustness analysis of the degree reduction): If $G_{n}$ is
$\Omega(n)$-robustly self-ordered, then $(G^{\prime}_{n},\chi^{\prime})$ is
$\Omega(1)$-robustly self-ordered (in the colored sense of Definition 2.1).

Using Theorem 2.4 (after adding self-loops), we obtain a $O(1)$-regular
$O(n^{2})$-vertex graph that is $\Omega(1)$-robustly self-ordered (in the
standard sense).

Proof: Denoting the vertex-set of $G^{\prime}_{n}$ by
$V=\bigcup_{v\in[n]}C_{v}$, we consider an arbitrary (non-trivial) permutation
$\mu^{\prime}:V\to V$, and the corresponding set of non-fixed-points
$T^{\prime}$. Intuitively, if $\mu^{\prime}$ maps vertices of $C_{v}$ to
several $C_{w}$’s, then we get a proportional contribution to the difference
between $G^{\prime}_{n}$ and $\mu^{\prime}(G^{\prime}_{n})$ by the (1-colored)
edges of the expander. Otherwise, $\mu^{\prime}$ induces a permutation $\mu$
over the vertices of $G_{n}$, and we get a corresponding contribution via the
(2-colored) edges of $G_{n}$. Lastly, non-identity mapping inside the
individual $C_{v}$’s are charged using the (0-colored and 2-colored) edges
that connect different $C_{v}$’s. Details follow.

For a permutation $\mu^{\prime}:V\to V$ as above, let $\mu:[n]\to[n]$ be a
permutation that maximizes the (average over $v\in[n]$ of the) number of
vertices in $C_{v}$ that are mapped by $\mu^{\prime}$ to vertices in
$C_{\mu(v)}$; that is, for every permutation $\nu:[n]\to[n]$, it holds that

$\left|\left\\{{\langle{v,u}\rangle}\\!\in\\!V:\mu^{\prime}({\langle{v,u}\rangle})\in
C_{\mu(v)}\right\\}\right|\;\geq\;\left|\left\\{{\langle{v,u}\rangle}\\!\in\\!V:\mu^{\prime}({\langle{v,u}\rangle})\in
C_{\nu(v)}\right\\}\right|.$ (18)

We consider the following three cases.

Case 1:

$\sum_{v\in[n]}|B_{v}|=\Omega(|T^{\prime}|)$, where
$B_{v}\stackrel{{\scriptstyle\rm
def}}{{=}}\\{{\langle{v,u}\rangle}\\!\in\\!C_{v}:\mu^{\prime}({\langle{v,u}\rangle})\not\in
C_{\mu(v)}\\}$.

(This refers to the case that many vertices are mapped by $\mu^{\prime}$ to an
expander that is different from the one designated by $\mu$, which represents
the best possible mapping of whole expanders.)

Letting $C_{v,w}\stackrel{{\scriptstyle\rm
def}}{{=}}\\{{\langle{v,u}\rangle}:\mu^{\prime}({\langle{v,u}\rangle})\in
C_{w}\\}$, we first observe that for every $v$ it holds that
$\max_{w\neq\mu(v)}\\{|C_{v,w}|\\}\leq\frac{2}{3}\cdot(n-1)$, because
otherwise we reach a contradiction to the maximality of $\mu$ by defining
$\nu(v)=w$ and $\nu({\mu^{-1}}(w))=\mu(v)$, where $w$ is the element obtaining
the maximum, and $\nu(x)=\mu(x)$ otherwise.

Next, observe that there exists $W_{v}\subseteq[n]\setminus\\{\mu(v)\\}$ such
that $B^{\prime}_{v}=\bigcup_{w\in W_{v}}C_{v,w}$ satisfies both
$|B^{\prime}_{v}|\leq\frac{2}{3}\cdot(n-1)$ and
$|B^{\prime}_{v}|\geq|B_{v}|/3$. Now, consider the sets $B^{\prime}_{v}$ and
$C_{v}\setminus B^{\prime}_{v}$: On the one hand, in
$\mu^{\prime}(G^{\prime}_{n})$ there are $\Omega(|B^{\prime}_{v}|)$ 1-colored
edges connecting $\mu^{\prime}(B^{\prime}_{v})$ and
$\mu^{\prime}(C_{v}\setminus B^{\prime}_{v})$, due to the subgraph of
$\mu^{\prime}(G^{\prime}_{n})$ induced by $\mu^{\prime}(C_{v})$ which equals
subgraph of $G^{\prime}_{n}$ induced by $C_{v}$ (which, in turn, is an
expander). On the other hand, in $G^{\prime}_{n}$ there are no 1-colored edges
between $\mu^{\prime}(B^{\prime}_{v})$ and $\mu^{\prime}(C_{v}\setminus
B^{\prime}_{v})$, since $\mu^{\prime}(B^{\prime}_{v})\subseteq\bigcup_{w\in
W_{v}}C_{w}$ and $\mu^{\prime}(C_{v}\setminus
B^{\prime}_{v})\subseteq\bigcup_{w\in[n]\setminus W_{v}}C_{w}$.

We conclude that, in this case, the difference between $G^{\prime}_{n}$ and
$\mu^{\prime}(G_{n})$ is
$\sum_{v}\Omega(|B^{\prime}_{v}|)=\sum_{v}\Omega(|B_{v}|)=\Omega(|T^{\prime}|)$.

Case 2:

$\sum_{v\in[n]:\mu(v)\neq v}|C^{\prime}_{v}|=\Omega(|T^{\prime}|)$, where
$C^{\prime}_{v}\stackrel{{\scriptstyle\rm
def}}{{=}}\\{{\langle{v,u}\rangle}\\!\in\\!C_{v}:\mu^{\prime}({\langle{v,u}\rangle})\in
C_{\mu(v)}\\}$.

(This refers to the case that many vertices are mapped by $\mu^{\prime}$ to an
expander that is designated by $\mu$, but this expander is not the one in
which they reside (i.e., $\mu$ has many non-fixed-points).)

Letting $\gamma>0$ be a constant such that $G_{n}$ is $\gamma\cdot n$-robustly
self-ordered, we may assume that $\sum_{v\in[n]:\mu(v)\neq
v}|C^{\prime}_{v}|\geq(1-0.5\cdot\gamma)\cdot\sum_{v\in[n]:\mu(v)\neq
v}|C_{v}|$, since otherwise we are done by Case 1.

By the $\gamma n$-robust self-ordering of $G_{n}$, the difference between
$G_{n}$ and $\mu(G_{n})$ is at least $\Delta\stackrel{{\scriptstyle\rm
def}}{{=}}\gamma n\cdot|\\{v\in[n]:\mu(v)\neq v\\}|$. Assuming, for a moment,
that $\mu^{\prime}(C_{v})=C_{v}$ for every $v$ such that $\mu(v)\neq v$, the
difference between $G^{\prime}_{n}$ and $\mu^{\prime}(G^{\prime}_{n})$ is
$\Delta$, where the difference is due to edges colored 2 (i.e., the edges
inherited from $G_{n}$). This amount is prorotional to the number of vertices
in the current case, since

$\Delta\;=\;\frac{\gamma n}{n-1}\cdot\sum_{v:\mu(v)\neq
v}|C_{v}|\;>\;\gamma\cdot\sum_{v:\mu(v)\neq v}|C_{v}|.$

In general, $\mu^{\prime}(C_{v})=C_{v}$ may not hold for some $v$, and in this
case we may loss the contribution of the 2-colored edges incident at vertices
in $\bigcup_{v\in[n]:\mu(v)\neq v}(C_{v}\setminus C^{\prime}_{v})$. Recalling
that (by our hypothesis) the size of this set is at most
$0.5\cdot\gamma\cdot\sum_{v:\mu(v)\neq v}|C_{v}|$, we are left with a
contribution of at least $0.5\gamma\cdot\sum_{v:\mu(v)\neq
v}|C^{\prime}_{v}|$.

We conclude that, in this case, the difference between $G^{\prime}_{n}$ and
$\mu^{\prime}(G_{n})$ is $\Omega(\sum_{v:\mu(v)\neq
v}|C^{\prime}_{v}|)=\Omega(|T^{\prime}|)$.

Case 3:

$\sum_{v\in[n]}|C^{\prime\prime}_{v}|=\Omega(|T^{\prime}|)$, where
$C^{\prime\prime}_{v}\stackrel{{\scriptstyle\rm
def}}{{=}}\\{{\langle{v,u}\rangle}\\!\in\\!C_{v}:\mu^{\prime}({\langle{v,u}\rangle})\in
C_{v}\setminus\\{{\langle{v,u}\rangle}\\}\\}$.

(This refers to the case that many vertices are mapped by $\mu^{\prime}$ to a
different vertex in the same expander in which they reside.)353535Note that if
${\langle{v,u}\rangle}\in C_{v}$ is not mapped by $\mu^{\prime}$ to $C_{v}$,
then either $\mu^{\prime}({\langle{v,u}\rangle})\not\in C_{\mu(v)}$ holds
(i.e., Case 1) or $\mu^{\prime}({\langle{v,u}\rangle})\in C_{\mu(v)}$ such
that $\mu(v)\neq v$ (i.e., Case 2). Hence, if ${\langle{u,v}\rangle}\in
T^{\prime}$ is not counted in Cases 1 and 2, then it must be counted in Case
3.

(This case would have been easy to handle if the expanders used on the
$C_{v}$’s were robustly self-ordered. Needless to say, we want to avoid such
an assumption. Instead, we rely on the fact that in $G^{\prime}_{n}$ different
vertices in $C_{v}$ are connected to different $C_{u}$’s.)

We may assume that $\sum_{v\in[n]}|C^{\prime\prime}_{v}|\geq
2\cdot\sum_{v\in[n]}|\\{{\langle{v,u}\rangle}\\!\in\\!C_{v}:\mu^{\prime}({\langle{v,u}\rangle})\not\in
C_{v}\\}|$, since otherwise we are done by either Case 1 or Case 2. Now,
consider a generic ${\langle{v,u}\rangle}\in C^{\prime\prime}_{v}$, and let
$w\neq u$ be such that
$\mu^{\prime}({\langle{v,u}\rangle})={\langle{v,w}\rangle}$. Then, in
$\mu^{\prime}(G^{\prime}_{n})$ an edge colored either 0 or 2 connects
${\langle{v,w}\rangle}=\mu^{\prime}({\langle{v,u}\rangle})$ to
$\mu^{\prime}({\langle{u,v}\rangle})$, since ${\langle{v,u}\rangle}$ and
${\langle{u,v}\rangle}$ are so connected in $G^{\prime}_{n}$, whereas in
$G^{\prime}_{n}$ an (even-colored) edge connects ${\langle{v,w}\rangle}$ to
${\langle{w,v}\rangle}\in C_{w}$. We consider two sub-cases.

  * •

If $\mu^{\prime}({\langle{u,v}\rangle})\in C_{u}$, then
${\langle{v,w}\rangle}$ contributes to the difference between
$\mu^{\prime}(G^{\prime}_{n})$ and $G^{\prime}_{n}$, because in
$\mu^{\prime}(G^{\prime}_{n})$ vertex ${\langle{v,w}\rangle}$ is connected (by
its even-colored edge) to a vertex in $C_{u}$ whereas in $G^{\prime}_{n}$
vertex ${\langle{v,w}\rangle}$ is connected (by its even-colored edge) to a
vertex in $C_{w}$.

(Recall that $w$ is uniquely determined by ${\langle{v,u}\rangle}\in
C^{\prime\prime}_{n}$, since
$\mu^{\prime}({\langle{v,u}\rangle})={\langle{v,w}\rangle}$, and so this
contribution can be charged to ${\langle{v,u}\rangle}$.)

  * •

If $\mu^{\prime}({\langle{u,v}\rangle})\not\in C_{u}$, then
${\langle{u,v}\rangle}$ contributes to the set
$\bigcup_{x\in[n]}\\{{\langle{x,y}\rangle}\\!\in\\!C_{x}:\mu^{\prime}({\langle{x,y}\rangle})\not\in
C_{x}\\}$, which (by the hypothesis) has size at most
$0.5\cdot\sum_{v\in[n]}|C^{\prime\prime}_{v}|$

Hence, at least half of $\bigcup_{v\in[n]}C^{\prime\prime}_{v}$ appears in the
first sub-case, which implies that, in this case, the difference between
$G^{\prime}_{n}$ and $\mu^{\prime}(G_{n})$ is at least
$\frac{1}{2}\cdot\sum_{v\in[n]}|C^{\prime\prime}_{v}|=\Omega(|T^{\prime}|)$.

Hence, the difference between $G^{\prime}_{n}$ and $\mu^{\prime}(G_{n})$ is
$\Omega(|T^{\prime}|)$.

###  8 Relation to Non-Malleable Two-Source Extractors

For $n=2^{\ell}$, we reduce the construction of $\Omega(n)$-robustly self-
ordered (dense) $n$-vertex graphs to the construction of non-malleable two-
source extractors for $(\ell,\ell-O(1))$-sources. Recall that a random
variable $X$ is called an $(\ell,k)$-source if $X$ is distributed over
$[2^{\ell}]$ and has min-entropy at least $k$ (i.e., ${\rm Pr}[X\\!=\\!i]\leq
2^{-k}$ for every $i\in[2^{\ell}]$).363636Indeed, for the sake of simplicity
(of our arguments), we do not require that $\ell\in\mathbb{N}$, but rather
only that $2^{\ell}\in\mathbb{N}$; consequently, we consider distributions
over $[2^{\ell}]$ rather than over $\\{0,1\\}^{\ell}$. A function ${\tt
E}:[2^{\ell}]\times[2^{\ell}]\to\\{0,1\\}^{m}$ is called a (standard) two-
source $(k,\epsilon)$-extractor if, for every two independent
$(\ell,k)$-sources $X$ and $Y$, it holds that ${\tt E}(X,Y)$ is
$\epsilon$-close to the uniform distribution over $\\{0,1\\}^{m}$, denoted
$U_{m}$. Our notion of a non-malleable two-source extractor, presented next,
is a restricted case of the notions considered in [8, 7].373737In particular,
in [8, 7] it is only required that one of the two functions
$f,g:[2^{\ell}]\to[2^{\ell}]$ has no fixed-points. There seems to be no
concrete reason to prefer one of these three variants over the others. We
mention that Definition 8.1 is strictly weaker than the definition of [8]
(even in its simplified form [7, Def. 1.3]; see Appendix).

###### Definition 8.1

(non-malleable two-source extractors): A function ${{\tt
nmE}}:[2^{\ell}]\times[2^{\ell}]\to\\{0,1\\}^{m}$ is called a non-malleable
two-source $(k,\epsilon)$-extractor if, for every two independent
$(\ell,k)$-sources $X$ and $Y$, and for every two functions
$f,g:[2^{\ell}]\to[2^{\ell}]$ that have no fixed-point (i.e., $f(z)\neq z$ and
$g(z)\neq z$ for every $z\in[2^{\ell}]$), it holds that $({\tt nmE}(X,Y),{\tt
nmE}(f(X),g(Y)))$ is $\epsilon$-close to $(U_{m},{\tt nmE}(f(X),g(Y))$; that
is,

$\frac{1}{2}\cdot\sum_{\alpha,\beta}\left|{\rm Pr}[({\tt nmE}(X,Y),{\tt
nmE}(f(X),g(Y)))\\!=\\!(\alpha,\beta)]-2^{-m}\cdot{\rm Pr}[{\tt
nmE}(f(X),g(Y))\\!=\\!\beta]\right|\;\leq\;\epsilon.$ (19)

The parameter $\epsilon$ is called the error of the extractor.

We shall be interested in the special case in which $f$ and $g$ are
permutations. In this case, the foregoing condition (i.e., Eq. (19)) can be
replaced by requiring that $({\tt nmE}(X,Y),{\tt nmE}(f(X),g(Y)))$ is
$2\epsilon$-close to the uniform distribution over $\\{0,1\\}^{m+m}$.383838In
this case, $f(X)$ and $g(Y)$ have min-entropy at least $k$, which implies that
${\tt nmE}(f(X),g(Y))$ is $\epsilon$-close to the uniform distribution over
$\\{0,1\\}^{m}$. Furthermore, we shall focus on non-malleable two-source
$(k,\epsilon)$-extractors that output a single bit (i.e., $m=1$), and in this
case non-triviality mandates $\epsilon<0.5$. In general, we view $\epsilon$ as
a constant, but view $\ell$ and $k$ as varying (or generic) parameters, and
focus on the case of $k=\ell-O(1)$.

Recall that constructions of non-malleable two-source
$(k,\epsilon)$-extractors with much better parameters are known [7, Thm. 1].
In particular, these constructions support $k=\ell-\ell^{\Omega(1)}$,
negligible error (i.e., $\epsilon=\exp(-\ell^{\Omega(1)})$), and
$m=\ell^{\Omega(1)}$. We stress that, as is the norm in the context of
randomness extraction, the extracting function is computable in polynomial-
time (i.e., in ${\rm poly}(\ell)$-time).

We shall show that any non-malleable two-source $(\ell-O(1),0.49)$-extractor
(for sources over $[2^{\ell}]$) yields $\Omega(2^{\ell})$-robustly self-
ordered $O(2^{\ell})$-vertex graphs. Actually, we shall show two such
constructions: The first construction runs in ${\rm poly}(2^{\ell})$-time, and
the second construction provides strong constructability (a.k.a local
computability) as claimed in Theorem 1.4. Both constructions use a similar
underlying logic, which is more transparent in the first construction.

####  8.1 The first construction

For the first construction, we need the extractor to satisfy the following
natural (and quite minimal) requirement, which we call quasi-orthogonality. We
say that an extractor ${{\tt nmE}}:[2^{\ell}]\times[2^{\ell}]\to\\{0,1\\}$ is
quasi-orthogonal (with error $\epsilon$) if the following conditions hold:

  1. 1.

The residual function obtained from ${\tt nmE}$ by any fixing of one of its
two arguments is almost unbiased: For every $x\in[2^{\ell}]$ and every
$\sigma\in\\{0,1\\}$ it holds that $|\\{y\\!\in\\![2^{\ell}]:{\tt
nmE}(x,y)\\!=\\!\sigma\\}|\leq(0.5+\epsilon)\cdot 2^{\ell}$; ditto for every
$y\in[2^{\ell}]$ and the corresponding set $\\{x\\!\in\\![2^{\ell}]:{\tt
nmE}(x,y)\\!=\\!\sigma]\\}$.

  2. 2.

The residual functions obtained from ${\tt nmE}$ by any two different fixings
of one of its two arguments are almost uncorrelated: For every
$\\{x,x^{\prime}\\}\in{{[2^{\ell}]}\choose 2}$ it holds that
$|\\{y\\!\in\\![2^{\ell}]:{\tt nmE}(x,y)\\!\neq\\!{\tt
nmE}(x^{\prime},y)\\}|\geq(0.5-\epsilon)\cdot 2^{\ell}$; ditto for every
$\\{y,y^{\prime}\\}\in{{[2^{\ell}]}\choose 2}$ and the corresponding set
$\\{x\\!\in\\![2^{\ell}]:{\tt nmE}(x,y)\\!\neq\\!{\tt nmE}(x,y^{\prime})]\\}$.

As shown in Proposition 8.2, any non-malleable two-source
$(k,\epsilon)$-extractor can be transformed (in ${\rm poly}(2^{\ell})$-time)
into a quasi-orthogonal one at a small degradation in the parameters (i.e.,
$\epsilon$ increases by an additive term of $O(2^{-(\ell-k)})$ and $2^{\ell}$
decreases by an additive term of $O(2^{k})$). Note that ${\rm
poly}(2^{\ell})$-time is acceptable when one aims at constructing
$O(2^{\ell})$-vertex graphs; however, aiming at strong/local constructability
(as in Theorem 1.4), we shall avoid such a transformation in the second
construction (presented in Section 8.2).

###### Proposition 8.2

(transforming non-malleable two-source extractors into ones that are quasi-
orthogonal): For every $k\leq\ell-3$, there exists a ${\rm
poly}(2^{\ell})$-time transformation that given a non-malleable two-source
$(k,\epsilon)$-extractor ${{\tt nmE}}:[2^{\ell}]\times[2^{\ell}]\to\\{0,1\\}$,
returns a non-malleable two-source $(k,\epsilon^{\prime})$-extractor ${{\tt
nmE}}:[n^{\prime}]\times[n^{\prime}]\to\\{0,1\\}$ such that $n^{\prime}\geq
2^{\ell}-O(2^{k})$ and ${\tt nmE}^{\prime}$ is quasi-orthogonal with error
$\epsilon^{\prime}=\epsilon+O(2^{k}/n^{\prime})$.

Proof: Essentially, ${\tt nmE}^{\prime}$ is obtained from ${\tt nmE}$ by
simply discarding inputs that violate the quasi-orthogonality conditions.
Letting $n=2^{\ell}$, first note that the number of $x$’s that violate the
first condition is at most $2^{k+1}$, because otherwise we obtain a
contradiction to the hypothesis that ${\tt nmE}$ is a two-source
$(k,\epsilon)$-extractor (by letting $X$ be uniform on the $x$’s that satisfy
$|\\{y\\!\in\\![n]:{\tt nmE}(x,y)\\!=\\!\sigma\\}|>(0.5+\epsilon)\cdot n$ for
either $\sigma=0$ or $\sigma=1$, and $Y$ be uniform on $\\{0,1\\}^{n}$). Next,
consider the residual $(k,\epsilon)$-extractor ${\tt
nmE}_{1}:[n_{1}]\times[n_{1}]\to\\{0,1\\}$, where $n_{1}\geq n-2^{k+1}$,
obtained by omitting the exceptional $x$’s. Note that ${\tt nmE}_{1}$
satisfies the first quasi-orthogonality condition with respect to the first
argument with error $\epsilon$. Doing the same for the second argument yields
a residual $(k,\epsilon)$-extractor ${\tt
nmE}_{2}:[n_{2}]\times[n_{2}]\to\\{0,1\\}$, where $n_{2}\geq n_{1}-2^{k+1}$
and ${\tt nmE}_{2}$ satisfies the first quasi-orthogonality condition (for
both arguments) with error $\epsilon+\frac{2^{k+1}}{n_{1}}$. Likewise, we
claim that there are at most $2^{k}$ disjoint pairs $\\{x,x^{\prime}\\}$’s
that violate the second condition (i.e., $|\\{y\\!\in\\![n_{2}]:{\tt
nmE}_{2}(x,y)\\!\neq\\!{\tt nmE}_{2}(x^{\prime},y)\\}|\geq(0.5-\epsilon)\cdot
n_{2}$), because otherwise we obtain a contradiction to the hypothesis that
${\tt nmE}_{2}$ is a non-malleable two-source $(k,\epsilon)$-extractor (by
using a function that maps each such $x$ to its matched $x^{\prime}$). And,
again, we consider a residual extractor obtained by omitting the exceptional
pairs. Doing the same for the $y$’s, we obtained the desired extractor.

Recall that non-malleable two-source extractors with much stronger parameters
than we need (i.e., min-entropy $\ell-\ell^{\Omega(1)}$, negligible error, and
$\ell^{\Omega(1)}$ bits of output), were constructed in [7, Thm. 1], but these
extractors are not quasi-orthogonal. Employing Proposition 8.2, we obtain a
quasi-orthogonal non-malleable two-source $(\ell-4,0.1)$-extractor that can be
used in the construction of Theorem 8.3. Essentially, the construction
consists of a bipartite graph, with $2^{\ell}$ vertices on each side, such
that the edges between the two sides are determined by the extractor. In
addition, we add a clique on one of the two sides so that the two sides are
(robustly) distinguishable (see Fugure 1). We stress that the resulting
$2^{\ell+1}$-vertex graph is $\Omega(2^{\ell})$-robustly self-ordered as long
as the non-malleable extractor is quasi-orthogonal and works for very mild
parameters; that is, we only require error that is bounded away from $1/2$
with respect to min-entropy $\ell-O(1)$.

Figure 1: Illustrating the construction of Theorem 8.3.

###### Theorem 8.3

(using a quasi-orthogonal non-malleable two-source extractor to obtain a
$\Omega(2^{\ell})$-robustly self-ordered $O(2^{\ell})$-vertex graph): For a
constant $\epsilon\in(0,0.5)$ varying $\ell\geq k$ such that
$k\leq\ell-2+\log_{2}(0.5-\epsilon)=\ell-O(1)$, suppose that ${{\tt
nmE}}:[2^{\ell}]\times[2^{\ell}]\to\\{0,1\\}$ is a quasi-orthogonal (with
error $\epsilon$) non-malleable two-source $(k,\epsilon)$-extractor. Then, the
$2^{\ell+1}$-vertex graph $G=(V_{1}\cup V_{0},E)$ such that
$V_{\sigma}=\\{{\langle{\sigma,i}\rangle}\\!:\\!i\\!\in\\![2^{\ell}]\\}$ and

$E\;=\;\left\\{\\{{\langle{1,i}\rangle},{\langle{0,j}\rangle}\\}\\!:\\!{\tt
nmE}(i,j)\\!=\\!1\right\\}\cup{{V_{1}}\choose 2}$ (20)

is $\Omega(|V_{1}\cup V_{0}|)$-robustly self-ordered. Furthermore, the claim
holds even if the non-malleability condition (i.e., Eq. (19)) holds only for
permutations $f$ and $g$.

Indeed, the first set of edges, denoted $E^{\prime}$, corresponds to a
bipartite graph between $V_{1}$ and $V_{0}$ that is determined by ${\tt nmE}$,
and the second set corresponds to a $2^{\ell}$-vertex clique. Note that the
extraction parameters are extremely weak; that is, the min-entropy may be very
high (i.e., $k=\ell-O(1)$), the error may be an arbitrary non-trivial constant
(i.e., $\epsilon<1/2$), and we only extract one bit (i.e., $m=1$).

Proof: Let $V=V_{1}\cup V_{0}$, and consider an arbitrary (non-trivial)
permutation $\mu:V\to V$. Intuitively, if $\mu$ maps a vertex of $V_{1}$ to
$V_{0}$, then the difference in degrees of vertices in the two sets (caused by
the clique edges) contributes at least $((2^{\ell}-1)-2\epsilon\cdot
2^{\ell})/2$ units to the symmetric difference between $G$ and $\mu(G)$, where
here we use the first quasi-orthogonality condition. On the other hand, if
$\mu$ maps ${\langle{1,i}\rangle}\in V_{1}$ to
$V_{1}\setminus\\{{\langle{1,i}\rangle}\\}$, then the difference in the
neighborhoods caused by the bipartite graph contributes at least
$(0.5-\epsilon)\cdot 2^{\ell}/2$ units to the symmetric difference between $G$
and $\mu(G)$. To prove this, we distinguish between the case that $\mu$ has
relatively few non-fixed-points (in either $V_{0}$ or $V_{1}$), which is
analyzed using the second quasi-orthogonality condition, and the case that
$\mu$ has relatively many non-fixed-points (in both $V_{0}$ and $V_{1}$),
which is analyzed using the non-malleability condition. Details follow.

Let $T=\\{v\\!\in\\!V\\!:\\!\mu(v)\neq v\\}$ denote the set of non-fixed-
points of $\mu$. Then, we consider two types of vertices: Those that belong to
the set
$T^{\prime}=\bigcup_{\sigma\in\\{0,1\\}}\\{v\\!\in\\!V_{\sigma}\\!:\\!\mu(v)\not\in
V_{\sigma}\\}\subseteq T$ and those that belong to $T\setminus T^{\prime}$.
The threshold for distinguishing these cases is set to $K=(0.5-\epsilon)\cdot
2^{\ell-2}=\Omega(|V|)$.

Case 1:

$|T^{\prime}|\geq K$.

(This refers to the case that many vertices are mapped by $\mu$ to the
opposite side of the bipartite graph $(V,E^{\prime})$, where ‘many’ means
$\Omega(|V|)$.)

Each vertex in $T^{\prime}$ contributes $(1-2\epsilon)\cdot 2^{\ell}-1$ units
to the symmetric difference between $G$ and $\mu(G)$, because the degree of
each vertex in $V_{1}$ is at least $(2^{\ell}-1)+(0.5-\epsilon)\cdot
2^{\ell}$, whereas the degree of each vertex in $V_{0}$ is at most
$(0.5+\epsilon)\cdot 2^{\ell}$, where we use the first quasi-orthogonality
condition, which implies that the number of bipartite edges incident at each
vertex is at least $(0.5-\epsilon)\cdot 2^{\ell}$ and at most
$(0.5+\epsilon)\cdot 2^{\ell}$.

Hence, the symmetric difference between $G$ and $\mu(G)$ is at least
$((1-2\epsilon)\cdot
2^{\ell}-1)\cdot|T^{\prime}|=\Omega(|V|)\cdot|T^{\prime}|$, since
$2^{\ell}=\Omega(|V|)$. Using the case’s hypothesis, we have
$|T^{\prime}|=\Omega(|V|)=\Omega(|T|)$, which means that in this case the
difference between $G$ and $\mu(G)$ is $\Omega(|V|)\cdot|T|$.

We stress that the difference between $G$ and $\mu(G)$ is at least
$\Omega(|V|)\cdot|T^{\prime}|$ also if the case hypothesis does not hold.

Case 2:

$|T^{\prime}|<K$.

(This refers to the case that few vertices are mapped by $\mu$ to the opposite
side of the bipartite graph $(V,E^{\prime})$, where ‘few’ means less than
$K\leq|V|/20$ (assuming $\epsilon\leq 0.1$).)

For every $\sigma\in\\{0,1\\}$, let
$V^{\prime}_{\sigma}=V_{\sigma}\cap\mu(V_{\sigma})$ and
$T_{\sigma}=V^{\prime}_{\sigma}\cap T$. Indeed, $(T^{\prime},T_{0},T_{1})$ is
a three-way partition of $T$. Note that the size of the symmetric difference
between $G$ and $\mu(G)$ is lower-bounded by

$\left|\\{(v,u)\in V^{\prime}_{1}\times V^{\prime}_{0}:{\tt
nmE}(\mu(v),\mu(u))\neq{\tt nmE}(v,u)\\}\right|,$ (21)

since, for any $(v,u)\in V^{\prime}_{1}\times V^{\prime}_{0}$, it holds that
$\mu(v)$ neighbors $\mu(u)$ in $G$ if and only if ${\tt
nmE}(\mu(v),\mu(u))=1$, whereas $\mu(v)$ neighbors $\mu(u)$ in $\mu(G)$ if and
only if $v$ neighbors $u$ in $G$ which holds if and only if ${\tt
nmE}(v,u)=1$.

We consider two sub-cases according to whether or not $\min(|T_{0}|,|T_{1}|)$
is relatively large. The threshold for distinguishing these sub-cases is also
set to $K=(0.5-\epsilon)\cdot 2^{\ell-2}$; note that $K=\Omega(|V|)$ and
$K\geq 2^{k}$.

Case 2.1:

$\min(|T_{0}|,|T_{1}|)<K$.

In this case we shall use the (second condition of) quasi-orthogonality of
${\tt nmE}$.

Suppose, without loss of generality, that $|T_{0}|\leq|T_{1}|$, which implies
$|T_{0}|<K$. Then, the contribution of each vertex $v\in T_{1}$ to Eq. (21)
equals

$\displaystyle|\\{u\in V^{\prime}_{0}:{\tt nmE}(\mu(v),\mu(u))\neq{\tt
nmE}(v,u)\\}|$ $\displaystyle\geq$ $\displaystyle|\\{u\in V^{\prime}_{0}:{\tt
nmE}(\mu(v),u)\neq{\tt nmE}(v,u)\\}|-|T_{0}|$ $\displaystyle\geq$
$\displaystyle|\\{u\in V_{0}:{\tt nmE}(\mu(v),u)\neq{\tt
nmE}(v,u)\\}|-|T^{\prime}|-|T_{0}|$ $\displaystyle\geq$
$\displaystyle(0.5-\epsilon)\cdot 2^{\ell}-2\cdot K$ $\displaystyle=$
$\displaystyle(0.5-\epsilon)\cdot 2^{\ell-1}$

where the first inequality uses $\mu(u)=u$ for $u\in V^{\prime}_{0}\setminus
T_{0}$, the second inequality uses $|V^{\prime}_{0}|\geq|V_{0}|-|T^{\prime}|$,
the third inequality uses $\mu(v)\neq v$ along with the (second condition of)
quasi-orthogonality of ${\tt nmE}$ (and the hypotheses regarding
$|T^{\prime}|$ and $|T_{0}|$), and the equality is due to
$K=(0.5-\epsilon)\cdot 2^{\ell-2}$.

Hence, in this case, the total contribution to Eq. (21) is
$(0.5-\epsilon)\cdot 2^{\ell-1}\cdot|T_{1}|$, which is
$\Omega(|V|)\cdot(|T|-|T^{\prime}|)$, since $|T_{1}|\geq(|T|-|T^{\prime}|)/2$.

Case 2.2:

$\min(|T_{0}|,|T_{1}|)\geq K$.

In this case we shall use the non-malleable feature of ${\tt nmE}$.

Specifically, for each $\sigma\in\\{0,1\\}$, let $\mu_{\sigma}$ denote the
restriction of $\mu$ to $T_{\sigma}$. Essentially, using $K\geq 2^{k}$, the
non-malleability condition of the $(k,\epsilon)$-extractor ${\tt nmE}$ implies

$\left|\left\\{(i,j)\in T_{0}\times T_{1}:{\tt nmE}(i,j)\neq{\tt
nmE}(\mu_{0}(i),\mu_{1}(j))\right\\}\right|\geq(0.5-\epsilon)\cdot|T_{0}|\cdot|T_{1}|.$

This can be seen by letting $X$ and $Y$ be uniform over $T_{0}$ and $T_{1}$,
respectively, and combining the fact that ${\rm Pr}[{\tt
nmE}(\mu_{0}(X),\mu_{1}(Y))\neq U_{1}]=0.5$ with the non-malleability
condition (while noting that $\mu_{0}:T_{0}\to\mu(T_{0})$ and
$\mu_{1}:T_{1}\to\mu(T_{1})$ have no fixed-points).393939Formally, we should
extend $\mu_{0}$ and $\mu_{1}$ to (arbitrary) derangements $f$ and $g$,
respectively. (Note that we may assume, w.l.o.g., that
$|T_{\sigma}\cup\mu(T_{\sigma})|\leq|V_{\sigma}|-2$.) Lastly, note that Eq.
(19) implies that ${\rm Pr}[{\tt nmE}(X,Y)\neq{\tt nmE}(f(X),g(Y))]\geq{\rm
Pr}[U_{1}\neq{\tt nmE}(f(X),g(Y))]-\epsilon=0.5-\epsilon$.

Hence, in this case, the total contribution to Eq. (21) is
$(0.5-\epsilon)\cdot|T_{0}|\cdot|T_{1}|=\Omega(|V|)\cdot(|T|-|T^{\prime}|)$,
where we use $\min(|T_{0}|,|T_{1}|)=\Omega(|V|)$.

Hence, in both sub-cases, the difference between $G$ and $\mu(G)$ is
$\Omega(|V|)\cdot(|T|-|T^{\prime}|)$.

Recall that (by the last comment at Case 1) the difference between $G$ and
$\mu(G)$ is $\Omega(|V|)\cdot|T^{\prime}|$. Combining this lower-bound with
the conclusion of Case 2, the difference between $G$ and $\mu(G)$ is
$\Omega(|V|)\cdot|T|$.

###### Digest:

Note that the quasi-orthogonality of ${\tt nmE}$ was used in Cases 1 and 2.1,
whereas the non-malleability of ${\tt nmE}$ (w.r.t derangements) was used in
Case 2.2. In particular, Case 1 only uses the first condition of quasi-
orthogonality, and does so in order to infer that the degrees of all vertices
in the bipartite graph are approximately equal. In Case 2.1 the second quasi-
orthogonality condition is used in order to assert that the neighborhoods of
two different vertices in $V_{\sigma}$ are significantly different. This is
useful only when the number of non-fixed-points in $V_{1-\sigma}$ is
relatively small. When the number of non-fixed-points is large but no vertex
is mapped to the other side (i.e., $T^{\prime}=\emptyset$), we only use Case
2.2, which does not refer to quasi-orthogonality at all. Hence, we have the
following –

###### Remark 8.4

(a special case of Theorem 8.3): For bipartite graphs $G=(V,E)$ such that
$V=V_{0}\cup V_{1}$ and $E\subseteq V_{0}\times V_{1}$, we consider the
special case of robust self-ordering that refers only to permutations
$\mu:V\to V$ that are derangements that preserve the bipartition of $V$ (i.e.,
$\mu$ has no fixed-points and $\mu(V_{0})=V_{0}$).404040That is, the
requirement regarding the symmetric difference between $G$ and $\mu(G)$ is
made only for permutations $\mu$ that have no fixed-points and satisfy
$\mu(V_{0})=V_{0}$. In this case, assuming (only) that ${\tt nmE}$ is a non-
malleable two-source $(\ell,\epsilon)$-extractor (i.e., the case of $k=\ell$),
implies that, for any such $\mu$, the size of the symmetric difference between
$G$ and $\mu(G)$ is $(0.5\pm\epsilon)\cdot|V_{0}|\cdot|V_{1}|$. In particular,
the quasi-orthogonality condition is not necessary, the proof of Theorem 8.3
simplifies, since $T^{\prime}=\emptyset$ and
$T_{\sigma}=V_{\sigma}=V^{\prime}_{\sigma}$ hold, and the size of the
symmetric difference between $G$ and $\mu(G)$ equal the quantity in Eq. (21).

Interestingly, the special case of Theorem 8.3 asserted in Remark 8.4 can be
reversed in the sense that a bipartite graph that is robustly self-ordered in
the foregoing restricted sense is actually a non-malleable two-source
$(\ell,0.5-\Omega(1))$-extractor.

###### Proposition 8.5

(a reversal of the special case of Theorem 8.3 (i.e., of Remark 8.4)): Let
$G=(V_{0}\cup V_{1},E)$ be a bipartite graph such that $|V_{0}|=|V_{1}|$ and
$E\subseteq V_{0}\times V_{1}$. Let $V=V_{0}\cup V_{1}$, and suppose that for
every derangement $\mu:V\to V$ such that $\mu(V_{0})=V_{0}$ it holds that the
size of the symmetric difference between $G$ and $\mu(G)$ is
$(0.5\pm\epsilon)\cdot|V_{0}|\cdot|V_{1}|$. Then, $F:V_{0}\times
V_{1}\to\\{0,1\\}$ such that $F(x,y)=1$ if and only if $\\{x,y\\}\in E$ is a
non-malleable two-source $(\ell,\epsilon+{\sqrt{2\epsilon}}+o(1))$-extractor.

Needless to say, the claim holds also if $G$ is augmented by complete graph on
the vertex-set $V_{1}$. Note that we lose a $\sqrt{2\epsilon}+o(1)$ term in
the reversal.

Proof: Let $(f,g)$ and $(X,Y)$ be as in Definition 8.1, and note that in this
case $X$ and $Y$ are independent distributions that are each uniformly
distributed on $[2^{\ell}]$. Define $\mu:V\to V$ such that $\mu(z)=f(z)$ if
$z\in V_{0}$ and $\mu(z)=g(z)$ otherwise, and note that $\mu$ is a derangement
that preserves the partition of $V$. Recall that $(\mu(x),\mu(y))$ contributes
to the symmetric difference between $G$ and $\mu(G)$ if and only if
$F(\mu(x),\mu(y))\neq F(x,y)$, since $\mu(x)$ is connected to $\mu(y)$ in
$\mu(G)$ if and only if $x$ is connected to $y$ in $G$. Hence, by the
hypothesis, we have

${\rm Pr}[F(X,Y)\neq F(\mu(X),\mu(Y))]=0.5\pm\epsilon.$ (22)

Letting $p_{\sigma,\tau}^{\mu}\stackrel{{\scriptstyle\rm def}}{{=}}{\rm
Pr}[(F(X,Y),F(\mu(X),\mu(Y)))\\!=\\!(\sigma,\tau)]$, we have
$p_{0,1}^{\mu}+p_{1,0}^{\mu}=0.5\pm\epsilon$, and using the fact that $(X,Y)$
and $(\mu(X),\mu(Y))$ are identically distributed we have
$p_{1,0}^{\mu}=p_{0,1}^{\mu}$ (since
$p_{1,1}^{\mu}+p_{1,0}^{\mu}=p_{1,1}^{\mu}+p_{0,1}^{\mu}$). Hence,
$p_{0,1}^{\mu}=0.25\pm 0.5\epsilon$. Lastly, we show that
$p_{1,1}^{\mu}+p_{1,0}^{\mu}=0.5\pm{\sqrt{\epsilon/2}}+o(1)$, and conclude
that $p_{1,1}^{\mu}=0.25\pm(0.5\epsilon+{\sqrt{\epsilon/2}}+o(1))$; it follows
that $F$ is a non-malleable (two-source)
$(\ell,\epsilon+{\sqrt{2\epsilon}}+o(1))$-extractor.

To show that $p_{1,1}^{\mu}+p_{1,0}^{\mu}=0.5\pm{\sqrt{\epsilon/2}}+o(1)$, we
first note that $p\stackrel{{\scriptstyle\rm
def}}{{=}}p_{1,1}^{\mu}+p_{1,0}^{\mu}={\rm Pr}[F(X,Y)\\!=\\!1]$ is actually
oblivious of $\mu$. Hence, by considering a random derangement $\mu$ that
preserves $V_{0}$ (i.e., $\mu(V_{0})=V_{0}$), we observe that, with
overwhelmingly high probability (over the choice of $\mu$), it holds that
$\\{(x,y)\\!\in\\!V_{0}\times V_{1}\\!:\\!F(x,y)\neq F(\mu(x),\mu(y))\\}$ has
size $(2p(1-p)\pm o(1))\cdot|V_{0}|\cdot|V_{1}|$. Confronting this with Eq.
(22), we infer that $p=0.5\pm({\sqrt{\epsilon/2}}+o(1))$.

###### Corollary.

Combining Theorem 8.3 with the non-malleable two-source extractors of [7, Thm.
1], while using Proposition 8.2, we obtain an efficient construction of
$\Omega(n)$-robustly self-ordered graphs (alas not a strongly explicit (aka
locally computable) one).

###### Theorem 8.6

(constructing $\Omega(n)$-robustly self-ordered $n$-vertex graphs): There
exist an algorithm that, on input $n$, works in ${\rm poly}(n)$-time and
outputs an explicit description of an $\Omega(n)$-robustly self-ordered
$O(n)$-vertex graph. Furthermore, each vertex in this graph has degree at
least $0.24\cdot n$ and at most $0.76\cdot n$.

The degree bounds follow by observing that the vertices in the graph described
in Theorem 8.3 have degree at least $(0.5-\epsilon)\cdot n/2$ and at most
$(1.5+\epsilon)\cdot n/2$, whereas [7, Thm. 1] provides for $\epsilon=o(1)$.

####  8.2 The second construction

Combining Theorem 8.3 with the non-malleable two-source extractors of [7, Thm.
1], while using Proposition 8.2, we obtained an efficient construction of
$\Omega(n)$-robustly self-ordered $n$-vertex graphs (see Theorem 8.6).
However, this construction is not locally computable (as postulated in Theorem
1.4), because the non-malleable two-source extractors of [7, Thm. 1] are not
quasi-orthogonal and the transformation of Proposition 8.2 runs in time that
is polynomial in the size of the resulting graph.

To avoid the foregoing transformation and prove Theorem 1.4, we employ a
variant on the construction presented in Theorem 8.3. Rather than connecting
two sets of vertices using a bipartite graph that corresponds to a quasi-
orthogonal non-malleable two-source extractor, we connect three sets of
vertices such that one pair of vertex-sets is connected by a (not necessarily
quasi-orthogonal) non-malleable two-source extractor, whereas the other two
pairs are connected by bipartite graphs that are merely quasi-orthogonal. In
analogy to the definition of a quasi-orthogonal (two-source) extractor, we say
that a bipartite graph on the vertex-set $X\cup Y$ is quasi-orthogonal (with
error $\epsilon$) if the following two conditions hold regarding its adjacency
predicate $B:X\times Y\to\\{0,1\\}$:

  1. 1.

The degree of each vertex is approximately half the number of the vertices on
the other side: For each $x\in X$ (resp., $y\in Y$), it holds that
$|\\{y\\!\in\\!Y\\!:\\!B(x,y)\\!=\\!1\\}|=(0.5\pm\epsilon)\cdot|Y|$ (resp.,
$|\\{x\\!\in\\!X\\!:\\!B(x,y)\\!=\\!1\\}|=(0.5\pm\epsilon)\cdot|X|$).

  2. 2.

Each pair of vertices on one side neighbors approximately a quarter of the
vertices on the other side: For every $x\neq x^{\prime}\in X$, it holds that
$|\\{y\\!\in\\!Y\\!:\\!B(x,y)\\!\neq\\!B(x^{\prime},y)\\}|=(0.5\pm\epsilon)\cdot|Y|$.
Similarly, for $y\neq y^{\prime}\in Y$.

We note that inner-product (mod 2) extractor, denoted
$E_{2}:\\{0,1\\}^{\ell}\times\\{0,1\\}^{\ell}\to\\{0,1\\}$, corresponds to a
quasi-orthogonal bipartite graph for the case
$X=Y=\\{0,1\\}^{\ell}\setminus\\{0^{\ell}\\}$. We will however need quasi-
orthogonal bipartite graphs with different-sized sides, which can be obtained
by a simple variant. Specifically, for the case of
$X=\\{0,1\\}^{\ell}\setminus\\{0^{\ell}\\}$ and
$Y=\\{0,1\\}^{\ell+2}\setminus\\{0^{\ell+2}\\}$, we use the function
$B(x,y)=E_{2}(G(x),y)$, where $G:\\{0,1\\}^{\ell}\to\\{0,1\\}^{\ell+2}$ is a
small-bias generator that satisfies $G(x)\neq 0^{\ell+2}$ and $G(x)\neq
G(x^{\prime})$ for every $x\neq 0^{\ell}$ and $x^{\prime}\neq x$ (see
Proposition 8.8, and note that $G(a,b,c,d)=(a,b,c,d,E_{2}(a,b),E_{2}(c,d))$
will do). We stress that the foregoing construction is strongly explicit
(i.e., locally computable).

We shall also assume that the (bipartite graph corresponding to the) non-
malleable extractor ${{\tt nmE}}:[2^{\ell}-1]\times[2^{\ell}-1]\to\\{0,1\\}$
has linear degrees in the sense that for every $x$ it holds that
$|\\{y\\!\in\\![2^{\ell}-1]\\!:\\!{\tt
nmE}(x,y)\\!=\\!1\\}|\geq\epsilon^{\prime}\cdot 2^{\ell}$ for some constant
$\epsilon^{\prime}>0$. This can be enforced by starting with an arbitrary non-
malleable two-source $(k,\epsilon^{\prime})$-extractor (e.g., the one of [7,
Thm. 1]) and resetting pairs in $m=\epsilon^{\prime}\cdot 2^{\ell}$ fixed
perfect matchings to 1 (i.e., for each $(x,y)$ in one of these matching, we
reset ${\tt nmE}(x,y)\leftarrow 1$).414141For example, we may use the
matchings $\\{(z,z+i):z\in[2^{\ell}-1]\\}$ for $i\in[m]$, where addition is
mod $2^{\ell}-1$. In addition, starting from an extractor that is defined over
$\ell$-bit strings, we may omit one of these strings (and obtain an extractor
defined over $[2^{\ell}-1]$). This increases the error of the extractor by an
additive term of $m/2^{k}=2^{\ell-k}\cdot\epsilon^{\prime}$, which we can
afford (e.g., $\epsilon^{\prime}=0.01$ and $k=\ell-4$, yields extraction error
$\epsilon<0.2$). We stress that this transformation preserves polynomial-time
computability of the extracting function.

###### Theorem 8.7

(using a non-malleable two-source extractor with linear degrees to obtain a
$\Omega(2^{\ell})$-robustly self-ordered $O(2^{\ell})$-vertex graph): For any
constants $\epsilon,\epsilon^{\prime}\in(0,0.5)$ and varying $k\leq\ell-4$,
where $\ell\in\mathbb{N}$, suppose that ${{\tt
nmE}}:[2^{\ell}-1]\times[2^{\ell}-1]\to\\{0,1\\}$ is a non-malleable two-
source $(k,\epsilon)$-extractor such that for every $x$ it holds that
$|\\{y\\!\in\\![2^{\ell}-1]\\!:\\!{\tt
nmE}(x,y)\\!=\\!1\\}|>\epsilon^{\prime}\cdot 2^{\ell}$. Further suppose that
$B:[2^{\ell}-1]\times[2^{\ell+2}-1]\to\\{0,1\\}$ is quasi-orthogonal with
error $0.1\cdot\epsilon^{\prime}$. Then, the $(6\cdot 2^{\ell}-3)$-vertex
graph $G=(V_{0}\cup V_{1}\cup V_{2},E)$ such that
$V_{\sigma}=\\{{\langle{\sigma,i}\rangle}\\!:\\!i\\!\in\\![2^{\ell_{\sigma}}-1]\\}$,
where $\ell_{0}=\ell_{1}=\ell$ and $\ell_{2}=\ell+2$, and

$E\;=\;\left\\{\\{{\langle{1,i}\rangle},{\langle{0,j}\rangle}\\}\\!:\\!{\tt
nmE}(i,j)\\!=\\!1\right\\}\cup\left\\{\\{{\langle{\sigma,i}\rangle},{\langle{2,j}\rangle}\\}\\!:\\!B(i,j)\\!=\\!1,\sigma\in\\{0,1\\}\right\\}\cup{{V_{1}}\choose
2}\cup{{V_{2}}\choose 2}$ (23)

is $\Omega(|V|)$-robustly self-ordered, where $V=V_{0}\cup V_{1}\cup V_{2}$.
Furthermore, each vertex in this graph has degree at least $0.3\cdot|V|$ and
at most $0.9\cdot|V|$.

Using the foregoing ingredients (including the non-malleable extractor of [7,
Thm. 1]), Theorem 1.4 follows (see also Remark 8.9). Looking at Eq. (23), note
that the first set of edges corresponds to a bipartite graph between $V_{1}$
and $V_{0}$ that is determined by ${\tt nmE}$, the second set corresponds the
bipartite graphs between $V_{\sigma}$ (for $\sigma\in\\{0,1\\}$) and $V_{2}$
that are determined by $B$, and the other two sets correspond to cliques on
$V_{1}$ and on $V_{2}$. (See Figure 2.)

Figure 2: Illustrating the construction of Theorem 8.7.

Proof: Recall that $V=V_{0}\cup V_{1}\cup V_{2}$, and consider an arbitrary
(non-trivial) permutation $\mu:V\to V$. Intuitively, if $\mu$ maps a vertex of
$V_{0}$ (or $V_{1}$) to $V_{2}$, then the difference in degrees of vertices in
the two sets (caused by the $|V_{2}|$-clique edges) contributes $\Omega(|V|)$
units to the symmetric difference between $G$ and $\mu(G)$, where here we use
the first quasi-orthogonality condition of $B$. A similar argument, which uses
the $V_{1}$-clique edges and relies on the linear degrees of ${\tt nmE}$,
applies to a vertex of $V_{\sigma}$ mapped to $V_{1-\sigma}$ for any
$\sigma\in\\{0,1\\}$. On the other hand, if for some $\sigma\in\\{0,1,2\\}$
the bijection $\mu$ maps ${\langle{\sigma,i}\rangle}\in V_{\sigma}$ to
$V_{\sigma}\setminus\\{{\langle{\sigma,i}\rangle}\\}$, then the difference in
the neighborhoods caused by one of the two relevant bipartite graphs
contributes $\Omega(|V|)$ units to the symmetric difference between $G$ and
$\mu(G)$. Here, we distinguishes between the case that $\mu$ has relatively
few non-fixed-points in either $V_{0}$ or $V_{1}$, which is analyzed using the
second quasi-orthogonality condition of $B$, and the case that $\mu$ has
relatively many non-fixed-points in both $V_{0}$ and $V_{1}$, which is
analyzed using the non-malleability condition of ${\tt nmE}$. Indeed, the
structure of the proof is similar to the one of Theorem 8.3, but the details
are different in many aspects, and so we provide them below.

Let $T=\\{v\\!\in\\!V\\!:\\!\mu(v)\neq v\\}$ denote the set of non-fixed-
points of $\mu$. Then, we consider two types of vertices: Those that belong to
the set
$T^{\prime}=\bigcup_{\sigma\in\\{0,1,2\\}}\\{v\\!\in\\!V_{\sigma}\\!:\\!\mu(v)\not\in
V_{\sigma}\\}\subseteq T$ and those that belong to $T\setminus T^{\prime}$.
The threshold for distinguishing these cases is set to
$K=(0.5-0.1\cdot\epsilon^{\prime})\cdot|V_{0}|/4=\Omega(|V|)$.424242The
threshold is set depending on the quasi-orthogonality error of $B$. In the
proof of Theorem 8.3, the threshold was set depending on the quasi-
orthogonality error of ${\tt nmE}$ (which equaled its extraction error).
Recall that $\epsilon$ denotes the extraction error of ${\tt nmE}$, whereas
$\epsilon^{\prime}$ is the fractional degree bound associated with its linear
degrees feature, and $0.1\cdot\epsilon^{\prime}$ is the quasi-orthogonality
error of $B$.

Case 1:

$|T^{\prime}|\geq K$.

(This refers to the case that many vertices are mapped by $\mu$ to a different
part of the three-way partition $(V_{0},V_{1},V_{2})$ of $V$, where ‘many’
means $\Omega(|V|)$.)

Each vertex in $T^{\prime}$ contributes $\Omega(|V|)$ units to the symmetric
difference between $G$ and $\mu(G)$, because of the differences in the degrees
of vertices in the three parts. Specifically:

  * •

Vertices in $V_{2}$ have degree at least
$(|V_{2}|-1)+(0.5-0.1\epsilon^{\prime})\cdot(|V_{0}|+|V_{1}|)>(5-0.2\epsilon^{\prime})\cdot|V_{0}|-O(1)$,
where the first term is due to the clique edges and the second term is due to
the bipartite graphs connecting $V_{2}$ to $V_{0}$ and $V_{1}$ (and relies on
the first quasi-orthogonality condition of $B$).

  * •

Vertices in $V_{0}$ have degree at most
$|V_{1}|+(0.5+0.1\epsilon^{\prime})\cdot|V_{2}|<(3+0.4\epsilon^{\prime})\cdot|V_{0}|+O(1)$,
where the first term is due to the edges (determined by ${\tt nmE}$)
connecting $V_{0}$ to $V_{1}$ and the second term is due to the bipartite
graph connecting $V_{0}$ to $V_{2}$.

  * •

Vertices in $V_{1}$ have degree at least
$(|V_{1}|-1)+\epsilon^{\prime}\cdot|V_{0}|+(0.5-0.1\epsilon^{\prime})\cdot|V_{2}|>(3+0.6\epsilon^{\prime})\cdot|V_{0}|-O(1)$
and at most
$(|V_{1}|-1)+|V_{0}|+(0.5+0.1\epsilon^{\prime})\cdot|V_{2}|<(4+0.4\epsilon^{\prime})\cdot|V_{0}|$.
In both cases, the first term is due to clique edges, the second term is due
to the edges connecting $V_{1}$ to $V_{0}$ (as determined by ${\tt nmE}$), and
the third term is due to the edges connecting $V_{1}$ to $V_{2}$ (as
determined by $B$). The crucial fact is that the linear degrees of ${\tt nmE}$
provides a non-trivial lower bound (of $\epsilon^{\prime}\cdot|V_{0}|$) on the
second term.

Hence, the difference in the degrees of vertices in the different parts is at
least $0.2\epsilon^{\prime}\cdot|V_{0}|-O(1)$, where the minimum is due to the
difference between the degrees of vertices in $V_{1}$ and the degrees of
vertices in $V_{0}$.

It follows that the symmetric difference between $G$ and $\mu(G)$ is at least
$(0.2\epsilon^{\prime}\cdot|V_{0}|-O(1))\cdot|T^{\prime}|=\Omega(|V|)\cdot|T^{\prime}|$,
since $|V_{0}|=\Omega(|V|)$ and $\epsilon^{\prime}=\Omega(1)$. Using the
case’s hypothesis, we have $|T^{\prime}|=\Omega(|V|)=\Omega(|T|)$, which means
that in this case the difference between $G$ and $\mu(G)$ is
$\Omega(|V|)\cdot|T|$.

We stress that the difference between $G$ and $\mu(G)$ is at least
$\Omega(|V|)\cdot|T^{\prime}|$ also if the case hypothesis does not hold.

Case 2:

$|T^{\prime}|<K$.

(This refers to the case that few vertices are mapped by $\mu$ to a different
part of the three-way partition $(V_{0},V_{1},V_{2})$ of $V$.)

For every $\sigma\in\\{0,1,2\\}$, let
$V^{\prime}_{\sigma}=V_{\sigma}\cap\mu(V_{\sigma})$ and
$T_{\sigma}=V^{\prime}_{\sigma}\cap T$. Indeed,
$(T^{\prime},T_{0},T_{1},T_{2})$ is a four-way partition of $T$. Note that the
size of the symmetric difference between $G$ and $\mu(G)$ is lower-bounded by

$\begin{array}[]{ll}&\left|\\{(v,u)\in V^{\prime}_{1}\times
V^{\prime}_{0}:{\tt nmE}(\mu(v),\mu(u))\neq{\tt nmE}(v,u)\\}\right|\\\
&+\;\left|\\{(v,u)\in V^{\prime}_{1}\times V^{\prime}_{2}:B(\mu(v),\mu(u))\neq
B(v,u)\\}\right|\\\ &+\;\left|\\{(v,u)\in V^{\prime}_{0}\times
V^{\prime}_{2}:B(\mu(v),\mu(u))\neq B(v,u)\\}\right|,\end{array}$ (24)

since, for any $(v,u)\in V^{\prime}_{1}\times V^{\prime}_{0}$, it holds that
$\mu(v)$ neighbors $\mu(u)$ in $G$ if and only if ${\tt
nmE}(\mu(v),\mu(u))=1$, whereas $\mu(v)$ neighbors $\mu(u)$ in $\mu(G)$ if and
only if $v$ neighbors $u$ in $G$ which holds if and only if ${\tt
nmE}(v,u)=1$. Ditto for the other two cases.

We consider two sub-cases according to whether or not $\min(|T_{0}|,|T_{1}|)$
is relatively large. The threshold for distinguishing these sub-cases is also
set to $K=(0.5-0.1\cdot\epsilon^{\prime})\cdot|V_{0}|/4$; note that
$K=\Omega(|V|)$ and $K>0.1\cdot|V_{0}|>2^{\ell-4}\geq 2^{k}$.

Case 2.1:

$\min(|T_{0}|,|T_{1}|)<K$.

In this case we shall use the quasi-orthogonality of $B$.

Suppose, without loss of generality, that $|T_{0}|\leq|T_{1}|$, which implies
$|T_{0}|<K$.

Depending on the relative sizes of $T_{1}$ and $T_{2}$, we shall use either
the quasi-orthogonal bipartite graph between $V_{1}$ and $V_{2}$ or the quasi-
orthogonal bipartite graph between $V_{2}$ and $V_{0}$.

  1. 1.

On the one hand, if $|T_{1}|>|T_{2}|$, then we consider the quasi-orthogonal
bipartite graph between $V_{1}$ and $V_{2}$. The contribution of each vertex
$v\in T_{1}$ to Eq. (24) equals

$\displaystyle|\\{u\in V^{\prime}_{2}:B(\mu(v),\mu(u))\neq B(v,u)\\}|$
$\displaystyle\geq$ $\displaystyle|\\{u\in V^{\prime}_{2}:B(\mu(v),u)\neq
B(v,u)\\}|-|T_{2}|$ $\displaystyle>$ $\displaystyle|\\{u\in
V_{2}:B(\mu(v),u)\neq B(v,u)\\}|-|T^{\prime}|-|T_{1}|$ $\displaystyle\geq$
$\displaystyle(0.5-0.1\cdot\epsilon^{\prime})\cdot|V_{2}|-K-|V_{0}|$
$\displaystyle>$ $\displaystyle 0.6\cdot|V_{0}|$

where the first inequality uses $\mu(u)=u$ for $u\in V^{\prime}_{2}\setminus
T_{2}$, the second inequality uses $|V^{\prime}_{0}|\geq|V_{0}|-|T^{\prime}|$
and the hypothesis $|T_{2}|<|T_{1}|$, the third inequality uses $\mu(v)\neq v$
along with the (second condition of) quasi-orthogonality of $B$ (and the
hypotheses $|T^{\prime}|<K$ and the fact that $|T_{1}|\leq|V_{1}|=|V_{0}|$),
and the fourth inequality uses $\epsilon^{\prime}<0.5$ and
$|V_{2}|>4\cdot|V_{0}|$. So the total contribution in this sub-case is
$|T_{1}|\cdot\Omega(|V|)\geq(|T|-|T^{\prime}|)\cdot\Omega(|V|)$, since
$|T_{1}|\geq\max(|T_{0}|,|T_{2}|)$ and
$|T_{0}|+|T_{1}|+|T_{2}|=|T|-|T^{\prime}|$.

  2. 2.

On the other hand, if $|T_{1}|\leq|T_{2}|$, then we consider the quasi-
orthogonal bipartite graph between $V_{2}$ and $V_{0}$. The contribution of
each vertex $v\in T_{2}$ to Eq. (24) equals

$\displaystyle|\\{u\in V^{\prime}_{0}:B(\mu(u),\mu(v))\neq B(u,v)\\}|$
$\displaystyle\geq$ $\displaystyle|\\{u\in V^{\prime}_{0}:B(u,\mu(v))\neq
B(u,v)\\}|-|T_{0}|$ $\displaystyle\geq$ $\displaystyle|\\{u\in
V_{0}:B(u,\mu(v))\neq B(u,v)\\}|-|T^{\prime}|-|T_{0}|$ $\displaystyle\geq$
$\displaystyle(0.5-0.1\cdot\epsilon^{\prime})\cdot|V_{0}|-2\cdot K$
$\displaystyle=$ $\displaystyle(0.5-0.1\cdot\epsilon^{\prime})\cdot|V_{0}|/2$

where the first inequality uses $\mu(u)=u$ for $u\in V^{\prime}_{0}\setminus
T_{0}$, the second inequality uses $|V^{\prime}_{0}|\geq|V_{0}|-|T^{\prime}|$,
the third inequality uses $\mu(v)\neq v$ along with the (second condition of)
quasi-orthogonality of $B$ (and the hypotheses regarding $|T^{\prime}|$ and
$|T_{0}|$), and the equality is due to
$K=(0.5-0.1\cdot\epsilon^{\prime})\cdot|V_{0}|/4$. So the total contribution
in this sub-case is
$|T_{2}|\cdot\Omega(|V|)\geq(|T|-|T^{\prime}|)\cdot\Omega(|V|)$, since
$|T_{2}|\geq|T_{1}|\geq|T_{0}|$.