s}{l_{i}}=\frac{D_{1}(\mathbf{L}_{i})\cdot s}{l_{i}}=1$

This completes the proof of the observation. ∎

Now we will apply the Birkhoff-Newmann theorem [13, 56], which states that the
doubly stochastic matrix $S$ defined above can be expressed as a weighted
average of permutation matrices. By translating the EMD expression from
$f_{\mathbf{XY}}$ to $S$ and using an averaging argument, we can infer that
there exists a permutation $\pi$ (among those in the representation of $S$)
such that $d_{H}(L^{\pi},M)$ is equal to $d_{EM}(D_{1},D_{2})$. This completes
the proof of the claim. ∎

Note that $D_{no}$ is supported over the set of distributions $D_{B}^{\sigma}$
for any permutation $\sigma$ and any matrix $B$ which consists of
$2^{2^{d-20}}$ columns of $A$. We will be done by showing that the Earth Mover
Distance between $D$ and $D_{B}^{\sigma}$ is at least $1/8$, where
$D\in\mathcal{P}_{\mathsf{vc}}$, $\sigma:[n]\rightarrow[n]$ is any
permutation, and $B$ is any matrix with $2^{2^{d-20}}$ columns.

Note that both $D$ and $D_{B}^{\sigma}$ admit respective corresponding
matrices $L$ and $M$, respectively, both of dimension $2^{d}\times n$, where
the rows of L are the vectors $\mathbf{V}_{i}$, and the rows of M are the
respective permutations of the vectors $\mathbf{W}_{i}$. By Claim 6.5, we note
that:

$d_{EM}(D_{B}^{\sigma},D)=\min_{\pi:[2^{d}]\rightarrow[2^{d}]}d_{H}(L^{\pi},M).$

The following claim will imply that $d_{EM}(D_{B}^{\sigma},D)\geq 1/8$.

######  Claim 6.7.

For any permutation $\pi:[2^{d}]\rightarrow[2^{d}]$, $d_{H}(L^{\pi},M)$ is at
least $1/8$.

###### Proof.

Let us partition the index set $[n]$ into $\ell^{\prime}$ many equivalence
classes $C_{1},\ldots,C_{\ell^{\prime}}$ such that two indices of $[n]$ belong
to the same equivalence class if the corresponding column vectors in $L^{\pi}$
are identical. Observe that

$d_{H}(L^{\pi},M)=\frac{\sum\limits_{i\in[\ell^{\prime}]}\sum\limits_{j\in
C_{i}}d_{H}(\mathbf{L}^{\pi}_{j},\mathbf{M}_{j})\cdot k}{k\cdot
n}=\frac{\sum\limits_{i\in[\ell^{\prime}]}\sum\limits_{j\in
C_{i}}d_{H}(\mathbf{L}^{\pi}_{j},\mathbf{M}_{j})}{n},$

where $\mathbf{L}^{\pi}_{j}$ and $\mathbf{M}_{j}$ denote the $j$-th column
vectors of $L^{\pi}$ and $M$, respectively.

Hence we will be done by showing $\sum\limits_{j\in
C_{i}}d_{H}\left(\mathbf{L}^{\pi}_{j},\mathbf{M}_{j}\right)\geq\frac{n}{8\ell^{\prime}},$
for every $i\in[\ell^{\prime}]$.

Note that $\left|C_{i}\right|=\frac{n}{\ell^{\prime}}$. Also, all the columns
in $\\{\mathbf{L}_{j}^{\pi}:j\in C_{i}\\}$ are identical. Consider a column
vector $\mathbf{v}\in\\{0,1\\}^{k}$. Observe that there can be at most
$\frac{n}{\ell}$ many columns in $\\{\mathbf{M}_{j}:j\in C_{i}\\}$ that are
$1/7$-close to $\mathbf{v}$. This follows from the construction of
$\mathcal{P}_{\mathsf{vc}}$, which implies that for every column
$\mathbf{M}_{j}$ of $M$, there are no more than $n/\ell-1$ many other columns
of $L^{\pi}$ whose distance from $\mathbf{M}_{j}$ is at most $2/7<1/3$.

So, in the expression $\sum\limits_{j\in
C_{i}}d_{H}\left(\mathbf{L}^{\pi}_{j},\mathbf{M}_{j}\right)$, there are at
least $(\frac{n}{\ell^{\prime}}-\frac{n}{\ell})$ many terms that are at least
$1/7$. Hence, $\sum\limits_{j\in
C_{i}}d_{H}\left(\mathbf{L}^{\pi}_{j},\mathbf{M}_{j}\right)\geq\ell^{\prime}\cdot\frac{1}{7}\left(\frac{n}{\ell^{\prime}}-\frac{n}{\ell}\right)\geq\frac{n}{8\ell^{\prime}}$.
∎

The above two claims conclude the proof of Lemma 6.3. ∎

######  Lemma 6.8 (Query complexity lower bound part of Theorem 6.1).

Any (non-adaptive) tester, that has sample and query access to either
$D_{yes}$ or $D_{no}$ and performs $2^{2^{d-\omega(1)}}$ queries, can not
distinguish between $D_{yes}$ and $D_{no}$.

###### Proof.

Let $A^{\prime}$ and $B^{\prime}$ be the matrices of dimension $k\times n$
such that the $i$-th row of $A^{\prime}$ corresponds to the vector
$\mathbf{V}_{i}^{\sigma}$ (for the permutation $\sigma$ drawn according to
$D_{yes}$) and the $i$-th row of $B^{\prime}$ corresponds to the vector
$\mathbf{W}_{i}^{\sigma}$ (for the permutation $\sigma$ drawn according to
$D_{no}$), where $i\in[k]$.

Let us divide the index set $[n]$ into $\ell$ equivalence classes
$C_{1},\ldots,C_{\ell}$ such that two indices belong to the same equivalence
class if the corresponding column vectors in $A^{\prime}$ are identical.
Similarly, let us divide the index set $[n]$ into $\ell^{\prime}$ equivalence
classes $C^{\prime}_{1},\ldots,C^{\prime}_{\ell^{\prime}}$ such that two
indices belong to the same equivalence class if the corresponding column
vectors in $B^{\prime}$ are identical.

Let $Q\subseteq[n]$ be the set of all distinct indices queried by the tester
to any sample (that is, the union of the sets $J_{1},\ldots,J_{s}$ as they
appear in Definition 3.11). If $\left|Q\right|=2^{2^{d-\omega(1)}}$, then the
probability that there exist two indices in $Q$ that belong to the same
$C_{i}$ or the same $C^{\prime}_{i}$ is $o(1)$. Observe that, conditioned on
the event that $Q$ does not contain two indices from the same equivalence
class $C_{i}$ or $C^{\prime}_{i}$, the distributions over the responses to the
queries of the tester are identical for both $D_{yes}$ and $D_{no}$. The
reason is that in both the cases of $D_{yes}$ and $D_{no}$, the distribution
over the responses is identical to the one derived from picking a uniformly
random subset of size $\left|Q\right|$ of the columns of the matrix $A$, and
taking uniformly independent samples of the rows of the resulting matrix. ∎

Now we will prove the sample complexity lower bound for testing
$\mathcal{P}_{\mathsf{vc}}$.

#### Sample complexity lower bound:

Let us define the second pair of hard distributions over distributions over
$\\{0,1\\}^{n}$, $D^{\prime}_{yes}$ and $D^{\prime}_{no}$.

#### Distribution $D^{\prime}_{yes}$:

Identically to $D_{yes}$ above, we choose a permutation
$\sigma:[n]\rightarrow[n]$ uniformly at random, and pick the distribution
$D_{A}^{\sigma}$ over $\\{0,1\\}^{n}$.

The distribution $D^{\prime}_{no}$ is constructed from the matrix $A$ used to
define $D^{\prime}_{yes}$ as follows:

#### Distribution $D^{\prime}_{no}$:

We first choose $k^{\prime}=2^{d-20}$ many row vectors uniformly at random
from $A$ and construct a matrix $B^{\prime}$ of dimension
$k^{\prime}\times\ell$. Let $D_{B^{\prime}}$ be the distribution supported
over the vectors
$\mathbf{W}^{\prime}_{1},\ldots,\mathbf{W}^{\prime}_{k^{\prime}}$ such that,
for every $i\in[k^{\prime}]$, the following hold:

  * •

$\mathbf{W}^{\prime}_{i}$ is the $n/\ell$ times blow-up of the $i$-th row of
$B^{\prime}$, that is, for $j\in[\ell]$ and $j^{\prime}$ with
$(j-1)\cdot\frac{n}{\ell}<j^{\prime}\leq j\cdot\frac{n}{\ell}$,
$\left(\mathbf{W}^{\prime}_{i}\right)_{j^{\prime}}=b_{ij}$, where $b_{ij}$
denotes the element of matrix $B^{\prime}$ present in the $i$-th row and the
$j$-th column.

  * •

$D_{no}(\mathbf{W}^{\prime}_{i})=\frac{1}{k^{\prime}}=\frac{1}{2^{d-20}}$.

We choose a permutation $\sigma:[n]\rightarrow[n]$ uniformly at random, and
pick the distribution $D_{B^{\prime}}^{\sigma}$ over $\\{0,1\\}^{n}$.

######  Lemma 6.9.

$D^{\prime}_{yes}$ is supported over $\mathcal{P}_{\mathsf{vc}}$ and
$D^{\prime}_{no}$ is supported over distributions that are $1/8$-far from
$\mathcal{P}_{\mathsf{vc}}$.

###### Proof.

Following the definition of $\mathcal{P}_{\mathsf{vc}}$ and
$D^{\prime}_{yes}$, it is clear that $D^{\prime}_{yes}$ is supported over
$\mathcal{P}_{\mathsf{vc}}$. To prove the claim about $D^{\prime}_{no}$, we
will apply Claim 6.5.

Note that $D^{\prime}_{no}$ is supported over the set of distributions
$D_{B^{\prime}}^{\sigma}$ for any permutation $\sigma$ and any matrix
$B^{\prime}$ which consists of $2^{d-20}$ rows of $A$. We will be done by
showing the Earth Mover Distance between $D$ and $D_{B^{\prime}}^{\sigma}$ is
at least $1/8$, where $D\in\mathcal{P}_{\mathsf{vc}}$ and
$\sigma:[n]\rightarrow[n]$ be any permutation, and $B^{\prime}$ is any matrix
with $2^{d-20}$ distinct rows.

Let $L$ and $M$ be corresponding matrices of $D$ and
$D_{B^{\prime}}^{\sigma}$, respectively, of dimension $k\times n$, where
$k=2^{d}$ (where the rows of $L$ are the vectors $\mathbf{V}_{i}$, and the
rows of $M$ are $2^{20}$-fold repetitions of the respective permutations of
the vectors $\mathbf{W^{\prime}}_{i}$). By Claim 6.5, we know that

$d_{EM}\left(D_{B^{\prime}}^{\sigma},D\right)=\min\limits_{\pi:[k]\rightarrow[k]}d_{H}(L^{\pi},M).$

Thus, the following claim will imply that
$d_{EM}(D_{B^{\prime}}^{\sigma},D)\geq 1/8$.

######  Claim 6.10.

For any permutation $\pi:[2^{d}]\rightarrow[2^{d}]$, $d_{H}(L^{\pi},M)$ is at
least $1/8$.

###### Proof.

Our proof will follow a similar vain to that of Claim 6.7. Let us first
partition the index set $[n]$ into $\ell^{\prime}$ many equivalence classes
$C_{1},\ldots,C_{\ell^{\prime}}$ such that two indices of $[n]$ belong to the
same equivalence class if the corresponding column vectors in $L^{\pi}$ are
identical. Observe that

$d_{H}(L^{\pi},M)=\frac{\sum\limits_{i\in[\ell^{\prime}]}\sum\limits_{j\in
C_{i}}d_{H}(\mathbf{L}^{\pi}_{j},\mathbf{M}_{j})\cdot k}{k\cdot
n}=\frac{\sum\limits_{i\in[\ell^{\prime}]}\sum\limits_{j\in
C_{i}}d_{H}(\mathbf{L}^{\pi}_{j},\mathbf{M}_{j})}{n},$

where $\mathbf{L}^{\pi}_{j}$ and $\mathbf{M}_{j}$ denote the $j$-th column
vectors of $L^{\pi}$ and $M$, respectively.

Since $B^{\prime}$ has only $2^{d-20}$ distinct rows, the number of its
equivalence classes is bounded by $\ell^{\prime}=2^{2^{d-20}}$. Note that
unlike the proof of the query lower bound, the sizes of the equivalence
classes here may be different from each other. Also, note that the sizes of
the equivalence classes of $L$ are $n/\ell$, as
$D\in\mathcal{P}_{\mathsf{vc}}$. Thus we have the following:

$d_{H}(L^{\pi},M)\geq\frac{1}{7}\cdot\frac{\sum_{i=1}^{\ell^{\prime}}\max\\{0,|C_{i}|-n/\ell\\}}{n}\geq\frac{1}{7}\cdot\left(1-\frac{1}{2^{10}}\right)\cdot
n>\frac{1}{8}n.$

The inequality follows from the facts that $\ell=2^{2^{d-10}}$ and
$\ell^{\prime}=2^{2^{d-20}}$, and the columns of $M$ corresponding to each
$C_{i}$ can be $1/7$-close to at most $n/\ell$ columns of $L$. ∎

This concludes the proof of Lemma 6.9. ∎

The sample lower bound for testing $\mathcal{P}_{\mathsf{vc}}$ now follows
from the following lemma.

######  Lemma 6.11 (Sample complexity lower bound part of Theorem 6.1).

Any tester that takes at most $2^{o(d)}$ samples from the input distribution
can not distinguish between the distributions $D^{\prime}_{yes}$ and
$D^{\prime}_{no}$.

###### Proof.

Let $\mathcal{S}$ be the set of samples taken by the algorithm. Note that if
$\left|\mathcal{S}\right|=2^{o(d)}$, then the probability that $\mathcal{S}$
contains two samples of the same $\mathbf{V}_{i}$ or the same
$\mathbf{W^{\prime}}_{i}$ is $o(1)$. Conditioned on the event that
$\mathcal{S}$ does not contain two samples from the same vector
($\mathbf{V}_{i}$ or $\mathbf{W^{\prime}}_{i}$), even if the tester queries
the samples of $\mathcal{S}$ in their entirety, the distributions over the
responses to the queries of the tester are identical for both
$D^{\prime}_{yes}$ and $D^{\prime}_{no}$. This follows from the fact that the
distribution over the responses is identical to a distribution obtained by
drawing uniformly without repetitions a sequence of row vectors from
$\mathbf{V}_{1},\ldots,\mathbf{V}_{2^{d}}$, and querying the row vectors
completely. This completes the proof. ∎

##  7 Exponential gap between adaptive and non-adaptive testers for general
properties

In this section, we prove that unlike the index-invariant properties, there
can be an exponential gap between the query complexities of adaptive and non-
adaptive algorithms for non-index-invariant properties. In Subsection 7.1 we
prove an exponential upper bound on the relation between the non-adaptive and
adaptive query complexities of general properties. In Subsection 7.2, we
provide an exponential separation between them, and also use the same method
to prove Proposition 1.5.

###  7.1 Relation between adaptive and non-adaptive testers for general
properties

Let us assume that $\mathcal{A}$ is the adaptive algorithm that
$\varepsilon$-tests $\mathcal{P}$ using $s$ samples
$\\{\mathbf{V}_{1},\ldots,\mathbf{V}_{s}\\}$ and $q$ queries, along with
tossing some random coins. Before directly proceeding to the description of
the non-adaptive algorithm, let us first consider the following observation.

######  Observation 7.1.

For any given outcome sequence of the random coin tosses of $\mathcal{A}$,
there are at most $2^{q}-1$ possible internal states of $\mathcal{A}$.

###### Proof.

Consider the $k$-th step of $\mathcal{A}$, where $\mathcal{A}$ queries the
$j_{k}$-th index of $\mathbf{V}_{i_{k}}$ for some $i_{k}\in[s]$,
$j_{k}\in[n]$, and $k\in[q]$. Note that ${i_{1}}$ and ${j_{1}}$ are functions
of only the random coins, and ${i_{k}}$ and ${j_{k}}$ are functions of the
random coins, as well as
$\mathbf{V}_{i_{1}}\mid_{j_{1}},\ldots,\mathbf{V}_{i_{k-1}}\mid_{j_{k-1}}$,
where $2\leq k\leq q$. Due to the $2^{k-1}$ possible values of
$\mathbf{V}_{i_{1}}\mid_{j_{1}},\ldots,\mathbf{V}_{i_{k-1}}\mid_{j_{{k-1}}}$,
there are $2^{k}$ possible states of the algorithm $\mathcal{A}$ at Step $k$,
for each $1\leq k\leq q$. Finally, the state of $\mathcal{A}$ depending on the
random coins and the values of
$\mathbf{V}_{i_{1}}\mid_{j_{1}},\ldots,\mathbf{V}_{i_{q}}\mid_{j_{q}}$ will
decide the final output. This implies that for any fixed set of outcomes of
the random coin tosses used by $\mathcal{A}$, there can be a total of at most
$\sum\limits_{i=0}^{q-1}2^{i}=2^{q}-1$ internal states, each making one query,
as well as $2^{q}$ final (non-query-making) states. ∎

Now we proceed to present the non-adaptive algorithm $\mathcal{A}^{\prime}$
that simulates $\mathcal{A}$ by using $s$ samples and at most $2^{q}$ queries.

######  Lemma 7.2.

Let $\mathcal{P}$ be any property that is $\varepsilon$-testable by an
adaptive algorithm using $s$ samples and $q$ queries. Then $\mathcal{P}$ can
be $\varepsilon$-tested by a non-adaptive algorithm using $s$ samples and at
most $2^{q}-1$ queries, where $s$ and $q$ are integers.

###### Proof.

Let $\mathcal{A}$ be the adaptive algorithm that $\varepsilon$-tests
$\mathcal{P}$ using $s$ samples $\\{\mathbf{V}_{1},\ldots,\mathbf{V}_{s}\\}$
and $q$ queries. Now we show that a non-adaptive algorithm
$\mathcal{A}^{\prime}$ exists that uses $s$ samples and makes at most
$2^{q}-1$ queries, such that the output distributions of $\mathcal{A}$ and
$\mathcal{A}^{\prime}$ are identical for any unknown distribution $D$.

The idea of $\mathcal{A}^{\prime}$ in a high level is to enumerate all
possible internal steps of $\mathcal{A}$, and list all possible queries
$\mathcal{Q}$ that might be performed by $\mathcal{A}$. Note that
$\mathcal{Q}$ depends on the random coins used by $\mathcal{A}$. We then query
all the indices of $\mathcal{Q}$ non-adaptively, and finally simulate
$\mathcal{A}$ using the full information at hand, with the same random coins
that were used to generate $\mathcal{Q}$. As $\mathcal{A}$ has query
complexity $q$, the number of possible internal states of $\mathcal{A}$ is at
most $2^{q}-1$, and the query complexity of $\mathcal{A}^{\prime}$ follows.
Now we formalize the above intuition below.

The algorithm $\mathcal{A}^{\prime}$ has two phases:

#### Phase 1:

  1. (i)

$\mathcal{A}^{\prime}$ first takes $s$ samples
$\mathbf{V}_{1},\ldots,\mathbf{V}_{s}$.

  2. (ii)

$\mathcal{A}^{\prime}$ now tosses some random coins (same as $\mathcal{A}$)
and determines the set of all possible indices $J_{i}$ of $\mathbf{V}_{i}$
that might be queried by $\mathcal{A}$, for every $i\in[s]$. The sets of
indices $J_{i}$’s are well defined after we fix the random coins, and follows
from Observation 7.1.

Thus at the end of Phase $1$, $\mathcal{A}^{\prime}$ has determined $s$ sets
of indices $J_{1},\ldots,J_{s}$ of the vectors
$\mathbf{V}_{1},\ldots,\mathbf{V}_{s}$ such that
$\sum\limits_{i=1}^{s}|J_{i}|\leq 2^{q}-1$. Now $\mathcal{A}^{\prime}$
proceeds to the second phase of the algorithm.

#### Phase 2:

  1. (i)

For every $i\in[s]$ and $j\in J_{i}$, query the $j$-th index of
$\mathbf{V}_{i}$, where $J_{i}$ denotes the set of indices of $\mathbf{V}_{i}$
that might be queried at the internal states of $\mathcal{A}$, determined in
Phase $1$.

  2. (ii)

Simulate the algorithm $\mathcal{A}$ using the same random coins used in Phase
$1$, and report Accept or Reject according to the output of $\mathcal{A}$.

Note that the set of random coins that are used to determine
$J_{1},\ldots,J_{s}$ in Step $(ii)$ of Phase $1$ of the algorithm are the same
random coins that are used to simulate $\mathcal{A}$ in Step $(ii)$ of Phase
$2$. Thus the correctness of $\mathcal{A}^{\prime}$ follows from to the
correctness of $\mathcal{A}$ along with Observation 7.1. ∎

###  7.2 Exponential separation between adaptive and non-adaptive query
complexities

Now we prove that the gap of Lemma 7.2 is almost tight, in the sense that
there exists a property such that the adaptive and non-adaptive query
complexities for testing it are exponentially separated.

Before proceeding to the proof, let us consider any property $\mathcal{P}$ of
strings of length $n$ over the alphabet $\\{0,1\\}$. Now we describe a related
property $1_{\mathcal{P}}$ over distributions as follows:

#### Property $1_{\mathcal{P}}$:

For any distribution $D\in 1_{\mathcal{P}}$, the size of the support of $D$ is
$1$, and the single string in the support of $D$ satisfies $\mathcal{P}$.

Let us first recall the following result from [37], which states that
$\widetilde{\mathcal{O}}(\frac{1}{\varepsilon})$ queries are enough to
$\varepsilon$-test whether any distribution has support size $1$.

######  Lemma 7.3 (Restatement of Corollary $2.3.1$ of [37]).

There exists a non-adaptive algorithm that $\varepsilon$-tests whether an
unknown distribution $D$ has support size $1$ and uses
$\widetilde{\mathcal{O}}(\frac{1}{\varepsilon})$ queries, for any
$\varepsilon\in(0,1)$.

We now prove that the query complexity of $\varepsilon$-testing
$1_{\mathcal{P}}$ is at least the query complexity of $\varepsilon$-testing
$\mathcal{P}$, and can be at most the query complexity of
$\frac{\varepsilon}{2}$-testing of $\mathcal{P}$, along with an additional
additive factor of $\widetilde{\mathcal{O}}(\frac{1}{\varepsilon})$ for
testing whether the distribution has support size $1$. The result is formally
stated as follows:

######  Lemma 7.4.

Let $q_{N}$ and $q_{A}$ denote the non-adaptive and adaptive query
complexities for $\varepsilon$-testing $\mathcal{P}$, respectively. Similarly,
let $Q_{N}$ and $Q_{A}$ denote the non-adaptive and adaptive query
complexities of $\varepsilon$-testing $1_{\mathcal{P}}$, respectively. Then
the following hold:

  1. 1.

$q_{A}(\varepsilon)\leq
Q_{A}(\varepsilon)\leq\widetilde{\mathcal{O}}(\frac{1}{\varepsilon})+\mathcal{O}\left(q_{A}(\frac{\varepsilon}{2})\right)$
191919We are using $\mathcal{O}(\cdot)$ as we are amplifying the success
probability of the tester for the property $\mathcal{P}$ to $9/10$ as compared
to the usual success probability of $2/3$..

  2. 2.

$q_{N}(\varepsilon)\leq
Q_{N}(\varepsilon)\leq\widetilde{\mathcal{O}}(\frac{1}{\varepsilon})+\mathcal{O}\left(q_{N}(\frac{\varepsilon}{2})\right)$.

###### Proof.

We prove here (1), and omit the nearly identical proof of (2).

#### Proof of $q_{A}(\varepsilon)\leq Q_{A}(\varepsilon)$:

Consider an adaptive algorithm $\mathcal{A}$ that $\varepsilon$-tests
$1_{\mathcal{P}}$ by using $Q_{A}(\varepsilon)$ queries. We construct an
algorithm $\mathcal{A}^{\prime}$ that $\varepsilon$-tests $\mathcal{P}$ using
the same number of queries. Let $\mathbf{V}$ be the unknown string of length
$n$, where we want to test whether $\mathbf{V}\in\mathcal{P}$ or $\mathbf{V}$
is $\varepsilon$-far from $\mathcal{P}$.

Let us define an unknown distribution $D^{\prime}$ (over the Hamming cube
$\\{0,1\\}^{n}$) such that we want to distinguish whether $D^{\prime}\in
1_{\mathcal{P}}$ or $D^{\prime}$ is $\varepsilon$-far from $1_{\mathcal{P}}$.
The distribution $D^{\prime}$ is defined as follows:

$D^{\prime}(\mathbf{X})=\left\\{\begin{array}[]{ll}1&\mathbf{X}=\mathbf{V}\\\
\vspace{3pt}0&\mbox{otherwise}\end{array}\right.$

Observe that $\mathbf{V}\in\mathcal{P}$ if and only if $D^{\prime}\in
1_{\mathcal{P}}$. Similarly, it is not hard to see that $\mathbf{V}$ is
$\varepsilon$-far from $\mathcal{P}$ if and only if $D^{\prime}$ is
$\varepsilon$-far from $1_{\mathcal{P}}$. We simulate the algorithm
$\mathcal{A}$ by $\mathcal{A}^{\prime}$ as follows: when $\mathcal{A}$ takes a
sample, $\mathcal{A}^{\prime}$ does nothing, and when $\mathcal{A}$ queries an
index $i\in[n]$ of any sample, $\mathcal{A}^{\prime}$ queries the index $i$ of
$\mathbf{V}$. Finally, $\mathcal{A}^{\prime}$ provides the output received
from the simulation of $\mathcal{A}$.

From the description, it is clear that $\mathcal{A}^{\prime}$ performs exactly
$Q_{\mathcal{A}}(\varepsilon)$ queries and is indeed simulated by running
$\mathcal{A}$ over $D^{\prime}$.

#### Proof of
$Q_{A}(\varepsilon)\leq\widetilde{{\mathcal{O}}}\left(\frac{1}{\varepsilon}\right)+\mathcal{O}\left(q_{A}(\frac{\varepsilon}{2})\right)$:

Let us consider an adaptive algorithm $\mathcal{A}_{1}$ that
$\frac{\varepsilon}{2}$-tests $\mathcal{P}$ using
$\mathcal{O}\left(q_{A}(\frac{\varepsilon}{2})\right)$ queries to the unknown
string $\mathbf{X}\in\\{0,1\\}^{n}$, with success probability at least
$\frac{9}{10}$. Now we design an adaptive algorithm $\mathcal{A}_{1}^{\prime}$
that $\varepsilon$-tests $1_{\mathcal{P}}$ using
$\widetilde{{\mathcal{O}}}\left(\frac{1}{\varepsilon}\right)+\mathcal{O}\left(q_{A}(\frac{\varepsilon}{2})\right)$
many queries.

#### Algorithm $\mathcal{A}_{1}^{\prime}$:

Assume that $D$ is the distribution that we want to $\varepsilon$-test for
$1_{\mathcal{P}}$. The algorithm $\mathcal{A}_{1}^{\prime}$ performs the
following steps:

  1. (i)

Run the tester corresponding to Lemma 7.3 to $\frac{\varepsilon}{20}$-test
whether $D$ has support size $1$, with success probability at least
$\frac{9}{10}$. If the tester decides that $D$ has support size $1$, then go
to the next step. Otherwise, Reject.

  2. (ii)

Take one more sample from $D$ and let it be $\mathbf{U}\in\\{0,1\\}^{n}$. Run
algorithm $\mathcal{A}_{1}$ to $\frac{\varepsilon}{2}$-test $\mathcal{P}$
considering $\mathbf{X}=\mathbf{U}$ as the unknown string. If
$\mathcal{A}_{1}$ accepts, Accept. Otherwise Reject.

Note that the query complexity for performing Step $(i)$ is
$\widetilde{\mathcal{O}}(\frac{1}{\varepsilon})$, which follows from Lemma
7.3. Additionally, the number of queries performed in Step $(ii)$ is
$\mathcal{O}\left(q_{A}(\frac{\varepsilon}{2})\right)$, which follows from the
assertion of the lemma. Thus, the algorithm $\mathcal{A}_{1}^{\prime}$
performs
$\widetilde{\mathcal{O}}(\frac{1}{\varepsilon})+\mathcal{O}\left(q_{A}(\frac{\varepsilon}{2})\right)$
many queries in total.

Now we will argue the correctness of $\mathcal{A}_{1}^{\prime}$. For
completeness, assume that $D\in 1_{\mathcal{P}}$. Let
$\mathbf{V}\in\\{0,1\\}^{n}$ be the string such that $D(\mathbf{V})=1$ and
$\mathbf{V}\in\mathcal{P}$. Note that, by Lemma 7.3,
$\mathcal{A}_{1}^{\prime}$ proceeds to Step $(ii)$ with probability at least
$\frac{9}{10}$. In Step $(ii)$, $\mathcal{A}^{\prime}$ sets
$\mathbf{U}=\mathbf{V}$, and runs algorithm $\mathcal{A}_{1}$ to
$\frac{\varepsilon}{2}$-test $\mathcal{P}$ considering $\mathbf{X}=\mathbf{V}$
as the unknown string. Since $\mathbf{V}\in\mathcal{P}$, by the assumption on
the algorithm $\mathcal{A}_{1}$, $\mathcal{A}_{1}^{\prime}$ accepts with
probability at least $\frac{9}{10}$, given that $\mathcal{A}_{1}^{\prime}$
does not report Reject in Step $(i)$. Thus, by the union bound,
$\mathcal{A}_{1}^{\prime}$ accepts $D$ with probability at least
$\frac{4}{5}$.

Now consider the case where $D$ is $\varepsilon$-far from $1_{\mathcal{P}}$.
If $D$ is $\frac{\varepsilon}{20}$-far from having support size $1$,
$\mathcal{A}_{1}^{\prime}$ reports Reject in Step $(i)$ with probability at
least $\frac{9}{10}$, and we are done. So, assume that $D$ is
$\frac{\varepsilon}{20}$-close to having support size $1$. Then there exists a
distribution $D^{\prime}$ with support size $1$, and the distance between $D$
and $D^{\prime}$ is at most $\frac{\varepsilon}{20}$. Let us assume that
$D^{\prime}$ is supported on the string $\mathbf{V}$. By the Markov
inequality, this implies that with probability at least $\frac{4}{5}$, a
string $\mathbf{U}$ sampled according $D$ will be
$\frac{9\varepsilon}{20}$-close to $\mathbf{V}$.

  1. (i)

If $\mathbf{V}$ is $\frac{19\varepsilon}{20}$-close to $\mathcal{P}$, using
the triangle inequality, this implies that $D$ is $\varepsilon$-close to
$1_{\mathcal{P}}$, which is a contradiction.

  2. (ii)

Now consider the case where $\mathbf{V}$ is $\frac{19\varepsilon}{20}$-far
from $\mathcal{P}$. Recall that with probability at least $\frac{4}{5}$, the
sample $\mathbf{U}$ taken at Step (ii) above is
$\frac{9\varepsilon}{20}$-close to $\mathbf{V}$. As we are considering the
case where $\mathbf{V}$ is $\frac{19\varepsilon}{20}$-far from $\mathcal{P}$,
using the triangle inequality, $\mathbf{U}$ is $\frac{\varepsilon}{2}$-far
from $\mathcal{P}$ with the same probability. In this case, the algorithm will
Reject in Step $(ii)$, with probability at least $\frac{9}{10}$. Together,
this implies that the algorithm will Reject the distribution $D$, with
probability at least $\frac{7}{10}$.

∎

In the following, we will construct the property $\mathcal{P}_{Pal}$ of
strings over the alphabet $\\{0,1,2,3\\}$. It will then be encoded as a
property of strings over $\\{0,1\\}$ by using two bits per letter.

#### Property $\mathcal{P}_{Pal}$:

A string $\mathbf{S}$ of length $n$ is in $\mathcal{P}_{Pal}$ if
$\mathbf{S}=\mathbf{X}\mathbf{Y}$, where $\mathbf{X}$ is a palindrome over the
alphabet $\\{0,1\\}$, and $\mathbf{Y}$ is a palindrome over the alphabet
$\\{2,3\\}$.

There is an exponential gap between the query complexities of adaptive and
non-adaptive algorithms to $\varepsilon$-test $\mathcal{P}_{Pal}$. The result
is stated as follows:

######  Lemma 7.5.

There exists an adaptive algorithm that $\varepsilon$-tests
$\mathcal{P}_{Pal}$ by performing $\mathcal{O}(\log n)$ queries for any
$\varepsilon\in(0,1)$. However, there exists an $\varepsilon\in(0,1)$ such
that $\Omega(\sqrt{n})$ non-adaptive queries are necessary to
$\varepsilon$-test $\mathcal{P}_{Pal}$.

###### Proof.

The lower bound proof (using Yao’s lemma), which we omit here, is nearly
identical to the one from [5] (see Theorem $2$ therein).

Let us assume that $\mathbf{V}$ is the string that we want to
$\varepsilon$-test for $\mathcal{P}_{Pal}$. The adaptive algorithm to
$\varepsilon$-test $\mathcal{P}_{Pal}$ uses binary search, and is described
below:

  1. (i)

Use binary search for an index of $\mathbf{V}$ that has “value 1.5” (which is
not present in the input). This returns an index $0\leq i\leq n$, such that
(a) $\mathbf{V}_{i}\in\\{0,1\\}$ unless $i=0$, and (b)
$\mathbf{V}_{i+1}\in\\{2,3\\}$ unless $i=n$.

  2. (ii)

Repeat $\mathcal{O}(\frac{1}{\varepsilon})$ times:

    1. (a)

Sample an index $j\in[n]$ uniformly at random.

    2. (b)

If $j\leq i$, then query $\mathbf{V}_{j}$ and $\mathbf{V}_{i+1-j}$. Reject if
they are not both equal to the same value in $\\{0,1\\}$.

    3. (c)

Otherwise query $\mathbf{V}_{j}$ and $\mathbf{V}_{n+i+1-j}$. Reject if they
are not both equal to the same value in $\\{2,3\\}$.

  3. (iii)

If the input has not been rejected till now, Accept.

We first argue the completeness of the algorithm. Assume that $\mathbf{V}$ is
a string such that $\mathbf{V}\in\mathcal{P}_{Pal}$, and $i$ is the index
returned by Step $(i)$ of the algorithm. As $\mathbf{V}=\mathbf{XY}$ for some
palindrome $\mathbf{X}$ over $\\{0,1\\}$ and palindrome $\mathbf{Y}$ over
$\\{2,3\\}$, the index $i$ will be equal to $\left|\mathbf{X}\right|$. This
implies that the algorithm will Accept $\mathbf{V}$ with probability $1$.

Now consider the case where $\mathbf{V}$ is $\varepsilon$-far from
$\mathcal{P}_{Pal}$. We call an index $j$ _violating_ if it does not satisfy
the condition appearing either in Step (ii)(b) or Step (ii)(c) above, where
$i$ is the index returned in Step $(i)$. The number of violating indices is at
least $\varepsilon n$, because otherwise we can change the violating indices
such that the modified input is a string of the form $\mathbf{XY}$ following
the definition of $\mathcal{P}_{Pal}$, where $\left|\mathbf{X}\right|=i$.
Since the loop in Step (ii) runs for $\mathcal{O}(\frac{1}{\varepsilon})$
times, we conclude that with probability at least $\frac{2}{3}$ at least one
such violating index will be found. So, the algorithm will Reject $\mathbf{V}$
with probability at least $\frac{2}{3}$. ∎

Now we are ready to formally state and prove the main result of this section.

######  Proposition 7.6.

There exists a property of distributions over strings that can be
$\varepsilon$-tested adaptively using $\mathcal{O}(\log n)$ queries for any
$\varepsilon\in(0,1)$, but $\Omega(\sqrt{n})$ queries are necessary for any
non-adaptive algorithm to $\varepsilon$-test it for some
$\varepsilon\in(0,1)$.

###### Proof.

Consider the property $1_{\mathcal{P}_{Pal}}$. From Lemma 7.5, we know that
$q_{A}(\frac{\varepsilon}{2})=\mathcal{O}(\log n)$, for any fixed
$\varepsilon\in(0,1)$. Using the upper bound of Lemma 7.4, we conclude that
$Q_{A}(\varepsilon)=\mathcal{O}(\log n)$, for any fixed $\varepsilon\in(0,1)$,
ignoring the additive $\widetilde{\mathcal{O}}(\frac{1}{\varepsilon})$ term.

On the other hand, according to Lemma 7.5,
$q_{N}(\varepsilon)=\Omega(\sqrt{n})$ for some $\varepsilon\in(0,1)$. Thus,
following Lemma 7.4, we conclude that $Q_{N}(\varepsilon)=\Omega(\sqrt{n})$
holds for some $\varepsilon\in(0,1)$. Together, Proposition 7.6 follows. ∎

Now we present a sketch of a proof of Proposition 1.5, which shows that for a
property to be constantly testable, it is not sufficient that the property has
constant VC-dimension, unless it is index-invariant as well.

######  Proposition 7.7 (Restatement of Proposition 1.5).

There exists a non-index-invariant property $\mathcal{P}$ such that any
distribution $D\in\mathcal{P}$ has VC-dimension $O(1)$ and the following
holds. There exists a fixed $\varepsilon>0$, such that distinguishing whether
$D\in\mathcal{P}$ or $D$ is $\varepsilon$-far from $\mathcal{P}$, requires
$\Omega(n)$ queries, where the distributions in the property $\mathcal{P}$ are
defined over the $n$-dimensional Hamming cube $\\{0,1\\}^{n}$.

###### Proof.

Note that the VC-dimension of $1_{\mathcal{P}}$ is $0$, where
$1_{\mathcal{P}}$ is the property corresponding to $\mathcal{P}$ as defined
before. String properties which are hard to test, for which there is a fixed
$\varepsilon>0$ such that $\varepsilon$-testing them requires $\Omega(n)$
queries, are known to exist. Examples are properties studied in the work of
Ben-Eliezer, Fischer, Levi and Rothblum [10], and in the work of Ben-Sasson,
Harsha and Raskhodnikova [12]. Defining $1_{\mathcal{P}}$ for such a property
$\mathcal{P}$ provides us the example proving Proposition 7.7. ∎

##  8 Quadratic gap between adaptive and non-adaptive testers for index-
invariant properties

In this section, we first prove Theorem 1.6 in Subsection 8.1, that is, there
can be at most a quadratic gap between the query complexities of adaptive and
non-adaptive algorithms for testing index-invariant properties. Then in
Subsection 8.2, we prove Theorem 1.7, that is, we demonstrate a quadratic
separation between them, which is one of the main results of the paper and the
main content of this section.

###  8.1 Quadratic relation between adaptive and non-adaptive testers for
index-invariant properties

######  Theorem 8.1 (Restatement of Theorem 1.6).

Let $\mathcal{P}$ be any index-invariant property that is
$\varepsilon$-testable by an adaptive algorithm using $s$ samples and $q$
queries. Then $\mathcal{P}$ can be $\varepsilon$-tested by a non-adaptive
algorithm using $s$ samples and $sq\leq q^{2}$ queries, where $s$ and $q$ are
integers.

###### Proof.

The main idea of the proof is to start with an adaptive algorithm
$\mathcal{A}$ as stated above, and then argue for another semi-adaptive
algorithm $\mathcal{A}^{\prime}$ with sample complexity $s$ but query
complexity $qs$, such that the output distributions of $\mathcal{A}$ and
$\mathcal{A}^{\prime}$ are the same for any unknown distribution $D$. Finally,
we construct a non-adaptive algorithm $\mathcal{A}^{\prime\prime}$ such that
(i) the sample and query complexities of $\mathcal{A}^{\prime\prime}$ are the
same as that of $\mathcal{A}^{\prime}$, and (ii) the probability bounds of
accepting and rejecting distributions depending on their distances to
$\mathcal{P}$ are preserved from $\mathcal{A}^{\prime}$ to
$\mathcal{A}^{\prime\prime}$. Now we proceed to formalize this argument.

Let $\mathcal{A}$ be the adaptive algorithm that $\varepsilon$-tests
$\mathcal{P}$ using $s$ samples $\\{\mathbf{V}_{1},\ldots,\mathbf{V}_{s}\\}$
and $q$ queries. Now we show that a two phase algorithm $\mathcal{A}^{\prime}$
exists that takes $s$ samples $\\{\mathbf{V}_{1},\ldots,\mathbf{V}_{s}\\}$ and
proceeds as follows:

#### Phase 1:

In this phase, $\mathcal{A}^{\prime}$ queries in an adaptive fashion. If
$\mathcal{A}$ queries the $j_{k}$-th index of $\mathbf{V}_{i_{k}}$ at its
$k$-th step, for some $i_{k}\in[s]$ and $j_{k}\in[n]$, then we perform the
following steps:

  1. (i)

If $\mathcal{A}^{\prime}$ has queried the $j_{k}$-th index of all the samples
before this step, then we reuse the queried value.

  2. (ii)

Otherwise, we query the $j_{k}$-th index from all the samples
$\\{\mathbf{V}_{1},\ldots,\mathbf{V}_{s}\\}$.

#### Phase 2:

Let $\mathcal{Q}\subset[n]$ be the set of indices queried by
$\mathcal{A}^{\prime}$ while running the $q$ querying steps of $\mathcal{A}$.
If $\left|\mathcal{Q}\right|<q$, we arbitrarily pick
$t=q-\left|\mathcal{Q}\right|$ distinct indices
$\\{j^{\prime}_{1},\ldots,j^{\prime}_{t}\\}$, disjoint from the set of indices
$\mathcal{Q}$. We query the set of indices
${j^{\prime}_{1},\ldots,j^{\prime}_{t}}$ from the entire set of sampled
vectors $\mathbf{V}_{1},\ldots,\mathbf{V}_{s}$.

The output (Accept or Reject) of $\mathcal{A}^{\prime}$ is finally set to that
of $\mathcal{A}$, and in particular depends only on the answers to the queries
made in the first phase.

Now we have the following observation regarding the query complexity of
$\mathcal{A}^{\prime}$, which will be used to argue the query complexity of
the non-adaptive algorithm later.

######  Observation 8.2.

$\mathcal{A}^{\prime}$ uses $s$ samples and performs exactly $qs$ queries.
Moreover, for any distribution $D$, the output distribution of
$\mathcal{A}^{\prime}$ is the same as that of $\mathcal{A}$.

Let us assume that $\mathcal{A}^{\prime}$ proceeds in $q$ steps by querying
indices $\ell_{1},\ldots,\ell_{q}\in[n]$ in each of the $s$ samples
$\mathbf{V}_{1},\ldots,\mathbf{V}_{s}$ (when the unknown distribution is $D$).
Equivalently, we can think that the algorithm proceeds in $q$ steps, where in
Step $k$ ($k\in[q]$), we query the $\ell_{k}$-th index of
$\\{\mathbf{V}_{1},\ldots,\mathbf{V}_{s}\\}$, such that $\ell_{k}$ depends on
$\ell_{1},\ldots,\ell_{k-1}$, where $2\leq k\leq q$.

Let us now consider an uniformly random permutation $\sigma:[n]\rightarrow[n]$
(unknown to $\mathcal{A}^{\prime}$). Assume that the unknown distribution is
$D_{\sigma}$ instead of $D$. As $\mathcal{P}$ is index-invariant, we can
assume that the algorithm $\mathcal{A}^{\prime}$ runs on $D_{\sigma}$ for $q$
steps as follows. In Step $k$, $\mathcal{A}^{\prime}$ queries the
$\sigma(\ell_{k})$-th index of each of the $s$ samples, for $k\in[q]$. Now we
have the following observation regarding the distribution of the indices
queried, which follows from $\sigma$ being uniformly random.

######  Observation 8.3.

$\sigma(\ell_{1})$ is uniformly distributed over $[n]$, and $\sigma(\ell_{k})$
is uniformly distributed over
$[n]\setminus\\{\sigma(\ell_{1}),\ldots,\sigma(\ell_{k-1})\\}$, where $2\leq
k\leq q$. Moreover, this holds even if we condition on the values
$\ell_{1},\ldots,\ell_{k}$ as well as
$\sigma(\ell_{1}),\ldots,\sigma(\ell_{k-1})$.

Now the algorithm $\mathcal{A}^{\prime\prime}$ works as follows:

  * •

First take a uniformly random permutation $\sigma:[n]\rightarrow[n]$.

  * •

Run $\mathcal{A}^{\prime}$ over $D_{\sigma}$ instead of $D$.

From the above description, it does not immediately follow that
$\mathcal{A}^{\prime\prime}$ is a non-adaptive algorithm. But from the
description along with Observation 8.3, it follows that
$\mathcal{A}^{\prime\prime}$ is the same as the following algorithm:

  * •

First take $s$ samples $\mathbf{V}_{1},\ldots,\mathbf{V}_{s}$, and also pick a
uniformly random non-repeating sequence of $q$ indices
$r_{1},\ldots,r_{q}\in[n]$.

  * •

Run $\mathcal{A}^{\prime}$ such that, for every $i\in[q]$, when
$\mathcal{A}^{\prime}$ is about to query $\ell_{i}$, query $r_{i}$ from all
samples instead. That is, we assume $r_{i}$ to be the value of
$\sigma(\ell_{i})$.

The sample complexity and query complexity of algorithm
$\mathcal{A}^{\prime\prime}$ are $s$ and $qs$, respectively, which follows
from Observation 8.2 and Observation 8.3. The correctness of the algorithm
follows from Observation 8.2 and Observation 8.3 along with the fact that
$\mathcal{P}$ is index-invariant. This completes the proof of Theorem 8.1. ∎

###  8.2 Preliminaries towards proving a quadratic separation result

In this subsection, we present some preliminary results required to prove that
Theorem 1.6 is almost tight, that is, there exists an index-invariant property
for which there is a nearly quadratic gap between the query complexities of
adaptive and non-adaptive testers. The result is formally stated as follows.

######  Theorem 8.4 (Restatement of Theorem 1.7).

There exists an index-invariant property $\mathcal{P}_{\mathrm{Gap}}$ that can
be $\varepsilon$-tested adaptively using $\widetilde{{\mathcal{O}}}(n)$
queries for any $\varepsilon\in(0,1)$, while there exists an
$\varepsilon\in(0,1)$ for which $\widetilde{\Omega}(n^{2})$ queries are
necessary for any non-adaptive $\varepsilon$-tester.

In what follows throughout this section, we assume that the integer $n$ is of
the form $n=2^{l}$ for some integer $l$, and that $k=\mathcal{O}(l)$ is
another integer. We denote vectors in $\\{0,1\\}^{N}$ by capital bold letters
(for example $\mathbf{X}\in\\{0,1\\}^{N}$) and vectors in $\\{0,1\\}^{n}$ by
small bold letters (for example $\mathbf{x}\in\\{0,1\\}^{n}$). For two vectors
$\mathbf{X},\mathbf{Y}\in\\{0,1\\}^{N}$, we will use
$\delta_{H}(\mathbf{X},\mathbf{Y})=N\cdot d_{H}(\mathbf{X},\mathbf{Y})$ to
denote the absolute Hamming distance between $\mathbf{X}$ and $\mathbf{Y}$.

To construct the property $\mathcal{P}_{\mathrm{Gap}}$ (as stated in Theorem
8.4), we define two encodings
$\mathrm{SE}:\\{0,1\\}^{\ell}\rightarrow\\{0,1\\}^{k}$ and
$\mathrm{GE}:[n]^{m}\rightarrow[n]^{n}$ 202020SE stands for Secret Encoding,
and GE stands for General Encoding.. The encodings $\mathrm{GE}$ and
$\mathrm{SE}$ follow from the construction of a Probabilistically Checkable
Unveiling of a Shared Secret (PCUSS) in [10]. We can also construct such a
function $\mathrm{GE}$ using the Reed-Solomon code, where we will assume that
$n$ is a prime power and use polynomials of degree $m-1$ over the field
$\mbox{{\sc GL}}(n)$ for $m=\Theta(n)$ 212121$\mbox{{\sc GL}}(n)$ stands for
the finite field with $n$ elements..

#### Function SE:

We will use a function $\mathrm{SE}$ of the form
$\mathrm{SE}:\\{0,1\\}^{l}\times\\{0,1\\}\rightarrow\\{0,1\\}^{k}$, where $l$
and $k$ are the integers defined above. In fact, $\mathrm{SE}$ takes an
integer $i\in[n]$ in its Boolean encoding as an $l$ bit Boolean string and a
“secret” bit $a\in\\{0,1\\}$, and will output a Boolean string of length $k$.
$\mathrm{SE}$ will have the following properties for some constant
$\zeta\in(0,1/2)$.

  1. (i)

Let $i,i^{\prime}\in[n]$ be two integers encoded as binary strings of length
$l$ 222222Binary strings of length $\log n$ can actually encode only integers
from $\\{0,\ldots,n-1\\}$, so we use the encoding of $0$ for the value $n$.,
and $a,a^{\prime}\in\\{0,1\\}$. If $(i,a)\neq(i^{\prime},a^{\prime})$, then
$\delta_{H}(\mathrm{SE}(i,a),\mathrm{SE}(i^{\prime},a^{\prime}))\geq\zeta\cdot
k$.

  2. (ii)

Let $a\in\\{0,1\\}$ be a fixed bit, and suppose that $i$ is an integer chosen
uniformly at random from $[n]$. Then for any set of indices $I\subset[k]$ such
that $\left|I\right|\leq\zeta\cdot k$, the restriction
$\mathrm{SE}(i,a)\mid_{I}$ is uniformly distributed over
$\\{0,1\\}^{\left|I\right|}$.

#### Function GE:

For our construction, we will use another function $\mathrm{GE}$ of the form
$\mathrm{GE}:[n]^{m}\rightarrow[n]^{n}$, where $n,m\in\mathbb{N}$ with the
following properties for the same constant $\zeta\in(0,1/2)$ as above.

  1. (i)

Let $\mathbf{z},\mathbf{z^{\prime}}\in[n]^{m}$ be two strings such that
$\mathbf{z}\neq\mathbf{z^{\prime}}$. For any two such strings $\mathbf{z}$ and
$\mathbf{z^{\prime}}$,
$\delta_{H}(\mathrm{GE}(\mathbf{z}),\mathrm{GE}(\mathbf{z^{\prime}}))=|\\{i:\mathrm{GE}(\mathbf{z})_{i}\neq\mathrm{GE}(\mathbf{z^{\prime}})_{i}\\}|\geq\zeta\cdot
n$.

  2. (ii)

Consider a string $\mathbf{z}\in[n]^{m}$ chosen uniformly at random. For any
set of indices $I\subset[n]$ such that $\left|I\right|\leq\zeta\cdot n$,
$\mathrm{GE}(\mathbf{z})\mid_{I}$ is uniformly distributed over
$[n]^{\left|I\right|}$.

From now on, we will use the following notation in this subsection: Let
$n\in\mathbb{N}$ be such that $n=2^{l}$ for some integer $l$,
$k=\mathcal{O}(l)$ and $\zeta\in(0,1/2)$ as above, $b=\lfloor\log(\lceil\log
kn\rceil)\rfloor+1$, $N=1+b+kn$ and $\alpha=1/\log n$. Note that in particular
$N=\mathcal{O}(n\log n)$. For a vector $\mathbf{X}\in\\{0,1\\}^{N}$ and a
permutation $\pi:[N]\rightarrow[N]$, $\mathbf{X}_{\pi}$ denotes the vector
obtained from $\mathbf{X}$ by permuting the indices of $\mathbf{X}$ with
$\pi$, that is,
$\mathbf{X}_{\pi}=(\mathbf{X}_{\pi(1)},\ldots,\mathbf{X}_{\pi(N)})$.

Let $B$ be the sequence of integers $B=\\{2,\ldots,b+1\\}$, and for every
$j\in[n]$, let $C_{j}$ denote the sequence of integers
$C_{j}=\\{b+2+k(j-1),\ldots,b+1+kj\\}$. For a sequence of integers $A$ and a
vector $\mathbf{X}$, we denote by $\mathbf{X}\mid_{A}$ the vector obtained by
projecting $\mathbf{X}$ onto the set of indices of $A$ preserving the sequence
order. For a sequence $A\subseteq[N]$ and a permutation
$\pi:[N]\rightarrow[N]$, we denote by $\pi(A)$ the sequence obtained after
permuting every element of $A$ with respect to the permutation $\pi$, that is,
if $A=(a_{1},\ldots,a_{l})$, then $\pi(A)=(\pi(a_{1}),\ldots,\pi(a_{l}))$. In
particular, we have $\mathbf{X}_{\pi}\mid_{A}=\mathbf{X}\mid_{\pi(A)}$. By
abuse of notation and for simplicity, for a set of integers $A$ and a vector
$\mathbf{X}$, we denote by $\mathbf{X}\mid_{A}$ the vector obtained by
projecting $\mathbf{X}$ onto the set of indices of $A$, whenever the ordering
in which we consider the indices in $A$ will be clear from the context 232323A
common scenario is when the indexes of $A$ are considered as a monotone
increasing sequence..

In the following, we use string notation. For example,
$\mathbf{1}^{k}\mathbf{0}^{k}$ denotes the vector in $\\{0,1\\}^{2k}$ whose
first $k$ coordinates are $1$ and whose last $k$ coordinates are $0$. Now we
formally define the notion of encoding of a vector which will be crucially
used to define $\mathcal{P}_{\mathrm{Gap}}$.

######  Definition 8.5 (Encoding of a vector).

Let $n,k,b\in\mathbb{N},N=1+b+kn$, and
$\mathbf{x}=(\mathbf{x}_{1},\ldots,\mathbf{x}_{n})\in\\{0,1\\}^{n}$ and
$\mathbf{Y}\in\\{0,1\\}^{N}$ be two vectors. $\mathbf{Y}$ is said to be an
_encoding_ of $\mathbf{x}$ with respect to the functions
$\mathrm{SE}:\\{0,1\\}^{l}\times\\{0,1\\}\rightarrow\\{0,1\\}^{k}$ and
$\mathrm{GE}:[n]^{m}\rightarrow[n]^{n}$ if the following hold:

  1. (i)

The first index of $\mathbf{Y}$ is $0$.

  2. (ii)

$\mathbf{Y}\mid_{B}$ is the all-$1$ vector.

  3. (iii)

$\mathbf{Y}\mid_{[N]\setminus\\{1\\}\cup B}$ is of the form
$\mathrm{SE}(\mathrm{GE}(\mathbf{z})_{1},\mathbf{x}_{1})\ldots\mathrm{SE}(\mathrm{GE}(\mathbf{z})_{n},\mathbf{x}_{n})$
for some string $\mathbf{z}\in[n]^{m}$. In other words,
$\mathbf{Y}\mid_{C_{j}}=\mathrm{SE}(\mathrm{GE}(\mathbf{z})_{j},\mathbf{x}_{j})$
for every $j\in[n]$.

For ease of presentation, we will denote this encoding by $\mathrm{FE}$, that
is, $\mathrm{FE}:[n]^{m}\times\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{N}$ is the
function 242424FE stands for Final Encoding. such that
$\mathrm{FE}(\mathbf{z},\mathbf{x})=\mathbf{0}(\mathbf{1}^{b})\mathrm{SE}(\mathrm{GE}(\mathbf{z})_{1},\mathbf{x}_{1})\ldots\mathrm{SE}(\mathrm{GE}(\mathbf{z})_{n},\mathbf{x}_{n})$,
for $\mathbf{z}\in[n]^{m}$ and
$\mathbf{x}=(\mathbf{x}_{1},\ldots,\mathbf{x}_{n})\in\\{0,1\\}^{n}$. We also
say that $\mathbf{X}\in\\{0,1\\}^{N}$ is a _valid encoding_ of some
$\mathbf{x}\in\\{0,1\\}^{n}$, if there exists some $\mathbf{z}\in[n]^{m}$ for
which $\mathbf{X}=\mathrm{FE}(\mathbf{z},\mathbf{x})$. The image of FE will be
called the set of all valid encodings.

Now let us infer two properties of the function $\mathrm{FE}$, which will be
crucial to our proofs, as stated in the following two claims. These properties
of FE are analogous to the properties of SE and GE. As FE is formed by
combining SE and GE, the proofs of these observations use their respective
properties.

The following observation, particularly Items (i) and (ii), will allow us to
prove that certain distributions are indeed far from the property
$\mathcal{P}_{\mathrm{Gap}}$ (to be defined later) in the EMD metric. Item
(iii) will be useful to prove the soundness of our adaptive algorithm in
Subsection 8.4, and in particular in Lemma 8.28.

######  Observation 8.6 (Distance properties of $\mathrm{FE}$).

Let $\mathrm{FE}:[n]^{m}\times\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{N}$ be the
function from Definition 8.5. Then $\mathrm{FE}$ has the following properties:

  1. (i)

Let $\mathbf{x},\mathbf{x^{\prime}}\in\\{0,1\\}^{n}$ be any two strings and
$\mathbf{z},\mathbf{z^{\prime}}\in[n]^{m}$ be two vectors such that
$\mathbf{z}\neq\mathbf{z^{\prime}}$. Then
$\delta_{H}(\mathrm{FE}(\mathbf{z},\mathbf{x}),\mathrm{FE}(\mathbf{z^{\prime}},\mathbf{x^{\prime}}))\geq\zeta^{2}\cdot
N/2$ holds.

  2. (ii)

Let $\mathbf{z},\mathbf{z^{\prime}}\in[n]^{m}$ be any two strings, and
$\mathbf{x},\mathbf{x^{\prime}}\in\\{0,1\\}^{n}$ be two other strings such
that $\mathbf{x}\neq\mathbf{x^{\prime}}$. Then
$\delta_{H}(\mathrm{FE}(\mathbf{z},\mathbf{x}),\mathrm{FE}(\mathbf{z^{\prime}},\mathbf{x^{\prime}}))\geq\zeta
k\cdot\delta_{H}(\mathbf{x},\mathbf{x^{\prime}})$.

  3. (iii)

Let $\mathbf{x},\mathbf{x^{\prime}}\in\\{0,1\\}^{n}$ be two strings and
$\mathbf{z}\in[n]^{m}$ be a vector. Then
$\delta_{H}(\mathrm{FE}(\mathbf{z},\mathbf{x}),\mathrm{FE}(\mathbf{z},\mathbf{x^{\prime}}))\leq
k\cdot\delta_{H}(\mathbf{x},\mathbf{x^{\prime}})$, and in particular
$d_{H}(\mathrm{FE}(\mathbf{z},\mathbf{x}),\mathrm{FE}(\mathbf{z},\mathbf{x^{\prime}}))\leq
d_{H}(\mathbf{x},\mathbf{x^{\prime}})$ holds.

###### Proof.

We prove each item separately below.

  1. (i)

Following the properties of $\mathrm{GE}$ (Property (i)), for
$\mathbf{z}\neq\mathbf{z^{\prime}}$, we know that
$\delta_{H}(\mathrm{GE}(\mathbf{z}),\mathrm{GE}(\mathbf{z^{\prime}}))\geq\zeta\cdot
n\geq\zeta N/2k$. That is, the number of indices $j\in[n]$ such that
$\mathrm{GE}(\mathbf{z})_{j}\neq\mathrm{GE}(\mathbf{z^{\prime}})_{j}$, is at
least $\zeta N/2k$. For every index $j\in[n]$ such that
$\mathrm{GE}(\mathbf{z})_{j}\neq\mathrm{GE}(\mathbf{z^{\prime}})_{j}$, we can
say that
$\delta_{H}(\mathrm{SE}(\mathrm{GE}(\mathbf{z})_{j},\mathbf{x}_{j}),\mathrm{SE}(\mathrm{GE}(\mathbf{z^{\prime}})_{j},\mathbf{x^{\prime}}_{j}))\geq\zeta\cdot
k$. This is due to Property (i) of $\mathrm{SE}$. Hence,

$\displaystyle\delta_{H}(\mathrm{FE}{\left(\mathbf{z},\mathbf{x}\right)},\mathrm{FE}{\left(\mathbf{z}^{\prime},\mathbf{x^{\prime}}\right)})$
$\displaystyle\geq$
$\displaystyle\sum\limits_{j\in[n]:\mathbf{z}_{j}\neq\mathbf{z^{\prime}}_{j}}\delta_{H}(\mathrm{SE}(\mathrm{GE}(\mathbf{z})_{j},\mathbf{x}_{j}),\mathrm{SE}(\mathrm{GE}(\mathbf{z})_{j},\mathbf{x^{\prime}}_{j}))$
$\displaystyle\geq$ $\displaystyle\zeta N/2k\cdot\zeta k=\zeta^{2}\cdot N/2.$

  2. (ii)

Consider two strings $\mathbf{x},\mathbf{x^{\prime}}\in\\{0,1\\}^{n}$ such
that $\mathbf{x}\neq\mathbf{x^{\prime}}$. Using Property (i) of $\mathrm{SE}$,
we know that
$\delta_{H}(\mathrm{SE}(\mathrm{GE}(\mathbf{z})_{j},\mathbf{x}_{j}),\mathrm{SE}(\mathrm{GE}(\mathbf{z})_{j},\mathbf{x^{\prime}}_{j}))\geq\zeta\cdot
k$ for every $j$ for which $\mathbf{x}_{j}\neq\mathbf{x^{\prime}}_{j}$. Note
that the number of such indices $j$ is
$\delta_{H}(\mathbf{x},\mathbf{x^{\prime}})$. Summing over them, we have the
result.

  3. (iii)

Consider any two strings $\mathbf{x},\mathbf{x^{\prime}}\in\\{0,1\\}^{n}$.
Observe that

$\delta_{H}(\mathrm{FE}{\left(\mathbf{z},\mathbf{x}\right)},\mathrm{FE}{\left(\mathbf{z},\mathbf{x^{\prime}}\right)})=\sum\limits_{j\in[n]}\delta_{H}(\mathrm{SE}(\mathrm{GE}(\mathbf{z})_{j},\mathbf{x}_{j}),\mathrm{SE}(\mathrm{GE}(\mathbf{z})_{j},\mathbf{x^{\prime}}_{j})).$

Note that
$\delta_{H}(\mathrm{SE}(\mathrm{GE}(\mathbf{z})_{j},\mathbf{x}_{j}),\mathrm{SE}(\mathrm{GE}(\mathbf{z})_{j},\mathbf{x^{\prime}}_{j}))$
is at most $k$ for every $j\in[n]$. Moreover,
$\delta_{H}(\mathrm{SE}(\mathrm{GE}(\mathbf{z})_{j},\mathbf{x}_{j}),\mathrm{SE}(\mathrm{GE}(\mathbf{z})_{j},\mathbf{x^{\prime}}_{j}))=0$
for every $j\in[n]$ with $\mathbf{x}_{j}=\mathbf{x}_{j}^{\prime}$. Since the
number of indices $j$ such that $\mathbf{x}_{j}\neq\mathbf{x}_{j}^{\prime}$ is
$\delta_{H}(\mathbf{x},\mathbf{x^{\prime}})$, we conclude the following:

$\delta_{H}(\mathrm{FE}{\left(\mathbf{z},\mathbf{x}\right)},\mathrm{FE}{\left(\mathbf{z},\mathbf{x^{\prime}}\right)})\leq
k\cdot\delta_{H}(\mathbf{x},\mathbf{x^{\prime}}).$

Note that this immediately implies
$d_{H}(\mathrm{FE}{\left(\mathbf{z},\mathbf{x}\right)},\mathrm{FE}{\left(\mathbf{z},\mathbf{x^{\prime}}\right)})\leq
d_{H}(\mathbf{x},\mathbf{x^{\prime}}).~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\qed$

The following lemma will provide us a way to construct distributions that
cannot be easily distinguished using non-adaptive queries (following a
uniformly random index-permutation which we will deploy).

######  Lemma 8.7 (Projection property of $\mathrm{FE}$).

Consider a fixed vector $\mathbf{x}\in\\{0,1\\}^{n}$, and let
$\mathbf{z}\in[n]^{m}$ be a string chosen uniformly at random. For any set of
indices $Q\subseteq[N]$ such that $\left|Q\right|\leq\zeta\cdot N/2k$ and
$|Q\cap C_{j}|\leq\zeta\cdot k$ for every $j\in[n]$, the restriction of
$\mathrm{FE}(\mathbf{z},\mathbf{x})\mid_{Q\setminus[b+1]}$ is uniformly
distributed over $\\{0,1\\}^{|Q\setminus[b+1]|}$ 252525Recall that the
restriction $\mathrm{FE}(\mathbf{z},\mathbf{x})\mid_{[b+1]}$ is always the
vector $\mathbf{0}\mathbf{1}^{b}$..

###### Proof.

For the set of indices $Q$, consider the set $J=\\{j:Q\cap
C_{j}\neq\emptyset\\}$. From the statement of the lemma, we know that
$\left|Q\cap C_{j}\right|\leq\zeta\cdot k$ for every $j\in J$. Noting that
$\left|J\right|\leq\left|Q\right|\leq\zeta\cdot n$, if we consider the
restriction $\mathrm{GE}(\mathbf{z})\mid_{J}$, following Property (ii) of the
function $\mathrm{GE}$, we know that $\mathrm{GE}(\mathbf{z})\mid_{J}$ is
uniformly distributed over $[n]^{\left|J\right|}$.

Now when we call $\mathrm{SE}(i_{j},\mathbf{x}_{j})$ with $i_{j}\in[n]$
obtained from $\mathrm{GE}(\mathbf{z})\mid_{J}$, following the above argument,
we can say that $i_{j}$ has been chosen uniformly at random from $[n]$ (and
independently from the other $i_{j^{\prime}}$). Since $\left|Q\cap
C_{j}\right|\leq\zeta\cdot k$, applying Property (ii) of the function
$\mathrm{SE}$, we know that the corresponding restriction of
$\mathrm{SE}(i_{j},\mathbf{x}_{j})$ will be uniformly distributed over
$\\{0,1\\}^{\left|Q\cap C_{j}\right|}$. Since
$\mathrm{FE}(\mathbf{z},\mathbf{x})=\mathbf{0}(\mathbf{1}^{b})\mathrm{SE}(\mathrm{GE}(\mathbf{z})_{1},\mathbf{x}_{1})\ldots\mathrm{SE}(\mathrm{GE}(\mathbf{z})_{n},\mathbf{x}_{n})$,
combining the above arguments, we conclude that
$\mathrm{FE}(\mathbf{z},\mathbf{x})\mid_{Q\setminus[b+1]}$ is uniformly
distributed over $\\{0,1\\}^{|Q\setminus[b+1]|}$. ∎

Now we are ready to formally define the property, first constructing a non-
index-invariant version to be used in the next index-invariant definition.

#### Property $\mathcal{P}^{0}_{\mathrm{Gap}}$:

A distribution $D$ over $\\{0,1\\}^{N}$ is in $\mathcal{P}^{0}_{\mathrm{Gap}}$
if and only if $D$ satisfies the following conditions:

  1. (i)

$D(\mathbf{U})=\alpha$, where $\mathbf{U}=\mathbf{1}\mathbf{0}^{N-1}$ is the
indicator vector for the index $1$.

  2. (ii)

Consider the set of vectors
$\mathcal{S}=\\{\mathbf{V}_{1},\ldots,\mathbf{V}_{b}\\}$ in $\\{0,1\\}^{N}$
such that for every $i\in[b]$, the $i$-th vector $\mathbf{V}_{i}$ is of the
form $\mathbf{1}^{i+1}\mathbf{0}^{N-1-i}$. Note that
$\mathbf{V}_{i}\mid_{B}=1^{i}0^{b-i}$ for $B=\\{2,\ldots,b+1\\}$. We require
that $D(\mathbf{V}_{i})=\alpha/b$ for every $i\in[b]$.

  3. (iii)

Consider the set of vectors
$\mathcal{T}=\\{\mathbf{W}_{0},\ldots,\mathbf{W}_{\lceil\log kn\rceil-1}\\}$
(disjoint from $\mathcal{S}$) in $\\{0,1\\}^{N}$ such that for every
$\mathbf{W}_{i}\in\mathcal{T}$, $\mathbf{W}_{i}$ is of the form
$\mathbf{0}(b(i))(\mathbf{0}^{2^{i}}\mathbf{1}^{2^{i}})^{kn/2^{i+1}}$, where
$b(i)$ denotes the length $b$ binary representation of $i$ 262626If
$kn/2^{i+1}$ is not an integer, we trim the rightmost copy of
$\mathbf{0}^{2^{i}}\mathbf{1}^{2^{i}}$ so that the total length of
“$(\mathbf{0}^{2^{i}}\mathbf{1}^{2^{i}})^{kn/2^{i+1}}$” is exactly $kn$.. Note
that for $i=b+2+j$, with $0\leq j\leq kn-1$, the sequence
$(\mathbf{W}_{0})_{i},\ldots,(\mathbf{W}_{{(\lceil\log kn\rceil-1)}})_{i}$
holds the binary representation of $j$. Also, note that there is an one-to-one
correspondence between $\mathbf{W}_{i}\mid_{B}$ and
$\mathbf{W}_{i}\mid_{[N]\setminus\\{B\\}\cup\\{1\\}}$. We require that
$D(\mathbf{W}_{i})=\alpha/|\mathcal{T}|$ for every
$\mathbf{W}_{i}\in\mathcal{T}$.

  4. (iv)

$\mbox{Supp}(D)\setminus(\\{\mathbf{U}\\}\cup\mathcal{S}\cup\mathcal{T})$
consists of valid encodings of at most $n$ vectors from $\\{0,1\\}^{n}$ with
respect to the functions
$\mathrm{SE}:\\{0,1\\}^{l}\times\\{0,1\\}\rightarrow\\{0,1\\}^{k}$ and
$\mathrm{GE}:[n]^{m}\rightarrow[n]^{n}$, for the integers $l,m,k\in\mathbb{N}$
as defined in Definition 8.5. That is, there exist vectors
$\mathbf{x}_{1},\ldots,\mathbf{x}_{n}\in\\{0,1\\}^{n}$ for which
$\mbox{Supp}(D)\setminus(\\{\mathbf{U}\\}\cup\mathcal{S}\cup\mathcal{T})\subseteq\\{\mathrm{FE}(\mathbf{z},\mathbf{x}_{i}):\mathbf{z}\in[n]^{m},i\in[n]\\}$.
Note that for $D$ to be a distribution, we must have
$D(\mbox{Supp}(D)\setminus(\\{\mathbf{U}\\}\cup\mathcal{S}\cup\mathcal{T}))=1-3\alpha$.

#### Property $\mathcal{P}_{\mathrm{Gap}}$:

A distribution $D$ over $\\{0,1\\}^{N}$ is said to be in the property
$\mathcal{P}_{\mathrm{Gap}}$ if $D_{\pi}$ is in
$\mathcal{P}^{0}_{\mathrm{Gap}}$ for some permutation $\pi:[N]\rightarrow[N]$.

######  Remark 4 (Intuition behind the definition of
$\mathcal{P}_{\mathrm{Gap}}$).

If a distribution $D$ is in $\mathcal{P}_{\mathrm{Gap}}^{0}$, then we can
easily check (by querying the indexes in $B$) whether a sample from $D$ would
be equal to $\mathrm{FE}(\mathbf{z},\mathbf{x})$ for some
$\mathbf{z}\in[n]^{m}$ and $\mathbf{x}\in\\{0,1\\}^{n}$. In that case,
individual bits of $\mathbf{x}$ can be decoded by querying the appropriate
$C_{j}$ and then passed to a tester of distributions over $\\{0,1\\}^{n}$.

On the other hand, if we take a uniformly random permutation of such a
distribution $D$, which keeps it in $\mathcal{P}_{\mathrm{Gap}}$ (though no
longer in $\mathcal{P}_{\mathrm{Gap}}^{0}$), a non-adaptive algorithm will
need many queries to capture sufficiently many bits from any $C_{j}$, and this
will enable us to fully hide the identity of $\mathbf{x}$ if fewer queries are
performed.

By contrast, an adaptive tester will use relatively few samples that are
queried in their entirety to obtain the (permutations of the) special vectors
in Items (i) to (iii) of the definition of $\mathcal{P}_{\mathrm{Gap}}^{0}$,
from which it will be able to fully learn the index-permutation applied to the
distribution, and continue to successfully decode individual bits. A few
further samples queried in their entirety will ensure that there is very
little total weight on vectors that are neither special vectors nor equal to
$\mathrm{FE}(\mathbf{z},\mathbf{x})$ for some $\mathbf{z}\in[n]^{m}$ and
$\mathbf{x}\in\\{0,1\\}^{n}$.

#### Known useful results about support estimation:

Now we state a lemma which will be required later to describe the adaptive
tester for $\mathcal{P}_{\mathrm{Gap}}$. Informally, it says that whether a
distribution $D$ over $\\{0,1\\}^{n}$ has support size $s$ or is
$\varepsilon$-far from any such distribution, can be tested by taking
$\widetilde{{\mathcal{O}}}(s)$ samples from $D$, and performing
$\widetilde{{\mathcal{O}}}(s)$ queries on them.

######  Lemma 8.8 (Support size estimation, Theorem $1.9$ and Corollary $2.3$
of [37] restated).

There exists an algorithm Supp-Est$(s,\varepsilon)$ that uses
$\widetilde{{\mathcal{O}}}(s/\varepsilon^{2})$ queries to an unknown
distribution $D$ defined over $\\{0,1\\}^{n}$, and with probability at least
$\frac{9}{10}$ distinguishes whether $D$ has at most $s$ elements in its
support or $D$ is $\varepsilon$-far from all such distributions with support
size at most $s$.

We will also use a lower bound on the support size estimation problem to prove
the lower bound on non-adaptive testers for testing
$\mathcal{P}_{\mathrm{Gap}}$. Informally speaking, given a distribution $D$
over $\\{1,\ldots,2n\\}$, in order to distinguish in the traditional (non-
huge-object) model whether the size of the support of $D$ is $n$, or $D$ is
far from all such distributions, $\Omega(\frac{n}{\log n})$ samples are
necessary. More formally, we have the following theorem.

######  Theorem 8.9 (Support Estimation Lower bound, Corollary $9$ of [57]
restated).

There exist two distributions $D_{yes}^{\mathrm{Supp}}$ and
$D_{no}^{\mathrm{Supp}}$ over distributions over $\\{1,\ldots,2n\\}$, and an
$\eta\in(0,1/8)$ such that the following holds:

  1. (i)

The probability mass of every element in the support of
$D_{yes}^{\mathrm{Supp}}$ as well as $D_{no}^{\mathrm{Supp}}$ is a multiple of
$1/2n$.

  2. (ii)

$D_{yes}^{\mathrm{Supp}}$ is supported over distributions whose support size
is $n$.

  3. (iii)

$D_{no}^{\mathrm{Supp}}$ is supported over distributions whose support size is
at least $(1+2\eta)n$, and in particular are $\eta$-far in variation distance
from any distribution defined over $\\{1,\ldots,2n\\}$ whose support size is
$(1+2\eta)n$.

  4. (iv)

If a sequence of $o(\frac{n}{\log n})$ samples from a distribution are drawn
according to either $D_{yes}^{\mathrm{Supp}}$ or $D_{no}^{\mathrm{Supp}}$, the
resulting distributions over the sample sequences are $1/4$-close to each
other.

We present an adaptive algorithm to test $\mathcal{P}_{\mathrm{Gap}}$ in
Subsection 8.4 and we prove the lower bound for non-adaptive testers in
Subsection 8.5. In Subsection 8.3, we describe a subroutine to determine the
unknown permutation that will be used in our adaptive algorithm in Subsection
8.4.

###  8.3 Determining the permutation $\pi$

Here we design an algorithm that, given a distribution
$D\in\mathcal{P}_{\mathrm{Gap}}$, can learn with high probability the
permutation $\pi$ for which $D_{\pi}\in P^{0}_{\mathrm{Gap}}$.

The crux of the algorithm is that if $D\in\mathcal{P}_{\mathrm{Gap}}$, then
there exist $\mathbf{U}^{\prime}=\mathbf{U}_{\pi}\in\\{0,1\\}^{n}$,
$\mathcal{S}^{\prime}=\mathcal{S}_{\pi}=\\{\mathbf{\mathbf{V}}_{i}^{\prime}=(\mathbf{V}_{i})_{\pi}:i\in[b]\\}$
and
$\mathcal{T}^{\prime}=\mathcal{T}_{\pi}=\\{\mathbf{W}_{j}^{\prime}=(\mathbf{W}_{j})_{\pi}:j\in\\{0\\}\cup[\lceil\log
kn\rceil]-1\\}$ in the support of $D$ such that
$D(\mathbf{U}^{\prime})=\alpha$, $D(\mathbf{V}_{i}^{\prime})=\alpha/b$ for
every $i\in[b]$ and $D(\mathbf{W}_{j}^{\prime})=\alpha/\lceil\log kn\rceil$.
Note that $\mathbf{U}$, $\mathcal{S}$ and $\mathcal{T}$ are as defined in the
property $\mathcal{P}_{\mathrm{Gap}}^{0}$.

The main observation is that, if we are given the set of special vectors
$\\{\mathbf{U^{\prime}}\\}\cup\mathcal{S}^{\prime}\cup\mathcal{T}^{\prime}$,
then we can determine the permutation $\pi$. Our algorithm can find
$\mathbf{U}^{\prime},\mathcal{S}^{\prime}$ and $\mathcal{T}^{\prime}$ with
high probability, if they exist, by taking
$\mathcal{O}(\log^{2}N/\alpha)=\mathcal{O}(\log^{2}n/\alpha)$ samples and
reading them in their entirety. This is due to the fact that the probability
mass of every vector in the set of special vectors is at least
$\Omega(\alpha/\log n)$.

The algorithm is described in the following subroutine Find-Permutation (see
Algorithm 3) 272727This algorithm is not adaptive in itself, but its output is
used adaptively in the testing algorithm described later..

1

2

Input: Sample and Query access to a distribution $D$ over $\\{0,1\\}^{N}$.

Output: Either a permutation $\pi:[N]\rightarrow[N]$, or Fail.

(i)

First take a multi-set $\mathcal{X}$ of $\mathcal{O}(\log^{2}N/\alpha)$
samples from $D$, and query all the entries of the sampled vectors of
$\mathcal{X}$ to know the vectors of $\mathcal{X}$ completely.

3(ii)

Find the set of distinct vectors in $\mathcal{X}$ that have exactly one $1$.
If no such vector exists or there

is more than one such vector, Fail. Otherwise, denote by $\mathbf{U^{\prime}}$
the vector that has exactly one $1$, and denote the corresponding index by
$i^{*}$. Set $\pi(i^{*})=1$, and proceed to the next step.

* (iii)

Find the set of distinct vectors
$\mathcal{S}^{\prime}\subseteq\mathcal{X}\setminus\\{\mathbf{U^{\prime}}\\}$
such that every vector in $\mathcal{S}^{\prime}$ has $1$ at the index $i^{*}$
and has at least another $1$ among other indices. If no such vector exists, or
$\left|\mathcal{S}^{\prime}\right|\neq b$, Fail. Otherwise, if the vectors of
$\mathcal{S}^{\prime}$ form a chain
$\mathbf{V}^{\prime}_{1},\ldots,\mathbf{V}^{\prime}_{b}$, where
$\mathbf{V}^{\prime}_{j}$ has exactly $j+1$ many $1$, then set
$\pi(i_{j})=j+1$, where $i_{j}$ is the index where $\mathbf{V}^{\prime}_{j}$
has $1$, but $\mathbf{V}^{\prime}_{j-1}$ has $0$ there, for every $j\in[b]$
(denoting $\mathbf{V^{\prime}}_{0}=\mathbf{U^{\prime}}$ for the purpose here).
Also, set $B^{\prime}=(i_{1},\ldots,i_{b})$. If $\mathcal{S}^{\prime}$ does
not form a chain $\mathbf{V}^{\prime}_{1},\ldots,\mathbf{V}^{\prime}_{b}$ as
mentioned above, Fail.

* (iv)

Let $\mathcal{T}^{\prime}\subseteq\mathcal{X}$ be the set of distinct vectors
such that every vector in $\mathcal{T}^{\prime}$ has $0$ at the index $i^{*}$,
and does not have $1$ in all indices of $B^{\prime}$. If no such vector
exists, Fail. For every $j$, denote by $\mathbf{W}^{\prime}_{j}$ the vector in
$\mathcal{T}^{\prime}$ for which
$\mathbf{W}^{\prime}_{j}\mid_{B^{\prime}}=b(j)$, where $b(j)$ denotes the
binary representation of $j$. For every $j\in\\{0\\}\cup[\lceil\log
kn\rceil-1]$, if either there are no vectors
$\mathbf{W}^{\prime}_{j}\in\mathcal{T}^{\prime}$ or there is more than one
distinct vector with $\mathbf{W^{\prime}}_{j}\mid_{B^{\prime}}=b(j)$, Fail.
Also, if there is any vector in
$\mathbf{W}^{\prime}_{j}\in\mathcal{T}^{\prime}$ such that
$\mathbf{W}^{\prime}_{j}\mid_{B^{\prime}}=b(j)$ for $\log kn\leq j<2^{b}-1$,
Fail.

* (v)

For any $i\in[N]\setminus(\\{i^{*}\\}\cup B^{\prime})$, let $l_{i}$ be the
integer with binary representation
$(\mathbf{W^{\prime}}_{0})_{i},\ldots,(\mathbf{W^{\prime}}_{\lceil\log
kn\rceil-1})_{i}$. Set $\pi(i)=b+2+l_{i}$ for each
$i\in[N]\setminus(\\{i^{*}\\}\cup B^{\prime})$. If $\pi$ is not a permutation
of $[N]$, Fail.

* 4(vi)

Take another multi-set $\mathcal{X}^{\prime}$ of
$\mathcal{O}(\log^{2}N/\alpha)$ samples from $D$, and query all the entries of
the sampled vectors of $\mathcal{X}^{\prime}$ to know the vectors of
$\mathcal{X}^{\prime}$ completely. Let $\mathcal{Y}$ be the set of vectors in

5 $\mathcal{X}^{\prime}$ such that
$\mathcal{Y}=\\{\mathbf{Z}\in\mathcal{X}^{\prime}:\mathbf{Z}\mid_{{\\{i^{*}\\}\cup
B^{\prime}}}\neq\mathbf{0}\mathbf{1}^{b}\\}$. If
$\left|\mathcal{Y}\right|/\left|\mathcal{X}^{\prime}\right|>4\alpha$, Fail.
Otherwise, output

6 the permutation $\pi$.

Algorithm 3 Find-Permutation

Let us start by analyzing the query complexity of Find-Permutation.

######  Lemma 8.10 (Query complexity of Find-Permutation).

The query complexity of the above defined Find-Permutation is
$\widetilde{{\mathcal{O}}}(N)$.

###### Proof.

Note that Find-Permutation takes a multi-set $\mathcal{X}$ of
$\mathcal{O}(\log^{2}N/\alpha)$ samples from $D$ in Step (i), and queries them
completely. So, Find-Permutation performs $\mathcal{O}(N\log^{2}N/\alpha)$
queries in Step (i). Find-Permutation does not perform any new queries in Step
(ii), Step (iii), Step (iv) and Step (v). Finally, Find-Permutation takes
another multi-set $\mathcal{X}^{\prime}$ of $\mathcal{O}(\log^{2}N/\alpha)$
samples from $D$ and queries them completely, similar to Step (i). Recalling
that $\alpha=1/\log n$, the query complexity of Find-Permutation is
$\widetilde{{\mathcal{O}}}(N)=\widetilde{{\mathcal{O}}}(n)$ in total. ∎

Now we proceed to prove the correctness of Find-Permutation.

######  Lemma 8.11 (Guarantee when $D\in\mathcal{P}_{\mathrm{Gap}}$).

If $D$ is a distribution defined over $\\{0,1\\}^{N}$ such that
$D\in\mathcal{P}_{\mathrm{Gap}}$, then with probability at least $9/10$, Find-
Permutation reports the permutation $\pi$ such that
$D_{\pi}\in\mathcal{P}_{\mathrm{Gap}}^{0}$.

We prove the above lemma by a series of intermediate lemmas. In the following
lemmas, we consider $\mathbf{U}$, $\mathcal{S}$ and $\mathcal{T}$ as per the
definition of $\mathcal{P}^{0}_{\mathrm{Gap}}$. Also, consider the permutation
$\pi$ such that $D_{\pi}\in\mathcal{P}_{\mathrm{Gap}}$.

######  Lemma 8.12 (Correctly finding $\pi^{-1}(1)$).

With probability at least $1-1/N^{3}$, $\mathcal{X}$ will contain the vector
$\mathbf{U^{\prime}}$ for which $\mathbf{U^{\prime}}_{\pi}=\mathbf{U}$, and
$i^{*}=\pi^{-1}(1)$ will be identified correctly. Moreover, Find-Permutation
proceeds to Step (iii).

###### Proof.

By the definition of $\mathcal{P}^{0}_{\mathrm{Gap}}$, the vector
$\mathbf{U^{\prime}}$ is the only vector in the support of $D$ containing a
single $1$. Since $D(\mathbf{U^{\prime}})=D(\mathbf{U}_{\pi^{-1}(1)})=\alpha$,
and we are taking $\left|\mathcal{X}\right|$ many samples from $D$, the
probability that $\mathbf{U^{\prime}}$ will not appear in $\mathcal{X}$ is at
most $(1-\alpha)^{\left|X\right|}\leq\frac{1}{N^{3}}$. Thus, with probability
at least $1-\frac{1}{N^{3}}$, $\mathbf{U^{\prime}}\in\mathcal{X}$ and Find-
Permutation in Step (ii) proceeds to the next step. ∎

######  Lemma 8.13 (Correctly finding $B^{\prime}=\pi^{-1}(B)$).

With probability at least $1-1/N^{3}$, the algorithm Find-Permutation will
correctly identify $\mathbf{V^{\prime}}_{1},\ldots,\mathbf{V^{\prime}}_{b}$
for which $\mathbf{V^{\prime}}_{i,\pi}=\mathbf{V}_{i}$, and
$B^{\prime}={\pi^{-1}(2),\ldots,\pi^{-1}(b+1)}$ will be identified correctly
as well. Moreover, Find-Permutation proceeds to Step (iv).

###### Proof.

Let $\mathbf{V^{\prime}}_{1},\ldots,\mathbf{V^{\prime}}_{b}$ denote the
vectors for which $\mathbf{V^{\prime}}_{i,\pi}=\mathbf{V}_{i}$ for every $i$.
Note that these are the only vectors outside $\mathbf{U^{\prime}}$ in the
support of $D$ that have $1$ at the index $i^{*}$. As
$D(\mathbf{V}^{\prime}_{i})=\frac{\alpha}{b}$, the probability that
$\mathbf{V}^{\prime}_{i}$ does not appear in $\mathcal{X}$ is at most
$(1-\frac{\alpha}{b})^{\left|X\right|}$. Since
$\left|\mathcal{X}\right|=\mathcal{O}(\log^{2}N/\alpha)$ and
$b=\mathcal{O}(\log\log kn)$, the probability that
$\mathbf{V}^{\prime}_{i}\in\mathcal{X}$ is at least $1-\frac{1}{N^{4}}$. Using
the union bound over all the vectors of $\mathcal{S}^{\prime}$, with
probability at least $1-1/N^{3}$, we know that all of these vectors are in
$\mathcal{X}$, in which case they are identified correctly, so $B^{\prime}$ is
identified correctly as well, and Find-Permutation in Step (iii) proceeds to
the next step. ∎

######  Lemma 8.14 (Correctly identifying $\pi^{-1}(b+2),\ldots,\pi^{-1}(N)$).

Let $\mathbf{W^{\prime}}_{1},\ldots,\mathbf{W^{\prime}}_{\lceil\log
kn\rceil-1}$ denote the vectors for which
$\mathbf{W^{\prime}}_{j,\pi}=\mathbf{W}_{j}$ for every $j$. With probability
at least $1-1/N^{3}$, all these vectors appear in $\mathcal{X}$, in which case
they are identified correctly, and so are $\pi^{-1}(b+2),\ldots,\pi^{-1}(N)$.
Moreover, Find-Permutation proceeds to Step (vi).

The proof of the above lemma is similar to the proof of Lemma 8.13 and is
omitted. Note that from Lemma 8.12, Lemma 8.13 and Lemma 8.14, we know that
with probability at least $1-o(1)$, the algorithm Find-Permutation has
correctly determined the permutation $\pi$ and proceeded to Step (vi). We will
finish up the proof of Lemma 8.11 using the following lemma.

######  Lemma 8.15.

The probability that Find-Permutation outputs Fail in Step (vi) (instead of
outputting $\pi$) is at most $1/N^{3}$.

###### Proof.

As $D\in\mathcal{P}_{\mathrm{Gap}}$, from the description of the property, we
know that
$D(\\{\mathbf{U^{\prime}}\\}\cup\mathcal{S}^{\prime}\cup\mathcal{T}^{\prime})=3\alpha$.
As $\left|\mathcal{X}^{\prime}\right|=\mathcal{O}(\log^{2}N/\alpha)$, using
the Chernoff bound (Lemma A.1), we have the result. ∎

Combining the above lemmas, we conclude that with probability at least $9/10$,
the algorithm Find-Permutation outputs a correct permutation $\pi$, completing
the proof of Lemma 8.11.

To conclude this section, we show that with high probability, we will not
output $\pi$ for which too much weight is placed outside the “encoded part” of
the distribution.

######  Lemma 8.16.

For any distribution $D$ (regardless of whether $D$ is in
$\mathcal{P}_{\mathrm{Gap}}$ or not), the probability that Find-Permutation
outputs a permutation $\pi$ for which
$D(\\{\mathbf{X}:\mathbf{X}\mid_{\\{i^{*}\\}\cup
B^{\prime}}=\mathbf{0}\mathbf{1}^{b}\\})\leq 1-5\alpha$ is at most $1/10$.

###### Proof.

Recall the set of vectors $\mathcal{Y}$ as defined in Step (vi) of Find-
Permutation:
$\mathcal{Y}=\\{\mathbf{Z}\in\mathcal{X}^{\prime}:\mathbf{Z}\mid_{{{i^{*}}\cup
B^{\prime}}}\neq\mathbf{0}\mathbf{1}^{b}\\}$, where $\mathcal{X}^{\prime}$ is
the multi-set of (new) samples obtained in Step (vi) of Find-Permutation.
Consider a distribution $D$ such that
$D(\\{\mathbf{X}:\mathbf{X}_{\\{i^{*}\\}\cup
B^{\prime}}=\mathbf{0}\mathbf{1}^{b}\\})\leq 1-5\alpha$. This implies that
$\mathbb{E}\left[\left|\mathcal{Y}\right|/\left|\mathcal{X}^{\prime}\right|\right]\geq
5\alpha$. As
$\left|\mathcal{X}^{\prime}\right|=\mathcal{O}(\log^{2}N/\alpha)$, using the
Chernoff bound (Lemma A.1), we obtain that with probability at least $9/10$,
the algorithm Find-Permutation outputs Fail in Step (vi), and does not output
any permutation $\pi$. This completes the proof. ∎

###  8.4 The upper bound on adaptive testing for property
$\mathcal{P}_{\mathrm{Gap}}$

In this subsection, we design the adaptive tester for the property
$\mathcal{P}_{\mathrm{Gap}}$. Given a distribution $D$ over $\\{0,1\\}^{N}$,
with high probability, Alg-Adaptive outputs Accept when
$D\in\mathcal{P}_{\mathrm{Gap}}$, and outputs Reject when $D$ is far from
$\mathcal{P}_{\mathrm{Gap}}$. The formal adaptive algorithm is presented in
Alg-Adaptive (see Algorithm 4). Note that it has only two adaptive steps.

In the first adaptive step, our tester Alg-Adaptive starts by calling the
algorithm Find-Permutation (as described in Subsection 8.3) whose query
complexity is $\widetilde{{\mathcal{O}}}(n)$. If
$D\in\mathcal{P}_{\mathrm{Gap}}$, with high probability, Find-Permutation
returns the permutation $\pi$ such that
$D_{\pi}\in\mathcal{P}_{\mathrm{Gap}}^{0}$. Once $\pi$ is known, when we
obtain a sample $\mathbf{X}$ from $D$, we can consider it as
$\mathbf{X}_{\pi}$ from $D_{\pi}$. Also, from the structure of the vectors in
the support of the distributions in $P^{0}_{\mathrm{Gap}}$, we can decide
whether $X_{\pi}$ is a special vector, that is,
$X_{\pi}\in\\{\mathbf{U}\\}\cup\mathcal{S}\cup\mathcal{T}$ or
$\mathbf{X}_{\pi}$ is an encoding vector, that is,
$\mathbf{X}_{\pi}=\mathrm{FE}(\mathbf{z},\mathbf{x})$ for some
$\mathbf{z}\in[n]^{m}$ and $\mathbf{x}\in\\{0,1\\}^{n}$. Observe that, in the
later case, we can decode any bit of $\mathbf{x}$ (say $\mathbf{x}_{j}$) by
finding $\mathbf{X}_{\pi}$ projected into $C_{j}$, which can be done by
performing $\mathcal{O}(\log n)$ queries.

As the second adaptive step, our algorithm asks for a sequence $\mathcal{Y}$
of $\mathcal{O}(n/\varepsilon)$ samples from $D$, that is, from $D_{\pi}$. Let
$\mathcal{Y}^{\prime}\subseteq\mathcal{Y}$ be the sequence of encoding vectors
in $\mathcal{Y}$. We now call Supp-Est$(\mathcal{Y}^{\prime},\varepsilon/3)$
(from Lemma 8.8), and depending on its output, Alg-Adaptive either reports
Accept or Reject. Note that we can execute every query by Supp-
Est$(\mathcal{Y}^{\prime},\varepsilon/3)$, by performing $\mathcal{O}(\log n)$
queries to the corresponding sample in $\mathcal{Y}^{\prime}$ as discussed
above.

When $D\in\mathcal{P}_{\mathrm{Gap}}$ (that is,
$D_{\pi}\in\mathcal{P}_{\mathrm{Gap}}^{0}$ for the permutation $\pi$), the set
of encoding vectors in $D_{\pi}$ is the encoding of at most $n$ vectors in
$\\{0,1\\}^{n}$. So, in that case, Alg-Adaptive reports Accept with high
probability. Now consider the case where $D$ is $\varepsilon$-far from
$\mathcal{P}_{\mathrm{Gap}}$. If Alg-Adaptive has not rejected $D$ before
calling Supp-Est$(\mathcal{Y}^{\prime},\varepsilon/3)$, we will show that the
distribution over $\\{0,1\\}^{n}$ induced by the vectors decoded from the
encoding vectors in $D_{\pi}$ is ${\varepsilon}/3$-far from having support
size $n$. Then, Alg-Adaptive will still reject $D$ with high probability.

1

Input: Sample and Query access to a distribution $D$ over $\\{0,1\\}^{N}$, and
a parameter $\varepsilon\in(0,1)$.

Output: Either Accept or Reject.

2

(i)

Call Find-Permutation. If Find-Permutation returns Fail, Reject. Otherwise,
let $\pi$ be the permutation returned by Find-Permutation. Denote for
convenience $i^{*}=\pi^{-1}(1),B^{\prime}=\pi^{-1}(B)$, and
$C^{\prime}_{j}=\pi^{-1}(C_{j})$ for every $j\in[n]$.

(ii)

Take a multi-set $\mathcal{X}$ of $\mathcal{O}(1/\varepsilon)$ samples from
$D$, and query all the entries of the sampled vectors of $\mathcal{X}$ to know
the vectors of $\mathcal{X}$ completely. If there is any vector $\mathbf{X}$
for which $\mathbf{X}\mid_{\\{i^{*}\\}\cup
B^{\prime}}=\mathbf{0}\mathbf{1}^{b}$ (according to the permutation $\pi$
obtained from Step (i)) for which $\mathbf{X}_{\pi}$ is not in the image of
$\mathrm{FE}$ (i.e. it is not a valid encoding of any vector in
$\\{0,1\\}^{n}$), Reject. Otherwise, proceed to the next step.

(iii)

Take a sequence of samples $\mathcal{Y}$ such that
$\left|\mathcal{Y}\right|=\mathcal{O}(n/\varepsilon)$ from $D$. Now construct
the sequence of vectors $\mathcal{Y}^{\prime}$ such that
$\mathcal{Y}^{\prime}=\\{\mathbf{Y}\in\mathcal{Y}:\mathbf{Y}\mid_{\\{i^{*}\\}\cup
B^{\prime}}=\mathbf{0}\mathbf{1}^{b}\\}$ by querying the indices corresponding
to $\\{i^{*}\\}\cup B^{\prime}$.

(iv)

Call Supp-Est$(\mathcal{Y}^{\prime},\varepsilon/3)$ (from Lemma 8.8), where a
query to an index $j$ is simulated by querying the indices of $C^{\prime}_{j}$
and decoding the obtained vector with respect to to $\mathrm{SE}$ (that is,
checking whether the restriction of the queried vector to $C^{\prime}_{j}$ is
equal to $\mathrm{SE}(i,0)$ for some $i$, or equal to $\mathrm{SE}(i,1)$ for
some i). Reject if any of the following conditions hold:

  * (a)

$\left|\mathcal{Y}^{\prime}\right|/\left|\mathcal{Y}\right|\leq 1/2$ (due to
the absence of sufficiently many samples in $\mathcal{Y}^{\prime}$ to apply
Supp-Est).

  * (b)

Supp-Est$(\mathcal{Y}^{\prime},\varepsilon/3)$ queries an index $j$ from some
$\mathbf{Y}_{i}$ corresponding to an invalid encoding of
$\mathbf{Y}_{i}\mid_{C^{\prime}_{j}}$ (that is, when
$\mathbf{Y}_{i}\mid_{C^{\prime}_{j}}$ is not in the image of $\mathrm{SE}$).

  * (c)

Supp-Est$(\mathcal{Y}^{\prime},\varepsilon/3)$ outputs Reject.

Otherwise, Accept.

Algorithm 4 Alg-Adaptive

Let us first discuss the query complexity of Alg-Adaptive.

######  Lemma 8.17 (Query complexity of Alg-Adaptive).

The query complexity of the adaptive tester Alg-Adaptive for testing the
property $\mathcal{P}_{\mathrm{Gap}}$ is
$\widetilde{{\mathcal{O}}}(N)=\widetilde{{\mathcal{O}}}(n)$.

###### Proof.

Note that Alg-Adaptive calls the algorithm Find-Permutation in Step (i).
Following the query complexity lemma of Find-Permutation (Lemma 8.10), we know
that Find-Permutation performs $\widetilde{{\mathcal{O}}}(N)$ queries.

For every sample taken in Step (ii), the sampled vectors of the multi-set
$\mathcal{X}$ are queried completely. Since we take
$\mathcal{O}(1/\varepsilon)$ samples, this step requires
$\mathcal{O}(N/\varepsilon)=\widetilde{\mathcal{O}}(n/\varepsilon)$ queries in
total.

Then in Step (iii), Alg-Adaptive takes a multi-set $\mathcal{Y}$ of
$\mathcal{O}(n/\varepsilon)$ samples, and queries for the indices in
$\\{i^{*}\\}\cup B^{\prime}$ to obtain the vectors in $\mathcal{Y}^{\prime}$,
which takes $\mathcal{O}(n\log\log kn/\varepsilon)$ queries. Finally, in Step
(iv), Alg-Adaptive calls the algorithm Supp-Est, which performs
$\widetilde{{\mathcal{O}}}(n)$ queries (following Lemma 8.8), each of them
simulated by $\mathcal{O}(\log n)$ queries to some
$\mathbf{Y}_{i}\mid_{{C^{\prime}_{j}}}$. Thus, in total, Alg-Adaptive performs
$\widetilde{{\mathcal{O}}}(N)=\widetilde{{\mathcal{O}}}(n)$ queries. ∎

Now we prove the correctness of Alg-Adaptive. We will start with the
completeness proof.

######  Lemma 8.18 (Completeness of Alg-Adaptive).

Let $D$ be a distribution defined over $\\{0,1\\}^{N}$. If
$D\in\mathcal{P}_{\mathrm{Gap}}$, then the algorithm Alg-Adaptive will output
Accept with probability at least $2/3$.

###### Proof.

Consider a distribution $D\in\mathcal{P}_{\mathrm{Gap}}$. From the
completeness lemma of Find-Permutation (Lemma 8.11), we infer that with
probability at least $9/10$, Find-Permutation returns the correct permutation
$\pi$ in Step (i). Then, by the definition of $\mathcal{P}_{\mathrm{Gap}}$,
the algorithm Alg-Adaptive can never encounter any samples with invalid
encodings in Step (ii) which could cause it to Reject. Thus, with probability
at least $9/10$, the algorithm proceeds, with the correct permutation $\pi$,
to Step (iii) and Step (iv).

As $D\in\mathcal{P}_{\mathrm{Gap}}$,
$D(\\{\mathbf{U^{\prime}}\\}\cup\mathcal{S}^{\prime}\cup\mathcal{T}^{\prime})=3\alpha$.
Since $\left|\mathcal{Y}\right|=\mathcal{O}(n/\varepsilon)$, using the
Chernoff bound (Lemma A.2 (ii)), we can say that, with probability at least
$9/10$, $\left|\mathcal{Y}^{\prime}\right|/\left|\mathcal{Y}\right|\geq 1/2$.
Moreover, as the vectors in $\mathcal{Y}^{\prime}$ are valid encodings with
respect to the function $\mathrm{FE}$ of at most $n$ vectors from $[2n]$,
following the support estimation upper bound lemma (Lemma 8.8), we obtain that
Supp-Est outputs Accept with probability at least $9/10$. Combining these, we
conclude that Alg-Adaptive outputs Accept with probability at least $2/3$. ∎

Now we prove that when $D$ is $\varepsilon$-far from
$\mathcal{P}_{\mathrm{Gap}}$, Alg-Adaptive will output Reject with probability
at least $2/3$.

######  Lemma 8.19 (Soundness of Alg-Adaptive).

Let $\varepsilon\in(0,1)$ be a proximity parameter. Assume that $D$ is a
distribution defined over $\\{0,1\\}^{N}$ such that $D$ is $\varepsilon$-far
from $\mathcal{P}_{\mathrm{Gap}}$. Then Alg-Adaptive outputs Reject with
probability at least $2/3$.

From the description of Alg-Adaptive (Algorithm 4), if the tester reports
Reject before executing all the steps of Supp-
Est$(\mathcal{Y}^{\prime},\varepsilon/3)$ in Step (iv), then we are done. So,
let us assume that Alg-Adaptive executes all the steps of Supp-
Est$(\mathcal{Y}^{\prime},\varepsilon/3)$. Let $\mathcal{Y}^{\prime}$ be the
set of samples from a distribution $D^{\\#}$ over $\\{0,1\\}^{n}$ as it is
presented to Supp-Est$(\mathcal{Y}^{\prime},\varepsilon/3)$. Note that
$D^{\\#}$ is unknown and we are accessing $D^{\\#}$ indirectly via decoding
samples from $D$ over $\\{0,1\\}^{N}$. From the correctness Supp-
Est$(\mathcal{Y}^{\prime},\varepsilon/3)$, we will be done with the proof of
Lemma 8.19 by proving the following lemma.

######  Lemma 8.20 (Property of the decoded distribution).

$D^{\\#}$ is $\varepsilon/3$-far from having support size at most $n$.

We prove the above lemma using a series of claims. Let $D$ be a distribution
which is $\varepsilon$-far from $\mathcal{P}_{\mathrm{Gap}}$, and
$\mathcal{V}$ denote the set
$\\{\mathbf{X}\in\mbox{Supp}(D):\mathbf{X}\mid_{\\{i^{*}\\}\cup
B^{\prime}}=\mathbf{0}\mathbf{1}^{b}\\}$, and let us define
$\mathcal{U}=\mbox{Supp}(D)\setminus\mathcal{V}$. Let us start with the
following observation.

######  Observation 8.21.

$D(\mathcal{U})\leq 5\alpha$, unless the algorithm Alg-Adaptive has rejected
with probability at least $1-1/N^{3}$ in Step (i).

###### Proof.

Since Alg-Adaptive in Step (i) invokes the algorithm Find-Permutation, this
follows immediately from Lemma 8.16. ∎

Let $\pi$ be the permutation returned by Find-Permutation. Now assume
$\mathcal{V}^{\mbox{inv}}\subseteq\mathcal{V}$ denotes the following set of
vectors:

$\mathcal{V}^{\mbox{inv}}=\\{\mathbf{X}\in\mathcal{V}:\mathbf{X}_{\pi}\neq\mathrm{FE}(\mathbf{z},\mathbf{x})\
\mbox{for all}\ \mathbf{z}\in[n]^{m},\mathbf{x}\in\\{0,1\\}^{n}\\}$

For every vector $\mathbf{V}\in\mathcal{V}^{\mbox{inv}}$, let
$\Gamma^{\prime}_{\mathbf{V}}=\\{j\in[n]:\mathbf{V}\mid_{C^{\prime}_{j}}\
\mbox{is not in the image of}\ \mathrm{SE}\\}$ denotes the set of indices in
$[n]$ of chunks of all the “ _locally invalid_ ” encodings in the vector
$\mathbf{V}$ 282828Note that it may be the case that
$\Gamma^{\prime}_{\mathbf{V}}=\emptyset$, for example when for every
$j\in[n]$, we have
$\mathbf{V}\mid_{C^{\prime}_{j}}=\mathrm{SE}(i_{j},\mathbf{x}_{j})$, for some
$i_{1},\ldots,i_{n}$ and $\mathbf{x}_{1},\ldots,\mathbf{x}_{n}$ for which
$i_{1},\ldots,i_{n}$ are not in the image of $\mathrm{GE}$.. Now we have the
following observation.

######  Observation 8.22.

$D(\mathcal{V}^{\mbox{inv}})\leq{\varepsilon}/10$.

The above observation holds as otherwise, Alg-Adaptive would have rejected in
Step (ii) with probability at least $2/3$.

Let us define a distribution $D_{1}$ over $\\{0,1\\}^{N}$ using the following
procedure:

  1. (i)

Set $D_{1}(\mathbf{X})=D(\mathbf{X})$ for every $\mathbf{X}\in\mathcal{U}$.

  2. (ii)

Recall that
$\Gamma^{\prime}_{\mathbf{V}}=\\{j\in[n]:\mathbf{V}\mid_{C^{\prime}_{j}}\
\mbox{is not in the image of}\ \mathrm{SE}\\}$ for every vector
$\mathbf{V}\in\mathcal{V}^{\mbox{inv}}$. For every vector
$\mathbf{V}\in\mathcal{V}^{\mbox{inv}}$, we perform the following steps:

    1. (a)

For every $j\notin\Gamma^{\prime}_{\mathbf{V}}$, decode the vector
$\mathbf{V}\mid_{C^{\prime}_{j}}$ using $\mathrm{SE}$ to obtain
$\mathbf{x}_{j}\in\\{0,1\\}$.

    2. (b)

For every $j\in\Gamma^{\prime}_{\mathbf{V}}$, choose an arbitrary value
$\mathbf{x}_{j}$ from $\\{0,1\\}$.

    3. (c)

Using $\mathbf{x}=(\mathbf{x}_{1},\ldots,\mathbf{x}_{n})$ obtained from (a)
and (b), construct a new vector $\mathbf{V}^{\prime}$ for which
$\mathbf{V}^{\prime}_{\pi}=\mathrm{FE}(\mathbf{z},\mathbf{x})$ for an
arbitrary $\mathbf{z}\in[n]^{m}$, where $\pi$ is the permutation obtained from
Find-Permutation in Step (i) of Alg-Adaptive.

  3. (iii)

For every vector $\mathbf{V}\in\mathcal{V}\setminus\mathcal{V}^{\mbox{inv}}$,
set $\mathbf{V}^{\prime}=\mathbf{V}$.

  4. (iv)

Finally define
$D_{1}(\mathbf{W})=\sum_{\mathbf{V}:\mathbf{V^{\prime}}=\mathbf{W}}D(\mathbf{V})$
for every $\mathbf{W}\in\mathcal{V}$.

Let $\mathcal{V}^{\prime}$ be the set of vectors in $\\{0,1\\}^{N}$ that are
in the support of $D_{1}$ but not in $\mathcal{U}$, that is,
$\mathcal{V}^{\prime}=\\{\mathbf{X}:\mathbf{X}\in\mathrm{Supp}(D_{1})\setminus\mathcal{U}\\}$.
From the construction of $D_{1}$, the following observation follows.

######  Observation 8.23.

$D_{1}(\mathcal{U})=D(\mathcal{U})\leq 5\alpha$ and
$D_{1}(\mathcal{V}^{\prime})=D(\mathcal{V})=1-D(\mathcal{U})\geq 1-5\alpha.$

Now we prove that the distributions $D$ and $D_{1}$ are not far in Earth Mover
Distance.

######  Lemma 8.24.

The Earth Mover Distance between $D$ and $D_{1}$ is at most $\varepsilon/10$.

###### Proof.

Recall that the EMD between $D$ and $D_{1}$ is the solution to the following
LP:

$\displaystyle\mbox{Minimize}\quad{\sum_{\mathbf{X},\mathbf{Y}\in\\{0,1\\}^{N}}f_{\mathbf{X}\mathbf{Y}}d_{H}(\mathbf{X},\mathbf{Y})}$
$\displaystyle\mbox{Subject
to}\quad\sum_{\mathbf{Y}\in\\{0,1\\}^{N}}f_{\mathbf{X}\mathbf{Y}}=D(\mathbf{X})~{}\forall\
\mathbf{X}\in\\{0,1\\}^{N}\;\mbox{and}\;\sum_{\mathbf{X}\in\\{0,1\\}^{N}}f_{\mathbf{X}\mathbf{Y}}=D_{1}(\mathbf{Y})~{}\forall\
\mathbf{Y}\in\\{0,1\\}^{N}.$

Consider the flow $f^{*}$ such that $f^{*}_{\mathbf{XX}}=D(\mathbf{X})$ for
every
$\mathbf{X}\in\mathcal{U}\cup(\mathcal{V}\setminus\mathcal{V}^{\mbox{inv}})$,
$f^{*}_{\mathbf{VV^{\prime}}}=D_{1}(\mathbf{V})$ for every
$\mathbf{V}\in\mathcal{V}^{\mbox{inv}}$, and $f^{*}_{\mathbf{X}\mathbf{Y}}=0$
for all other vectors. Then we have the following:

$\displaystyle d_{EM}(D,D_{1})$ $\displaystyle\leq$ $\displaystyle\sum_{{\bf
X},{\bf Y}\in\\{0,1\\}^{N}}f^{*}_{{\bf XY}}d_{H}({\bf X},{\bf Y})$
$\displaystyle\leq$
$\displaystyle\sum_{\mathbf{X}\in\\{0,1\\}^{N}\setminus\mathcal{V}^{\mbox{inv}}}f^{*}_{{\bf
XX}}d_{H}({\bf X},{\bf X})+\sum_{{\bf
V}\in\mathcal{V}^{\mbox{inv}}}f^{*}_{{\bf V}{\bf V}^{\prime}}d_{H}({\bf
V},{\bf V^{\prime}})$ $\displaystyle\leq$ $\displaystyle
0+\sum_{\mathbf{V}\in\mathcal{V}^{\mbox{inv}}}D(\mathbf{V})d_{H}({\bf V},{\bf
V^{\prime}}).$

To bound the second term of the last expression, note that

$\sum\limits_{\mathbf{V}\in\mathcal{V}^{\mbox{inv}}}D(\mathbf{V})d_{H}({\bf
V},{\bf V^{\prime}})\leq D(\mathcal{V}^{\mbox{inv}})\leq\varepsilon/10.$

This follows from Observation 8.22. Thus, we conclude that
$d_{EM}(D,D_{1})\leq\varepsilon/10$, completing the proof of the lemma. ∎

Now we have the following observation regarding the rejection probabilities of
Alg-Adaptive for the distributions $D$ and $D_{1}$. This will imply that, as
we are executing all steps of Supp-Est$(\mathcal{Y}^{\prime},\varepsilon/3)$,
the steps of our algorithm are oblivious to both $D$ and $D_{1}$. That is, we
can assume that the input to the algorithm Alg-Adaptive is the distribution
$D_{1}$ instead of $D$.

######  Observation 8.25.

The probability that the tester Alg-Adaptive outputs Reject in Step (iv) where
the input distribution is $D$ is at least as large as the probability that
Alg-Adaptive outputs Reject in Step (iv) when the input distribution is
$D_{1}$.

###### Proof.

Note that in the distribution $D$, there can be some vectors in
$\mbox{Supp}(D)$ that are not valid encodings with respect to the function
$\mathrm{FE}$. Thus during its execution, the tester Alg-Adaptive can Reject
$D$ by Condition (ii) and Condition (iv) (b). However, by the construction of
$D_{1}$ from $D$, we have replaced the invalid encoding vectors with valid
encoding vectors. Thus, the only difference it makes here is that Alg-Adaptive
may eventually accept a sample from $D_{1}$ when encountering such a place
where a sample from $D$ would have been immediately rejected by Condition (ii)
or Condition (iv) (b). Other than this difference, the distributions $D$ and
$D_{1}$ are identical. So, the probability that Alg-Adaptive will Reject $D$
is at least as large as the probability that it Rejects $D_{1}$. ∎

Now, let us come back to the proof of Lemma 8.20. Recall that
$\mathcal{V}^{\prime}=\\{\mathbf{X}:\mathbf{X}\in\mathrm{Supp}(D_{1})\setminus\mathcal{U}\\}$.
Let us define the distribution $D^{\\#}$ over $\\{0,1\\}^{n}$ referred to in
Lemma 8.20. For $\mathbf{x}\in\\{0,1\\}^{n}$, we have the following:

$D^{\\#}(\mathbf{x})=D_{1}^{{dec}}(\mathbf{x})=\frac{1}{D_{1}(\mathcal{V}^{\prime})}\sum_{\begin{subarray}{c}\mathbf{Y}_{\pi}=\mathrm{FE}(\mathbf{z},\mathbf{x})\\\
\mbox{for some}\
\mathbf{z}\in[n]^{m}\end{subarray}}D_{1}(\mathbf{Y})=\frac{1}{D_{1}(\mathcal{V}^{\prime})}\sum_{\mathbf{z}\in[n]^{m}}D_{1}(\mathrm{FE}(\mathbf{z},\mathbf{x})_{\pi^{-1}}).$
(1)

For the sake of contradiction, assume that $D^{\\#}=D_{1}^{dec}$ is
$\varepsilon/3$-close to having support size at most $n$. Let $D_{2}$ be a
distribution over $\\{0,1\\}^{n}$ having support size at most $n$ such that
the Earth Mover Distance between $D_{2}$ and $D_{1}^{dec}$ is at most
$\varepsilon/3$.

Given the distribution $D_{2}$ over $\\{0,1\\}^{n}$, and the flow
$f^{\prime}_{\mathbf{x}\mathbf{y}}$ from $D_{2}$ to $D_{1}^{dec}$ realizing
the EMD of at most $\varepsilon/3$ between them, let us consider the
distribution $D_{2}^{enc}$ over $\\{0,1\\}^{N}$ as follows:

  1. (i)

For any $\mathbf{X}\in\mathcal{V^{\prime}}$, for which
$\mathbf{X}_{\pi}=\mathrm{FE}(\mathbf{z},\mathbf{x})$ for some
$\mathbf{z}\in[n]^{m}$, set:

$D_{2}^{enc}(\mathbf{X})=\sum\limits_{\mathbf{y}\in\\{0,1\\}^{n}}f^{\prime}_{\mathbf{x}\mathbf{y}}\frac{D_{1}(\mathrm{FE}(\mathbf{z},\mathbf{y})_{\pi^{-1}})}{D_{1}^{dec}(\mathbf{y})}$.

  2. (ii)

For every $\mathbf{X}\in\mathcal{U}$, set
$D_{2}^{enc}(\mathbf{X})=D_{1}(\mathbf{X})$.

The following observation follows from Observation 8.23 and the construction
of $D_{2}^{enc}$.

######  Observation 8.26.

$D_{2}^{enc}(\mathcal{U})=D_{1}(\mathcal{U})\leq 5\alpha$ and
$D_{2}^{enc}(\mathcal{V}^{\prime})=D_{1}(\mathcal{V}^{\prime})=1-D_{1}(\mathcal{U})\geq
1-5\alpha.$

The following two lemmas bound the distance of $D_{2}^{enc}$ from
$\mathcal{P}_{\mathrm{Gap}}$ and from $D_{1}$, where $D_{1}^{dec}$ is
$\varepsilon/3$-close to having support size at most $n$. We will prove these
two lemmas later.

######  Lemma 8.27.

$D_{2}^{enc}$ is $6\alpha$-close to $\mathcal{P}_{\mathrm{Gap}}$.

######  Lemma 8.28.

The Earth Mover Distance between $D_{2}^{enc}$ and $D_{1}$ is at most
$\varepsilon/3$.

Assuming Lemma 8.27 and Lemma 8.28 hold, now we proceed to prove Lemma 8.20.

###### Proof of Lemma 8.20.

From Lemma 8.24, we know that $d_{EM}(D,D_{1})\leq\varepsilon/10$. So, the
above two lemmas imply that $D$ is
$(\varepsilon/3+\varepsilon/10+6\alpha)=2\varepsilon/3$-close to
$\mathcal{P}_{\mathrm{Gap}}$, which contradicts the fact that $D$ is
$\varepsilon$-far from $\mathcal{P}_{\mathrm{Gap}}$. This completes the proof
of the lemma. ∎

Now we will prove Lemma 8.27 and Lemma 8.28.

###### Proof of Lemma8.27.

We define another distribution $D_{3}$ over $\\{0,1\\}^{N}$ from $D_{2}^{enc}$
such that $D_{3}$ is in $\mathcal{P}_{\mathrm{Gap}}$ and
$d_{EM}(D_{2}^{enc},D_{3})\leq 6\alpha$ as follows:

  1. (i)

$D_{3}(\mathbf{U}^{\prime})=\alpha$.

  2. (ii)

$D_{3}(\mathbf{X})=\frac{\alpha}{b}$ for every
$\mathbf{X}\in\mathcal{S}^{\prime}$,
$D_{3}(\mathbf{X})=\frac{\alpha}{\lceil\log kn\rceil}$ for every
$\mathbf{X}\in\mathcal{T}^{\prime}$.

  3. (iii)

$D_{3}(\mathbf{X})={(1-3\alpha)}\cdot\frac{D_{2}^{enc}(\mathbf{X})}{D_{2}^{enc}(\mathcal{V}^{\prime})}$
for every $\mathbf{X}\in\mathcal{V^{\prime}}$.

Recall that $D_{2}$ is a distribution over $\\{0,1\\}^{n}$ that has support
size at most $n$. This implies that the set of vectors in $\mbox{{\sc
Supp}}(D_{2}^{enc})\setminus\mathcal{U}$ is the encoding of at most $n$
vectors in $\\{0,1\\}^{n}$. So, from the definition of
$\mathcal{P}_{\mathrm{Gap}}$ and $D_{3}$, it is clear that
$D_{3}\in\mathcal{P}_{\mathrm{Gap}}$.

Now we show that the Earth Mover Distance between the distributions $D_{3}$
and $D_{2}^{enc}$ is not large.

######  Claim 8.29.

The Earth Mover Distance between $D_{2}^{enc}$ and $D_{3}$ is at most
$6\alpha$.

###### Proof.

We will bound the Earth Mover Distance between $D_{2}^{enc}$ and $D_{3}$ in
terms of the variation distance between them as follows:

$\displaystyle d_{EM}(D_{2}^{enc},D_{3})$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}\cdot\sum_{\mathbf{X}\in\\{0,1\\}^{N}}|D_{2}^{enc}(\mathbf{X})-D_{3}(\mathbf{X})|$
(2) $\displaystyle=$
$\displaystyle\frac{1}{2}\cdot\sum_{\mathbf{X}\in\mathcal{V^{\prime}}}|D_{2}^{enc}(\mathbf{X})-D_{3}(\mathbf{X})|+\frac{1}{2}\cdot\sum_{\mathbf{X}\in\\{0,1\\}^{N}\setminus\mathcal{V^{\prime}}}|D_{2}^{enc}(\mathbf{X})-D_{3}(\mathbf{X})|.$

Let us bound the first term as follows:

$\displaystyle\sum_{\mathbf{X}\in\mathcal{V^{\prime}}}|D_{2}^{enc}(\mathbf{X})-D_{3}(\mathbf{X})|$
$\displaystyle=$
$\displaystyle\sum_{\mathbf{X}\in\mathcal{V^{\prime}}}|(1-3\alpha)\frac{D_{2}^{enc}(\mathbf{X})}{D_{2}^{enc}(\mathcal{V^{\prime}})}-D_{2}^{enc}(\mathbf{X})|$
$\displaystyle=$
$\displaystyle\sum_{\mathbf{X}\in\mathcal{V^{\prime}}}\frac{D_{2}^{enc}(\mathbf{X})}{D_{2}^{enc}(\mathcal{V^{\prime}})}|(1-3\alpha)-D_{2}^{enc}(\mathcal{V^{\prime}})|$
$\displaystyle=$
$\displaystyle\sum_{\mathbf{X}\in\mathcal{V^{\prime}}}\frac{D_{2}^{enc}(\mathbf{X})}{D_{2}^{enc}(\mathcal{V^{\prime}})}|3\alpha-(1-D_{2}^{enc}(\mathcal{V^{\prime}}))|$
$\displaystyle\leq$
$\displaystyle\sum_{\mathbf{X}\in\mathcal{V^{\prime}}}3\alpha\frac{D_{2}^{enc}(\mathbf{X})}{D_{2}^{enc}(\mathcal{V^{\prime}})}\leq
3\alpha.~{}~{}~{}\left(\because D_{2}^{enc}(\mathcal{V^{\prime}})\geq
1-5\alpha,\mbox{ Observation}~{}\ref{obs:v-dash-1}\right)$

From Observation 8.23, $D_{2}^{enc}(\mathcal{U})\leq 5\alpha$. From the
definition of $D_{3}$, $D_{3}(\mathcal{U})=3\alpha$, we have

$\sum_{\mathbf{X}\in\\{0,1\\}^{N}\setminus\mathcal{V^{\prime}}}|D_{2}^{enc}(\mathbf{X})-D_{3}(\mathbf{X})|\leq
8\alpha.$

Following Equation 2, we conclude that $d_{EM}(D_{2}^{enc},D_{3})\leq
6\alpha$, which completes the proof. ∎

Since $D_{3}\in\mathcal{P}_{\mathrm{Gap}}$, and $d_{EM}(D_{2}^{enc},D_{3})\leq
6\alpha$, we conclude that $D_{2}^{enc}$ is $6\alpha$-close to
$\mathcal{P}_{\mathrm{Gap}}$. ∎

###### Proof of Lemma 8.28.

Recall that the EMD between $D_{2}^{enc}$ and $D_{1}$ is the solution to the
following LP:

$\displaystyle\mbox{Minimize}\quad{\sum_{\mathbf{X},\mathbf{Y}\in\\{0,1\\}^{N}}f_{\mathbf{X}\mathbf{Y}}d_{H}(\mathbf{X},\mathbf{Y})}$
$\displaystyle\mbox{Subject
to}\quad\sum_{\mathbf{Y}\in\\{0,1\\}^{N}}f_{\mathbf{X}\mathbf{Y}}=D_{2}^{enc}(\mathbf{X})~{}\forall\mathbf{X}\in\\{0,1\\}^{N}\;\mbox{and}\;\sum_{\mathbf{X}\in\\{0,1\\}^{N}}f_{\mathbf{X}\mathbf{Y}}=D_{1}(\mathbf{Y})~{}\forall\mathbf{Y}\in\\{0,1\\}^{N}.$

Let $f^{\prime}_{\mathbf{x}\mathbf{y}}$ be the flow realizing the EMD between
$D_{2}$ and $D_{1}^{dec}$. Using $f^{\prime}$, we now construct a new flow
$f^{\star}$ between $D_{2}^{enc}$ and $D_{1}$ as follows:

  1. (i)

For vectors $\mathbf{X},\mathbf{Y}\in\mathcal{U}$,

    1. (a)

If $\mathbf{X}\neq\mathbf{Y}$, then set $f^{\star}_{\mathbf{X}\mathbf{Y}}=0$.

    2. (b)

If $\mathbf{X}=\mathbf{Y}$, then set
$f^{\star}_{\mathbf{X}\mathbf{Y}}=D_{2}^{enc}(\mathbf{X})=D_{1}(\mathbf{Y})$.

  2. (ii)

For two vectors $\mathbf{X},\mathbf{Y}\in\mathcal{V}$, we take the vectors
$\mathbf{x},\mathbf{y}\in\\{0,1\\}^{n}$ such that
$\mathbf{X},\mathbf{Y}\in\\{0,1\\}^{N}$ are their valid encodings (by
construction, if $\mathbf{X}$ and $\mathbf{Y}$ are in the support of $D_{2}$
and $D_{1}^{enc}$ respectively, such vectors $\mathbf{x},\mathbf{y}$ exist),
and vectors $\mathbf{z}_{1},\mathbf{z}_{2}$ such that
$\mathbf{X}_{\pi}=\mathrm{FE}(\mathbf{z}_{1},\mathbf{x})$ and
$\mathbf{Y}_{\pi}=\mathrm{FE}(\mathbf{z}_{2},\mathbf{y})$. Now we set the flow
as follows:

    1. (a)

If $\mathbf{z}_{1}\neq\mathbf{z}_{2}$, then set
$f^{\star}_{\mathbf{X}\mathbf{Y}}=0$.

    2. (b)

If $\mathbf{z}_{1}=\mathbf{z}_{2}$, then set
$f^{\star}_{\mathbf{X}\mathbf{Y}}=f^{\prime}_{\mathbf{x}\mathbf{y}}\cdot\frac{D_{1}(\mathbf{Y})}{D_{1}^{dec}(\mathbf{y})}$.

  3. (iii)

If one of $\mathbf{X}$ and $\mathbf{Y}$ is in $\mathcal{U}$ and the other one
is in $\mathcal{V}$, then $f^{\star}_{\mathbf{X}\mathbf{Y}}=0$.

We first argue that the flow $f^{*}_{\mathbf{X}\mathbf{Y}}$ constructed as
above is indeed a valid flow, that is, we have:
$\sum\limits_{\mathbf{Y}\in\\{0,1\\}^{N}}f^{\star}_{\mathbf{X}\mathbf{Y}}=D_{2}^{enc}(\mathbf{X})$
and
$\sum\limits_{\mathbf{X}\in\\{0,1\\}^{N}}f^{\star}_{\mathbf{X}\mathbf{Y}}=D_{1}(\mathbf{Y})$.

To prove
$\sum\limits_{\mathbf{Y}\in\\{0,1\\}^{N}}f_{\mathbf{X}\mathbf{Y}}=D_{2}^{enc}(\mathbf{X})$,
first observe that it holds when $\mathbf{X}\in\mathcal{U}$ from (i) and (iii)
in the description of $f^{\star}_{\mathbf{X}\mathbf{Y}}$. Now consider the
case where $\mathbf{X}\in\mathcal{V}$. Assume
$\mathbf{X}_{\pi}=\mathrm{FE}\left(\mathbf{z},\mathbf{x}\right)$, where
$\mathbf{z}\in[n]^{m}$ and $\mathbf{x}\in\\{0,1\\}^{n}$. So, from (ii) in the
description of $f^{\star}_{\mathbf{X}\mathbf{Y}}$, we have

$\sum\limits_{\mathbf{Y}\in\\{0,1\\}^{N}}f^{\star}_{\mathbf{X}\mathbf{Y}}=\sum\limits_{\mathbf{y}\in\\{0,1\\}^{n}}f^{\star}_{\mathbf{X}\mathrm{FE}(\mathbf{z},\mathbf{y})_{\pi^{-1}}}=\sum_{\mathbf{y}\in\\{0,1\\}^{n}}f^{\prime}_{\mathbf{x}\mathbf{y}}\frac{D_{1}(\mathrm{FE}(\mathbf{z},\mathbf{y})_{\pi^{-1}})}{D_{1}^{dec}(\mathbf{y})}=D_{2}^{enc}(\mathbf{X}).$

For
$\sum\limits_{\mathbf{X}\in\\{0,1\\}^{N}}f^{\star}_{\mathbf{X}\mathbf{Y}}=D_{1}(\mathbf{Y})$,
consider $\mathbf{Y}\in\mathcal{V}$ for which
$\mathbf{Y}_{\pi}=\mathrm{FE}(\mathbf{z},\mathbf{y})$ for some
$\mathbf{z}\in[n]^{m}$. Then we have the following:

$\sum_{\mathbf{X}\in\\{0,1\\}^{N}}f_{\mathbf{X}\mathbf{Y}}^{\star}=\sum_{\mathbf{x}\in\\{0,1\\}^{n}}f^{\prime}_{\mathbf{x}\mathbf{y}}\frac{D_{1}(\mathrm{FE}(\mathbf{z},\mathbf{y})_{\pi^{-1}})}{D_{1}^{dec}(\mathbf{y})}=D_{1}^{dec}(\mathbf{y})\frac{D_{1}(\mathrm{FE}(\mathbf{z},\mathbf{y})_{\pi^{-1}})}{D_{1}^{dec}(\mathbf{y})}=D_{1}(\mathbf{Y}).$

In the above, we have used the fact that $f^{\prime}_{\mathbf{x}\mathbf{y}}$
is a valid flow from $D_{2}$ to $D_{1}^{dec}$.

Now, to bound EMD between $D_{2}^{enc}$ and $D_{1}$, let us bound the sum
$\sum\limits_{\mathbf{X},\mathbf{Y}\in\\{0,1\\}^{N}}f^{\star}_{\mathbf{X}\mathbf{Y}}d_{H}(\mathbf{X},\mathbf{Y})$.

$\displaystyle\sum\limits_{\mathbf{X},\mathbf{Y}\in\\{0,1\\}^{N}}f^{\star}_{\mathbf{X}\mathbf{Y}}d_{H}(\mathbf{X},\mathbf{Y})$
$\displaystyle=$
$\displaystyle\sum\limits_{\mathbf{X},\mathbf{Y}\in\mathcal{V}}f^{\star}_{\mathbf{X}\mathbf{Y}}d_{H}(\mathbf{X},\mathbf{Y})~{}~{}~{}\left(\mbox{From
(i) and (iii) in the description of $f^{\star}$}\right)$ $\displaystyle=$
$\displaystyle\sum\limits_{\mathbf{x},\mathbf{y}\in\\{0,1\\}^{n}}\sum\limits_{\mathbf{z}\in[n]^{m}}f^{\star}_{\mathbf{\mathrm{FE}(\mathbf{z},\mathbf{x})_{\pi^{-1}}}\mathrm{FE}(\mathbf{z},\mathbf{y})_{\pi^{-1}}}\cdot
d_{H}({\mathrm{FE}(\mathbf{z},\mathbf{x})_{\pi^{-1}}},\mathrm{FE}(\mathbf{z},\mathbf{y})_{\pi^{-1}})$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\left(\mbox{From
(ii) in the description of $f^{\star}$}\right)$ $\displaystyle\leq$
$\displaystyle\sum\limits_{\mathbf{x},\mathbf{y}\in\\{0,1\\}^{n}}\sum\limits_{\mathbf{z}\in[n]^{m}}f^{\star}_{\mathbf{\mathrm{FE}(\mathbf{z},\mathbf{x})_{\pi^{-1}}}\mathrm{FE}(\mathbf{z},\mathbf{y})_{\pi^{-1}}}\cdot
d_{H}(\mathbf{x},\mathbf{y})~{}~{}~{}\left(\mbox{Observation~{}\ref{obs:FEproperties}
(iii)}\right)$ $\displaystyle=$
$\displaystyle\sum\limits_{\mathbf{x},\mathbf{y}\in\\{0,1\\}^{n}}\sum\limits_{\mathbf{z}\in[n]^{m}}f^{\prime}_{\mathbf{x}\mathbf{y}}\frac{D_{1}(\mathrm{FE}(\mathbf{z},\mathbf{y})_{\pi^{-1}})}{D_{1}^{dec}(\mathbf{y})}\cdot
d_{H}(\mathbf{x},\mathbf{y})~{}~{}~{}\left(\mbox{From (ii) in the description
of $f^{\star}$}\right)$ $\displaystyle=$
$\displaystyle\sum\limits_{\mathbf{x},\mathbf{y}\in\\{0,1\\}^{n}}\left(f^{\prime}_{\mathbf{x}\mathbf{y}}d_{H}(\mathbf{x},\mathbf{y})\cdot\sum\limits_{\mathbf{z}\in[n]^{m}}\frac{D_{1}(\mathrm{FE}(\mathbf{z},\mathbf{y})_{\pi^{-1}})}{D_{1}^{dec}(\mathbf{y})}\right)$
$\displaystyle=$ $\displaystyle
D_{1}(\mathcal{V}^{\prime})\sum\limits_{\mathbf{x},\mathbf{y}\in\\{0,1\\}^{n}}f^{\prime}_{\mathbf{x}\mathbf{y}}d_{H}(\mathbf{x},\mathbf{y})~{}~{}~{}(\mbox{By
Equation}~{}\eqref{def:enc-dist})$ $\displaystyle\leq$
$\displaystyle\sum\limits_{\mathbf{x},\mathbf{y}\in\\{0,1\\}^{n}}f^{\prime}_{\mathbf{x}\mathbf{y}}d_{H}(\mathbf{x},\mathbf{y})\leq\frac{\varepsilon}{3}.$

The last inequality follows from the fact that $f^{\prime}$ realizes the
assumed EMD between $D_{1}$ and $D^{dec}_{2}$. ∎

###  8.5 Near-quadratic lower bound for non-adaptive testers for testing
$\mathcal{P}_{\mathrm{Gap}}$

######  Lemma 8.30 (Lower bound on non-adaptive testers).

Given sample and query access to an unknown distribution $D$, in order to
distinguish whether $D$ satisfies $\mathcal{P}_{\mathrm{Gap}}$ or is
$\varepsilon$-far from satisfying it, any non-adaptive tester must perform
$\widetilde{\Omega}(n^{2})$ queries to the samples obtained from $D$, for some
$\varepsilon\in(0,1)$.

To prove the above lemma, we will construct two hard distributions over
distributions, $D_{yes}$ which is supported over $\mathcal{P}_{\mathrm{Gap}}$,
and $D_{no}$ which is supported over distributions far from
$\mathcal{P}_{\mathrm{Gap}}$, where to distinguish them, any non-adaptive
tester must perform $\widetilde{\Omega}(n^{2})$ queries. Recall from Theorem
8.9 that $D_{yes}^{\mathrm{Supp}}$ and $D_{no}^{\mathrm{Supp}}$ are two
distributions defined over distributions over $\\{1,\ldots,2n\\}$, where
$D_{yes}^{\mathrm{Supp}}$ provides distributions whose support sizes are $n$,
and $D_{no}^{\mathrm{Supp}}$ provides distributions that are $\eta$-far from
distributions whose support size is $(1+2\eta)n$, for some constant
$\eta\in(0,1/8)$. We will use these two distributions to construct the hard
distributions $D_{yes}$ and $D_{no}$ for the property
$\mathcal{P}_{\mbox{Gap}}$.

#### The hard distributions $D_{yes}$ and $D_{no}$:

We describe the distributions $D_{yes}$ and $D_{no}$ over distributions over
$\\{0,1\\}^{N}$ such that $D_{yes}$ is supported over
$\mathcal{P}_{\mathrm{Gap}}$ and $D_{no}$ is supported over distributions that
are $\zeta^{2}\cdot\eta/5$-far from $\mathcal{P}_{\mathrm{Gap}}$. In what
follows, we describe a distribution $D$ ($D=D_{yes}$ or $D=D_{no}$) with
$D^{\mathrm{Supp}}$ as parameter, where $D^{\mathrm{Supp}}$ is a distribution
defined over distributions over $[2n]$. In particular, $D^{\mathrm{Supp}}$ is
either $D_{yes}^{\mathrm{Supp}}$ or $D_{no}^{\mathrm{Supp}}$, where
$D=D_{yes}$ when $D^{\mathrm{Supp}}=D_{yes}^{\mathrm{Supp}}$, or $D=D_{no}$
when $D^{\mathrm{Supp}}=D_{no}^{\mathrm{Supp}}$. To generate $D$, we first
construct a distribution over distributions $D^{0}$ as follows. We denote by
$\widehat{D}$ the distribution over $\\{0,1\\}^{N}$ that we draw according to
$D^{0}$.

(i)

Set $\widehat{D}(U)=\alpha$, where $\mathbf{U}=\mathbf{1}\mathbf{0}^{N-1}$ is
the indicator vector for the index $1$.

(ii)

Take a set of vectors $\mathcal{S}=\\{\mathbf{V}_{1},\ldots,\mathbf{V}_{b}\\}$
in $\\{0,1\\}^{N}$ such that for every $i\in[b]$, the $i$-th vector
$\mathbf{V}_{i}$ is of the form $\mathbf{1}^{i+1}\mathbf{0}^{N-1-i}$. Set
$\widehat{D}(\mathbf{V}_{i})=\alpha/b$ for every $i\in[b]$.

(iii)

Take another set of vectors
$\mathcal{T}=\\{\mathbf{W}_{0},\ldots,\mathbf{W}_{\lceil\log kn\rceil-1}\\}$
(disjoint from $\mathcal{S}$) in $\\{0,1\\}^{N}$ such that for every
$\mathbf{W}_{i}\in\mathcal{T}$, $\mathbf{W}_{i}$ is of the form
$\mathbf{0}(b(i))(\mathbf{0}^{2^{i}}\mathbf{1}^{2^{i}})^{kn/2^{i+1}}$, where
$b(i)$ denotes the length $b$ binary representation of $i$ 292929If
$kn/2^{i+1}$ is not an integer, we trim the rightmost copy of
$\mathbf{0}^{2^{i}}\mathbf{1}^{2^{i}}$ so that the total length of
“$(\mathbf{0}^{2^{i}}\mathbf{1}^{2^{i}})^{kn/2^{i+1}}$” is exactly $kn$.. Set
$\widehat{D}(\mathbf{W}_{i})=\alpha/|\mathcal{T}|$ for every
$\mathbf{W}_{i}\in\mathcal{T}$.

(iv)

Take a set of vectors $\mathcal{Y}\subseteq\\{0,1\\}^{n}$ such that
$\left|\mathcal{Y}\right|=2n$, and for any two vectors
$\mathbf{y}_{i},\mathbf{y}_{j}\in\mathcal{Y}$, $i\neq j$,
$\delta_{H}(\mathbf{y}_{i},\mathbf{y}_{j})\geq n/3$. Also, draw a distribution
$\widetilde{D}$ over $[2n]$ according to $D^{\mathrm{Supp}}$.

(v)

Define $\widehat{D}(\mbox{{\sc
FE}}(\mathbf{z},\mathbf{y}_{i}))=(1-3\alpha)\widetilde{D}(i)/n^{m}$ for every
$i\in[2n]$ and $\mathbf{z}\in[n]^{m}$, where $\mbox{{\sc
FE}}:[n]^{m}\times\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{N}$ is the encoding
function from Definition 8.5.

(vi)

For all other remaining vectors that are not assigned probability mass in the
above description, set their probabilities to $0$.

We define $D$ as the process of drawing a distribution $\widehat{D}$ according
to $D^{0}$, and permuting it using a uniformly random permutation
$\pi:[N]\rightarrow[N]$.

######  Remark 5 (Intuition behind the above hard distributions).

Unlike our adaptive algorithm to test $\mathcal{P}_{\mathrm{Gap}}$ (Algorithm
4 in Subsection 8.4), we can not determine the permutation $\pi$ first, and
then perform queries depending on the permutation $\pi$. When the permutation
$\pi$ is not known, even if we obtain a sample $\mathbf{X}$ and know that it
is equal to $\mbox{\sc FE}(\mathbf{z},\mathbf{x})_{\pi^{-1}}$ for some
$\mathbf{x}\in\\{0,1\\}^{n}$ and $\mathbf{z}\in[n]^{m}$, we can not even
decode a single bit of $\mathbf{x}$, unless we query too many of the indices
of $\mathbf{X}$. This follows from the properties of our encodings functions
SE and GE, used to construct FE (see Lemma 8.7), which “hides” $\mathbf{x}$
inside $\mathbf{X}$. Intuitively, this says that we have to query a
quasilinear number of the coordinates of the sample. Since the support
estimation problem admits a sample complexity lower bound of $\Omega(n/\log
n)$, the non-adaptive query complexity of $\widetilde{\Omega}(n^{2})$ follows
for non-adaptive algorithms. We will formalize this intuition below.

We will start with the following simple observation.

######  Observation 8.31.

The distribution $D_{yes}$ is supported over $\mathcal{P}_{\mathrm{Gap}}$.

###### Proof.

From the construction of $D_{yes}$, which is constructed by encoding the
elements of the support of the distribution $D_{yes}$ drawn from
$D_{yes}^{\mathrm{Supp}}$, it is clear that
$D_{yes}\in\mathcal{P}_{\mathrm{Gap}}$. ∎

Now we show that the distribution $D_{no}$ is supported over distributions
that are far from the property $\mathcal{P}_{\mathrm{Gap}}$.

######  Lemma 8.32 (Farness lemma).

$D_{no}$ is supported over distributions that are $\zeta^{2}\cdot\eta/5$-far
from $\mathcal{P}_{\mathrm{Gap}}$.

Before directly proceeding to the proof, let us first prove an additional
lemma which will be used in the proof of Lemma 8.32.

######  Lemma 8.33.

For any two distinct vectors $\mathbf{X}_{1}$ and $\mathbf{X}_{2}$ where
$\mathbf{X}_{1,\pi}$,
$\mathbf{X}_{2,\pi}\in\mathrm{Supp}(\widehat{D})\setminus(\\{\mathbf{U}\\}\cup\mathcal{S}\cup\mathcal{T})$
for $\widehat{D}\in\mathrm{Supp}(D_{no})$, and $\pi$ is the permutation for
which $\widehat{D}_{\pi}\in D^{0}_{no}$, we have
$\delta_{H}(\mathbf{X}_{1},\mathbf{X}_{2})\geq\zeta^{2}\cdot N/2$.

###### Proof.

We will use the properties of the function FE as mentioned in Observation 8.6.
Recall that for a string $\mathbf{z}\in[n]^{m}$, and a vector
$\mathbf{x}=(\mathbf{x}_{1},\ldots,\mathbf{x}_{n})\in\\{0,1\\}^{n}$, we have
$\mbox{{\sc
FE}}(\mathbf{z},\mathbf{x})=\mathbf{0}(\mathbf{1}^{b})\mathrm{SE}(\mathrm{GE}(\mathbf{z})_{1},\mathbf{x}_{1})\ldots\mathrm{SE}(\mathrm{GE}(\mathbf{z})_{n},\mathbf{x}_{n})$.
Now we have the following two cases:

  1. (a)

Suppose that for some vectors $\mathbf{x}\in\\{0,1\\}^{n}$, and
$\mathbf{z}_{1},\mathbf{z}_{2}\in[n]^{m}$ such that
$\mathbf{z}_{1}\neq\mathbf{z}_{2}$, we have $\mathbf{X}_{1,\pi}=\mbox{{\sc
FE}}(\mathbf{z}_{1},\mathbf{x})$ and $\mathbf{X}_{2,\pi}=\mbox{{\sc
FE}}(\mathbf{z}_{2},\mathbf{x})$. Then following Property (i) of FE in
Observation 8.6, we know that
$\delta_{H}(\mathbf{X}_{1},\mathbf{X}_{2})\geq\zeta^{2}\cdot N/2$ (noting that
permuting the two vectors by the permutation $\pi$ preserves their pairwise
distance).

  2. (b)

Suppose that for some vectors $\mathbf{z}\in[n]^{m}$, and
$\mathbf{x}_{1},\mathbf{x}_{2}\in\\{0,1\\}^{n}$ such that
$\mathbf{x}_{1}\neq\mathbf{x}_{2}$, we have
$\mathbf{X}_{1,\pi}=\mathrm{FE}(\mathbf{z},\mathbf{x}_{1})$ and
$\mathbf{X}_{2,\pi}=\mbox{{\sc FE}}(\mathbf{z},\mathbf{x}_{2})$. Then
following Property (ii) of FE in Observation 8.6, we know that
$\delta_{H}(\mathbf{X}_{1},\mathbf{X}_{2})\geq\zeta\cdot\delta_{H}(\mathbf{x}_{1},\mathbf{x}_{2})$.
From the choice of the vectors $\mathbf{y}_{1},\ldots,\mathbf{y}_{2n}$, we
know that $\delta_{H}(\mathbf{x}_{1},\mathbf{x}_{2})\geq n/3$. Thus, we can
say that in this case $\delta_{H}(\mathbf{X}_{1},\mathbf{X}_{2})\geq\zeta\cdot
nk/3>\zeta^{2}\cdot N/2$ (recalling that $\zeta<1/2$).

Combining the above, we conclude that
$\delta_{H}(\mathbf{X}_{1},\mathbf{X}_{2})\geq\zeta^{2}\cdot N/2$, for any two
distinct vectors $\mathbf{X}_{1},\mathbf{X}_{2}$ as above. ∎

###### Proof of Lemma 8.32.

Suppose that $\widehat{D}\in\mbox{Supp}(D_{no})$, and $\pi$ is the permutation
for which $\widehat{D}_{\pi}\in\mbox{Supp}(D^{0}_{no})$. We will bound
$d_{EM}(\widehat{D},\mathcal{P}_{\mathrm{Gap}})$. Let us denote the
distribution $D_{Y}\in\mathcal{P}_{\mathrm{Gap}}$ that is closest to
$\widehat{D}$, where $\pi_{Y}$ is the permutation for which
$D_{Y,\pi_{Y}}\in\mathcal{P}^{0}_{\mathrm{Gap}}$. Let us first define a new
distribution $\widetilde{D}_{Y}$ over $\\{0,1\\}^{N}$ as follows:

$\widetilde{D}_{Y}(\mathbf{X})=\left\\{\begin{array}[]{ll}\frac{1}{(1-3\alpha)}D_{Y}(\mathbf{X})&\mathbf{X}_{\pi_{Y}}\notin(\\{\mathbf{U}\\}\cup\mathcal{S}\cup\mathcal{T})\\\
0&\mbox{otherwise}\end{array}\right.$

Similarly, we also define another distribution $\widetilde{D}$ from
$\widehat{D}$, using $\pi$ instead of $\pi_{Y}$.

Now we have the following claim that bounds the distance between
$\widetilde{D}_{Y}$ and $\widetilde{D}$.

######  Claim 8.34.

$d_{EM}(\widetilde{D},\widetilde{D}_{Y})\geq\zeta^{2}\cdot\eta/4$.

###### Proof.

Following the definition of the property $\mathcal{P}_{\mathrm{Gap}}$, we know
that $\mbox{Supp}(\widetilde{D}_{Y})$ consists of possible encodings of $n$
distinct vectors from $\\{0,1\\}^{n}$, and there are at most $n^{m}$ valid
encodings of every such vector (as per the number of possible vectors
$\mathbf{z}\in[n]^{m}$ that are given as input to $\mathrm{GE}$). This implies
that the size of the support of the distribution $\widetilde{D}_{Y}$ is at
most $n^{m+1}$.

Since any distribution in the support of $D_{no}^{\mathrm{Supp}}$ has support
size at least $(1+2\eta)n$, following a similar argument as above, we infer
that the size of the support of $\widetilde{D}$ is at least
$(1+2\eta)n^{m+1}$. Moreover, by Lemma 8.33, we know that any pair of vectors
there has distance at least $\zeta^{2}/2$ (in relative distance). Also, as any
vector in the support of any distribution in the support of
$D_{no}^{\mathrm{Supp}}$ has probability mass that is multiple of $1/2n$, we
infer that every vector in the support of $\widetilde{D}$ has probability mass
at least $n^{-m-1}/2$ (as per Item (v) in the definition of $D^{0}$).

Summing up, we obtain that there are at least $2\eta\cdot n^{m+1}$ many
vectors in $\mbox{Supp}(\widetilde{D})$ that are $\zeta^{2}/4$-far (in
relative distance) from any vector in $\mbox{Supp}(\widetilde{D}_{Y})$, all of
whose weights are at least $n^{-m-1}/2$ 303030By the triangle inequality, if
we consider a Hamming ball of radius $\zeta^{2}/4$ around every vector in
$\mbox{Supp}(\widetilde{D}_{Y})$, there can be at most one vector from
$\mbox{Supp}(\widetilde{D})$ inside the ball.. Thus, the Earth Mover Distance
of $\widetilde{D}$ from $\widetilde{D}_{Y}$ is at least
$\zeta^{2}\cdot\eta/4$. ∎

Recall that we need to bound the distance between $\widehat{D}$ and $D_{Y}$.
From Claim 8.34, we know that
$d_{EM}(\widetilde{D},\widetilde{D}_{Y})\geq\zeta^{2}\cdot\eta/4$, where the
distributions $\widetilde{D}$ and $\widetilde{D}_{Y}$ are defined over the
encoding vectors. From the definition of $\widetilde{D}$ and
$\widetilde{D}_{Y}$ from $\widehat{D}$ and $D_{Y}$, we conclude that
$d_{EM}(D_{Y},\widehat{D})=(1-3\alpha)d_{EM}(\widetilde{D},\widetilde{D}_{Y})\geq\zeta^{2}\cdot\eta/5$.
∎

Now we prove that the distributions $D_{yes}$ and $D_{no}$ remain
indistinguishable to any non-adaptive tester, unless it performs
$\widetilde{\Omega}(n^{2})$ queries. We start with some definitions that will
be required for the proof. Recall that $N=\mathcal{O}(n\log n)$.

######  Definition 8.35 (Large and small query set).

A set of indices $I\subseteq[N]$ is said to be a _large_ if
$\left|I\right|>n/\log^{10}n$. Otherwise, $I$ is said to be a _small_.

Now we show that for a uniformly random permutation $\sigma$, and any $C_{j}$
as defined in the property $\mathcal{P}_{\mathrm{Gap}}$, with high probability
the size of the set of indices $\left|I\cap\sigma(C_{j})\right|$ will be
small, unless $I$ is a large query set.

######  Observation 8.36.

Let $\sigma:[N]\rightarrow[N]$ be a uniformly random permutation, and $C_{j}$
correspond to a “bit encoding set” of size $k$ (as per the definition of
$\mathcal{P}_{\mathrm{Gap}}$) for an arbitrary $j\in[n]$. For a fixed small
query set $I\subseteq[N]$, the probability that $|I\cap\sigma(C_{j})|$ is at
least $\zeta\cdot k$ is at most $1/n^{10}$.

###### Proof.

Let us define a collection of binary random variables $\langle X_{i}:i\in
I\rangle$ such that the following holds:

$X_{i}=\left\\{\begin{array}[]{ll}1&i\in\sigma(C_{j})\\\
0&\mbox{otherwise}\end{array}\right.$

Then as $\sigma$ is a uniformly random permutation,
$\mathrm{Pr}(X_{i}=1)=\frac{\left|\sigma(C_{j})\right|}{N}=\mathcal{O}(\frac{1}{n})$
for any $i\in[n]$. Now let us define another random variable
$X=\sum_{i=1}^{n}X_{i}$. Noting that $X=|I\cap\sigma(C_{j})|$, we obtain
$\mathbb{E}[X]=\mathcal{O}(1/\log^{10}n)$. By applying Hoeffding’s bound for
sampling without replacement (Lemma A.4), we can say that
$\mathrm{Pr}(X\geq\zeta\cdot k)\leq 1/n^{10}$. This completes the proof. ∎

Now let us define an event $\mathcal{E}_{I,j}$ as follows:

$\mathcal{E}_{I,j}:=\mbox{The query set $I$ satisfies
$|I\cap\sigma(C_{j})|\leq\zeta\cdot k$.}$

Now we are ready to prove that unless $\widetilde{\Omega}(n^{2})$ queries are
performed, no non-adaptive tester can distinguish $D_{yes}$ from $D_{no}$.

######  Lemma 8.37 (Indistinguishibility lemma).

With probability at least $2/3$, in order to distinguish $D_{yes}$ from
$D_{no}$, $\widetilde{\Omega}(n^{2})$ queries are necessary for any non-
adaptive tester.

###### Proof.

From our result on the adaptive $\varepsilon$-tester for
$\mathcal{P}_{\mathrm{Gap}}$, we know that $\widetilde{\mathcal{O}}(n)$
queries are sufficient for adaptively testing $\mathcal{P}_{\mathrm{Gap}}$.
Without loss of generality, let us assume that the non-adaptive tester takes
at most $n^{2}$ samples from the unknown distribution $D$ (since we can assume
that at least one query is performed in every sample). As per the definition
of a non-adaptive tester, assume that the samples taken are
$\mathbf{X}_{1},\ldots,\mathbf{X}_{s}$, and their respective query sets are
$I_{1},\ldots,I_{s}$ for some integer $s$.

Consider an event $\mathcal{E}$ as follows:

$\mathcal{E}:=\mbox{For every $\ell\in[s]$ for which $I_{\ell}$ is small and
every $j\in[n]$, the event $\mathcal{E}_{I_{\ell},j}$ occurs.}$

Since the non-adaptive tester takes at most $n^{2}$ samples, there can be at
most $n^{2}$ samples for which a small set was queried, that is, $s\leq
n^{2}$. Moreover, there are $n$ possible sets $C_{j}$ present in a sample.
Using the union bound, along with Observation 8.36, we can say that the event
$\mathcal{E}$ holds with probability at least $1-1/n^{7}$. Given that the
event $\mathcal{E}$ holds, we will now show that the induced distributions of
$D_{yes}$ and $D_{no}$ on small query sets are identical and independent of
the samples with large query sets.

######  Claim 8.38.

Assume that the event $\mathcal{E}$ holds. Then a non-adaptive tester that
uses at most $o(n/\log n)$ large query sets, can not distinguish $D_{yes}$
from $D_{no}$ with probability more than $1/4$.

###### Proof.

Since the distributions produced by $D_{yes}$ and $D_{no}$ are identical over
the respective permutations of
$(\\{\mathbf{U}\\}\cup\mathcal{S}\cup\mathcal{T})$, it is sufficient to prove
indistinguishability over the restrictions to the valid encodings of
$\mathbf{y}_{1},\ldots,\mathbf{y}_{2n}$ (as they appear in the definition of
$D^{0}$). Furthermore, we argue that this claim holds even if for every large
query set, the tester is provided with the entire vector that was sampled.

Given that the event $\mathcal{E}$ holds, regardless of whether the
distribution was produced by $D_{yes}$ or $D_{no}$, the restriction of the
samples to the small queried sets are completely uniformly distributed, even
when conditioned on the samples with large query sets (which are taken
independently of them). Thus we may assume that all samples with small query
sets are ignored by the tester, since the answers to these queries can be
simulated without taking any samples at all.

Finally, we appeal to the construction of the hard distributions $D_{yes}$ and
$D_{no}$ from $D_{yes}^{\mathrm{Supp}}$ and $D_{no}^{\mathrm{Supp}}$. By
Theorem 8.9, the distance between these two distributions over the sample
sequence is at most $1/4$, unless there were more than $o(n/\log n)$ samples
with large sets. This completes the proof of the claim. ∎

Combining Claim 8.38 with the above bound on the probability of the event
$\mathcal{E}$, we conclude that $\widetilde{\Omega}(n^{2})$ queries are
necessary for any non-adaptive tester to distinguish $D_{yes}$ from $D_{no}$
with probability at least $2/3$, that is, with a probability difference of at
least $1/3$. This concludes the proof of the lemma. ∎

## References

  * ABEF [17] Noga Alon, Omri Ben-Eliezer, and Eldar Fischer.  Testing hereditary properties of ordered graphs and matrices.  In FOCS, 2017.
  * ABR [16] Maryam Aliakbarpour, Eric Blais, and Ronitt Rubinfeld.  Learning and testing junta distributions.  In COLT, 2016.
  * ACK [18] Jayadev Acharya, Clément L Canonne, and Gautam Kamath.  A chasm between identity and equivalence testing with conditional queries.  Theory Of Computing, 2018.
  * ADK [15] Jayadev Acharya, Constantinos Daskalakis, and Gautam Kamath.  Optimal testing for properties of distributions.  NIPS, 2015.
  * AKNS [99] Noga Alon, Michael Krivelevich, Ilan Newman, and Mario Szegedy.  Regular languages are testable with a constant number of queries.  In FOCS, 1999.
  * BC [17] Tugkan Batu and Clément L Canonne.  Generalized uniformity testing.  In FOCS, 2017.
  * BC [18] Rishiraj Bhattacharyya and Sourav Chakraborty.  Property testing of joint distributions using conditional samples.  ACM Trans. Comput. Theory, 2018.
  * BCY [22] Arnab Bhattacharyya, Clément L. Canonne, and Joy Qiping Yang.  Independence testing for bounded degree bayesian network.  CoRR, abs/2204.08690, 2022.
  * BDKR [05] Tugkan Batu, Sanjoy Dasgupta, Ravi Kumar, and Ronitt Rubinfeld.  The complexity of approximating the entropy.  SIAM Journal on Computing, 2005.
  * BFLR [20] Omri Ben-Eliezer, Eldar Fischer, Amit Levi, and Ron D. Rothblum.  Hard properties with (very) short pcpps and their applications.  In ITCS, 2020.
  * BGMV [20] Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, and N. V. Vinodchandran.  Efficient distance approximation for structured high-dimensional distributions via learning.  In NeurIPS, 2020.
  * BHR [05] Eli Ben-Sasson, Prahladh Harsha, and Sofya Raskhodnikova.  Some 3cnf properties are hard to test.  SIAM J. Comput., 2005.
  * Bir [46] Garrett Birkhoff.  Three observations on linear algebra.  Univ. Nac. Tacuman, Rev. Ser. A, 1946.
  * BY [22] Arnab Bhattacharyya and Yuichi Yoshida.  Property Testing - Problems and Techniques.  Springer, 2022.
  * Can [20] Clément L. Canonne.  A Survey on Distribution Testing: Your Data is Big. But is it Blue?  Theory of Computing, (9), 2020.
  * Can [22] Clément L. Canonne.  Topics and Techniques in Distribution Testing: A Biased but Representative Sample.  March 2022.
  * CCK+ [21] Clément L. Canonne, Xi Chen, Gautam Kamath, Amit Levi, and Erik Waingarten.  Random restrictions of high dimensional distributions and uniformity testing with subcube conditioning.  In SODA, 2021.
  * CDKS [17] Clément L. Canonne, Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart.  Testing bayesian networks.  In COLT, 2017.
  * CDVV [14] Siu-On Chan, Ilias Diakonikolas, Paul Valiant, and Gregory Valiant.  Optimal algorithms for testing closeness of discrete distributions.  In SODA, 2014.
  * CFGM [16] Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, and Arie Matsliah.  On the power of conditional samples in distribution testing.  SIAM J. Comput., 2016.
  * Cha [00] B. Chazelle.  The Discrepancy Method: Randomness and Complexity.  Cambridge University Press, Cambridge, New York, 2000.
  * CJLW [21] Xi Chen, Rajesh Jayaram, Amit Levi, and Erik Waingarten.  Learning and testing junta distributions with sub cube conditioning.  In COLT, 2021.
  * CKS [20] Clément L. Canonne, Gautam Kamath, and Thomas Steinke.  The discrete gaussian for differential privacy.  In NeurIPS, 2020.
  * CM [19] Sourav Chakraborty and Kuldeep S. Meel.  On testing of uniform samplers.  In AAAI, 2019.
  * CRS [15] Clément L. Canonne, Dana Ron, and Rocco A. Servedio.  Testing probability distributions using conditional samples.  SIAM J. Comput., 2015.
  * CS [10] Artur Czumaj and Christian Sohler.  Sublinear-time algorithms.  In Property Testing - Current Research and Surveys. 2010.
  * DKN [14] Ilias Diakonikolas, Daniel M Kane, and Vladimir Nikishkin.  Testing identity of structured distributions.  In SODA, 2014.
  * DKS [18] Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart.  Sharp bounds for generalized uniformity testing.  In NeurIPS, 2018.
  * DLM+ [07] Ilias Diakonikolas, Homin K Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A Servedio, and Andrew Wan.  Testing for concise representations.  In FOCS, 2007.
  * DP [09] D.P. Dubhashi and A. Panconesi.  Concentration of Measure for the Analysis of Randomized Algoritms.  In Cambridge, 2009.
  * Fis [01] Eldar Fischer.  The art of uninformed decisions.  Bull. EATCS, page 97, 2001.
  * Fis [04] Eldar Fischer.  The art of uninformed decisions: A primer to property testing.  In Current Trends in Theoretical Computer Science: The Challenge of the New Century Vol 1: Algorithms and Complexity Vol 2: Formal Models and Semantics. World Scientific, 2004.
  * Gol [17] Oded Goldreich.  Introduction to Property Testing.  Cambridge University Press, 2017.
  * GOS+ [09] Parikshit Gopalan, Ryan O’Donnell, Rocco A. Servedio, Amir Shpilka, and Karl Wimmer.  Testing fourier dimensionality and sparsity.  In ICALP, 2009.
  * GR [97] Oded Goldreich and Dana Ron.  Property testing in bounded degree graphs.  In STOC, 1997.
  * GR [11] Oded Goldreich and Dana Ron.  On testing expansion in bounded-degree graphs.  In Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation. Springer, 2011.
  * GR [22] Oded Goldreich and Dana Ron.  Testing distributions of huge objects.  In ITCS, 2022.
  * GT [03] Oded Goldreich and Luca Trevisan.  Three theorems regarding testing graph properties.  Random Structures & Algorithms, 2003.
  * GW [21] Oded Goldreich and Avi Wigderson.  Non-adaptive vs adaptive queries in the dense graph testing model.  In FOCS, 2021.
  * Hau [95] David Haussler.  Sphere packing numbers for subsets of the boolean n-cube with bounded vapnik-chervonenkis dimension.  Journal of Combinatorial Theory, Series A, 1995.
  * Hoe [94] Wassily Hoeffding.  Probability inequalities for sums of bounded random variables.  In The collected works of Wassily Hoeffding. Springer, 1994.
  * Jan [04] Svante Janson.  Large Deviations for Sums of Partly Dependent Random Variables.  Random Structures & Algorithms, 2004.
  * Mat [99] J. Matoušek.  Geometric Discrepancy: An Illustrated Guide.  Algorithms and Combinatorics. Springer, Berlin, New York, 1999.
  * Mat [02] Jirí Matousek.  Lectures on Discrete Geometry, volume 212 of Graduate texts in mathematics.  Springer, 2002.
  * MPC [20] Kuldeep S. Meel, Yash Pote, and Sourav Chakraborty.  On testing of samplers.  In NeurIPS, 2020.
  * PA [95] J. Pach and P. K. Agarwal.  Combinatorial Geometry.  John Wiley & Sons, New York, NY, 1995.
  * Pan [08] Liam Paninski.  A coincidence-based test for uniformity given very sparsely sampled discrete data.  IEEE Transactions on Information Theory, 2008.
  * PM [21] Yash Pote and Kuldeep S. Meel.  Testing probabilistic circuits.  In NeurIPS, 2021.
  * Ron [08] Dana Ron.  Property testing: A learning theory perspective.  Found. Trends Mach. Learn., 2008.
  * Ron [09] Dana Ron.  Algorithmic and analysis techniques in property testing.  Found. Trends Theor. Comput. Sci., 2009.
  * RS [11] Ronitt Rubinfeld and Asaf Shapira.  Sublinear time algorithms.  SIAM J. Discret. Math., 2011.
  * RS [15] Dana Ron and Rocco A Servedio.  Exponentially improved algorithms and lower bounds for testing signed majorities.  Algorithmica, 2015.
  * Ser [10] Rocco A Servedio.  Testing by implicit learning: a brief survey.  Property Testing, pages 197–210, 2010.
  * Val [11] Paul Valiant.  Testing Symmetric Properties of Distributions.  SIAM Journal on Computing, 2011.
  * VC [15] Vladimir N Vapnik and A Ya Chervonenkis.  On the uniform convergence of relative frequencies of events to their probabilities.  In Measures of complexity, pages 11–30. Springer, 2015.
  * VN [53] John Von Neumann.  A certain zero-sum two-person game equivalent to the optimal assignment problem.  Contributions to the Theory of Games, 1953.
  * VV [10] Gregory Valiant and Paul Valiant.  A clt and tight lower bounds for estimating entropy.  In Electron. Colloquium Comput. Complex., 2010.
  * VV [17] Gregory Valiant and Paul Valiant.  Estimating the unseen: Improved estimators for entropy and other properties.  Journal of the ACM (JACM), 2017.
  * Yao [77] Andrew Chi-Chin Yao.  Probabilistic computations: Toward a unified measure of complexity.  In FOCS, 1977.

##  Appendix A Some probability results

######  Lemma A.1 (Multiplicative Chernoff bound [30]).

Let $X_{1},\ldots,X_{n}$ be independent random variables such that
$X_{i}\in[0,1]$. For $X=\sum\limits_{i=1}^{n}X_{i}$ and $\mu=\mathbb{E}[X]$,
the following holds for any $0\leq\delta\leq 1$.

$\mathrm{Pr}(\left|X-\mu\right|\geq\delta\mu)\leq
2\exp{\left(-{\mu\delta^{2}}/{3}\right)}.$