Online Versus Offline Adversaries in Property Testing

Let $s=s[1]\circ \mathrm{\cdots }\circ s[r],$ where $s[i]=s{[i]}_1\mathrm{\dots }s{[i]}_m$ for all $i\in [r]$, be the input string over the alphabet $\mathrm{\Sigma }$. If $s\in {𝒞}_{m,r}$, then repetition-test always accepts $s$.

Suppose that string $s$ is $\epsilon$-far from ${𝒞}_{m,r}$. Let ${plurality}_{i\in [r]}(a_i)$ denote a function that takes inputs $a_1,\mathrm{\dots },a_r\in \mathrm{\Sigma }$ and outputs the most frequent among them, resolving ties arbitrarily. Let $\widehat{w}$ be the string of length $m$ defined by ${\widehat{w}}_j={plurality}_{i\in [r]}s{[i]}_j$ for all $j\in [m]$. Since $s$ is $\epsilon$-far from ${𝒞}_{m,r}$, we can bound the distance between the input string and $\widehat{w}$ repeated $r$ times:

For all $j\in [m]$ and $a\in \mathrm{\Sigma }$, let $p_j(a)$ denote $\underset{i\in [r]}{Pr}[s{[i]}_j=a]$, the probability that a randomly chosen repetition of the $j$-th character in $s$ is equal to $a$. The probability that one iteration of the loop in repetition-test accepts $s$ is

Hence, each iteration of the loop in repetition-test rejects with probability at least $\epsilon$. Therefore, repetition-test accepts $s$ with probability at most ${\left(1-\epsilon \right)}^{2/\epsilon }\le e^{-\epsilon \cdot 2/\epsilon }\le \frac{1}{6}$. $\mathrm{⊲}$

Next, we analyze the tester ${𝒯}^{\prime }$.

If the input $s$ is in ${𝒫}^r$ then $s=w^r$ for some string $w\in 𝒫$. In this case, repetition-test accepts with probability $1$, and ${𝒯}^{\prime }$ accepts with the same probability as $𝒯$. Next, suppose $s$ is $\epsilon$-far from ${𝒫}^r$. Consider the string $\widehat{w}\in {\mathrm{\Sigma }}^m$, where ${\widehat{w}}_j={plurality}_{i\in [r]}s{[i]}_j$ for all $j\in [m]$. Recall that the repetition code is defined as ${𝒞}_{m,r}=\{s^r:s\in {\mathrm{\Sigma }}^m\}$. Observe that the distance from $s$ to ${𝒞}_{m,r}$ is equal to ${\delta }_H(s,{\widehat{w}}^r)$. If this distance is at least $\frac{\epsilon }{2}$ then, by 3.7, repetition-test accepts with probability at most $\frac{1}{6}$, completing the proof.

Now assume We will show that, in this case, the simulation of $𝒯$ in Algorithm 1 accepts with probability at most $\frac{1}{6}$. Specifically, we consider two failure events: let $E_1$ be the event that the simulation of $𝒯$ feeds $𝒯$ at least one query answer inconsistent with $\widehat{w}$, and $E_2$ be the event that the simulation of $𝒯$ accepts string $\widehat{w}$. We will show that $Pr[E_1]\le \frac{1}{12}$ and $Pr[E_2]\le \frac{1}{12}$. Then a union bound over $E_1$ and $E_2$ completes the proof.

Since $s$ is $\epsilon$-far from ${𝒫}^r$ and , we get

implying that ${\delta }_H(\widehat{w},𝒫)\ge \frac{\epsilon }{2}$. Since $𝒯$ is a tester for $𝒫$ with amplified success probability, and $\widehat{w}$ is $\frac{\epsilon }{2}$-far from $𝒫$, algorithm $𝒯$ accepts with probability at most $\frac{1}{12}$ when run on input $\widehat{w}$ and with proximity parameter $\frac{\epsilon }{2}$; that is, $Pr[E_2]\le \frac{1}{12}$.

Next we analyze $Pr[E_1]$. Fix $j\in [m]$, and let $a_j$ denote the answer provided by ${𝒯}^{\prime }$ to query $j$ in the simulation. If ${𝒯}^{\prime }$ does not reject while simulating this query, then

The inequality in (2) follows from the following simple observation: once $s{[i_1]}_j$ has been sampled, if it is not the plurality, then for each $k\in \{2,\mathrm{\dots },d\}$, every subsequent $s{[i_k]}_j$ is equal to $s{[i_1]}_j$ with probability at most $\frac{1}{2}$. By our choice of $c_1$, and a union bound over all the $c_0\cdot q(m,\epsilon /2)$ queries made by $𝒯$, the probability of $E_1$ is at most $\frac{1}{12}$.

Since ${𝒯}^{\prime }$ can accept only if $E_1\cup E_2$ occurs, a union bound over $E_1$ and $E_2$ implies that ${𝒯}^{\prime }$ is indeed a tester for ${𝒫}^r$, and has error probability at most $\frac{1}{6}$ when no adversary is present. $\mathrm{⊲}$

Finally, we prove the lifting lemma.

First, we argue that the probability ${𝒯}^{\prime }$ (Algorithm 1) queries a corrupted index is small. Recall that $n=m\cdot r$ is the length of the input to ${𝒯}^{\prime }$ and that $c_0\cdot q(m,\epsilon )$ is the query complexity of $𝒯$ with proximity parameter $\epsilon$. Let $q^{\prime }=q^{\prime }(n,\epsilon )=\frac{8}{\epsilon }+c_0\cdot q(m,\frac{\epsilon }{2})\log (c_1\cdot q(m,\frac{\epsilon }{2}))$ be the number of queries made by ${𝒯}^{\prime }$. Then, there are at most $q^{\prime }t$ corruptions at any point during the execution. Moreover, each query made by ${𝒯}^{\prime }$ is an index that is uniform over the set of corresponding indices in the $r$ different segments of $s$. It follows that each query made by ${𝒯}^{\prime }$ is corrupted with probability at most $\frac{q^{\prime }t}{r}$. By a union bound over the $q^{\prime }$ queries,

The upper bound follows from the hypothesis that $t\le \frac{\delta \cdot r}{{[q(m,\epsilon /2)\log q(m,\epsilon /2)]}^2}$, that $q(m,\epsilon )=\mathrm{\Omega }\left(\frac{1}{\epsilon }\right)$, and that $\delta$ is a sufficiently small constant. By a union bound, the probability that ${𝒯}^{\prime }$ errs in the presence of the adversary is at most the probability ${𝒯}^{\prime }$ errs when no adversary is present plus the probability ${𝒯}^{\prime }$ queries a corrupted index. By 3.8 and (3), this probability is at most $\frac{1}{3}$, which completes the proof of Lemma 3.5. $◀$

We first make the following observation: if $x$ is $\epsilon$-far from ${𝒫}^{(\tau )}$, then every collection of $\tau$ distinct elements occupies at most a $1-\epsilon$ fraction of the indices in $x$. Suppose we sample uniformly random elements from $x$ until we have seen $\tau +1$ distinct elements. Notice that while we have seen at most $\tau$ distinct elements, our next sample is a new distinct element with probability at least $\epsilon$ (the at most $\tau$ distinct elements we have seen can have probability mass at most $1-\epsilon$). Let $X_i$ be the number of samples to get the $i$-th distinct element given we have seen $i-1$ distinct elements, and set $X={\sum }_{i=1}^{\tau +1}{X}_i$. Then $𝔼[X]\le (\tau +1)/\epsilon$, and hence, by Markov’s inequality, the probability we need more than $3(\tau +1)/\epsilon$ samples is at most $\frac{1}{3}$. This analysis inspires the following simple tester:

Sample $s=3(\tau +1)/\epsilon$ elements from $x$ and accept if and only if there are at most $\tau$ distinct symbols from $[n]$ in the sample (not counting the erasure symbol $⟂$).

Repeating the tester constantly many times suffices to make the failure probability smaller than $\frac{1}{10}$. $\mathrm{⊲}$

Recall that Lemma 4.3 states that to prove a lower bound on the randomness complexity of testing in the online model, it suffices to prove a lower bound on the query complexity of testing in the standard model. In Lemma 4.6, we show a lower bound on the query complexity of testing $\tau$-Distinct-Elements. Our lower bound is a direct corollary of the lower bound of [32].

We use the following fact to argue that we can assume the tester is sample-based with no loss of generality.

Since ${𝒫}^{(\tau )}$ is symmetric, we can without loss of generality consider sample-based testers. First, we prove the lower bound for two-sided error testers. The essence of our proof is a reduction from the hard instances used in [32] for estimating the support size of a distribution. While we cannot use the lower bound of [32] as a black box, we can nonetheless leverage their hard instances. Indeed, combining Theorem 1, Fact 5, and the remarks regarding the support size of their hard distributions (following Definition 12) from [32], we obtain the following immediate corollary.

While the distributions in [32] are defined over $ℝ$, they all have support size at most $m$. Thus, we can, without loss of generality, consider distributions over $[m]$. Indeed, given a distribution $𝒟$ over $ℝ$, the distribution ${𝒟}^{\pi }$ obtained by choosing a uniformly random permutation $\pi$ of $[m]$, and then mapping the $i$-th element in the support of $𝒟$ to $\pi (i)$, has domain $[m]$ and the same support size as $𝒟$. Moreover, if two distributions ${𝒟}_0$ and ${𝒟}_1$ each have support size at most $m$, then for $b\in \{0,1\}$, the distribution ${𝒟}_b^{\pi }$ can be generated by first, sampling a random permutation $\pi$ of $[m]$, second, sampling from ${𝒟}_b$, and third, sending each distinct sample to the first available element of $\pi$. Thus, any algorithm which distinguishes ${𝒟}_1^{\pi }$ and ${𝒟}_0^{\pi }$ can be used to distinguish ${𝒟}_0$ and ${𝒟}_1$ with the same sample complexity.

To apply 4.8 in our setting, we note that whenever $m\le \frac{\sqrt{n}}{\log n}$, there exists $x\in {[m]}^n$ such that the distribution obtained by sampling a uniform index in $x$ has total variation distance at most $\frac{m}{n}=\frac{1}{\sqrt{n}\log n}$ from $𝒟$. Thus, for sufficiently large $n$, there exist strings $x^{+},x^{-}\in {[m]}^n$ such that $x^{+}$ has at most $m(\frac{1}{2}+\alpha )$ distinct symbols, and the distributions generated by sampling from $x^{+}$ and $x^{-}$ have total variation distance $\frac{1}{\sqrt{n}\log n}$ from ${𝒟}^{+}$ and ${𝒟}^{-}$, respectively. Let $\tau =m(\frac{1}{2}+\alpha )$ and $\epsilon =\frac{1}{2}-2\alpha -o(1)$, then $x^{+}\in {𝒫}^{(\tau )}$ and $x^{-}$ is $\epsilon$-far from ${𝒫}^{(\tau )}$. By 4.8, every algorithm for distinguishing $x^{+}$ from $x^{-}$ uses $\mathrm{\Omega }\left(\frac{m}{\log m}\right)=\mathrm{\Omega }\left(\frac{\tau }{\log \tau }\right)$ samples. By 4.7, every tester for ${𝒫}^{(\tau )}$ has query complexity $\mathrm{\Omega }\left(\frac{\tau }{\log \tau }\right)$.

To prove the one-sided error lower bound, it suffices to note that every one-sided error algorithm must accept if its sample contains at most $\tau$ symbols. Thus, every one-sided error tester requires $\mathrm{\Omega }(\tau )$ samples. This completes the proof of Lemma 4.6. $◀$

First, for all $\tau \in \mathbb{N}$, we construct an offline-erasure-resilient tester for $\tau$-Distinct-Elements, and second, we argue that the tester can be simulated with $O(\log n)$ random bits and no additional queries. Let $𝒯$ be the tester given by 4.5. Recall that $𝒯$ accepts if and only if the number of nonerased symbols in the sample is at most $\tau$. Below, we argue that $𝒯$ is an $\alpha$-offline-erasure-resilient $\epsilon$-tester.

Let $x$ be an $\alpha$-erased string in ${[n]}^n$. If some completion of $x$ is in ${𝒫}^{(\tau )}$, then the number of nonerased symbols in the sample drawn by $𝒯$ is at most $\tau$, so the algorithm accepts. Next we argue that $𝒯$ accepts with probability at most $\frac{1}{4}$ when every completion of $x$ is $\epsilon$-far from ${𝒫}^{(\tau )}$. Let $x^{⟂}$ denote the erased portion of $x$, and $x^{\top }$ denote the nonerased portion of $x$. Notice that $|x^{\top }|=(1-\alpha )n$, and thus if $x^{\top }$ is $\frac{\epsilon }{1-\alpha }$-close to ${𝒫}^{(\tau )}$, then there is a completion of $x$ that is $\epsilon$-close to ${𝒫}^{(\tau )}$ (change $\epsilon n$ symbols in $x^{\top }$ and fill out $x^{⟂}$ with an arbitrary symbol from $x^{\top }$). Thus, if every completion of $x$ is $\epsilon$-far from ${𝒫}^{(\tau )}$, then $x^{\top }$ is $\frac{\epsilon }{1-\alpha }$-far from ${𝒫}^{(\tau )}$. By the proof of 4.5, a set of $O\left(\frac{\tau (1-\alpha )}{\epsilon }\right)$ uniform and independent samples from $x^{\top }$ contains at least $\tau +1$ distinct symbols with probability at least $\frac{9}{10}$. Moreover, a sample of $O\left(\frac{\tau }{\epsilon }\right)$ elements from $x$ contains $\mathrm{\Omega }\left(\frac{\tau (1-\alpha )}{\epsilon }\right)$ such samples from $x^{\top }$ with probability at least $\frac{9}{10}$. By the union bound, $𝒯$ accepts $x$ with probability at most $\frac{1}{4}$.

It remains to show that $𝒯$ can be simulated by a tester ${𝒯}^{\prime }$ that uses $O(\log n)$ random bits and has the same query complexity as $𝒯$. 4.9 states that any randomized oracle machine that solves a promise problem can be simulated using $\log n+\log \log |\mathrm{\Sigma }|+O(1)$ random bits, where $|\mathrm{\Sigma }|$ is the size of the alphabet. This fact was originally proven by Goldreich and Sheffet [18] and is stated as an exercise in [14]. We use the statement from the exercise since it is more convenient for our setting.

Let $\mathrm{\Pi }$ be the promise problem defined by $\alpha$-offline-erasure-resilient $\epsilon$-testing ${𝒫}^{(\tau )}$. By the first part of the proof, there exists a randomized oracle machine $𝒯$ that solves $\mathrm{\Pi }$ with error probability at most $\frac{1}{4}$. Applying 4.9 directly, we see that $𝒯$ can be simulated by a tester ${𝒯}^{\prime }$ using $\log n+\log \log |\mathrm{\Sigma }|+O(1)$ random bits; since $\mathrm{\Sigma }=[n]$, tester ${𝒯}^{\prime }$ uses $O(\log n)$ random bits, and has error probability at most $\frac{1}{3}$. To complete the proof, it suffices to note that ${𝒯}^{\prime }$ has the same query complexity as $𝒯$. $◀$

Next, we prove the part of the theorem regarding testing $\tau$-Distinct-Elements in the online erasure model.

We will show that for all $\tau \in \mathbb{N}$, the tester given by 4.5 is online-erasure-resilient. Let $𝒯$ be the tester for $\tau$-Distinct-Elements given by 4.5. Recall that $𝒯$ accepts if and only if the number of nonerased symbols in its sample is at most $\tau$. We show that $𝒯$ can test in the presence of a $t$-online-erasure-oracle, by arguing that with high constant probability, none of the queries made by $𝒯$ are erased. Notice that with proximity parameter $\epsilon$, the tester makes $O\left(\frac{\tau }{\epsilon }\right)$ queries. Thus, there are $O\left(\frac{t\cdot \tau }{\epsilon }\right)$ erasures at every point during the execution of $𝒯$. Since $𝒯$ makes uniform and independent queries, the probability that any particular query is erased is $O\left(\frac{t\cdot \tau }{n\epsilon }\right)$. Since $𝒯$ makes $O\left(\frac{\tau }{\epsilon }\right)$ queries, we can apply the union bound to see that some query is erased with probability at most $O\left(\frac{t\cdot {\tau }^2}{n{\epsilon }^2}\right)$. By the hypothesis that $t\le {\left(\frac{.01\epsilon \sqrt{n}}{\tau }\right)}^2$, we have $O\left(\frac{t\cdot {\tau }^2}{n{\epsilon }^2}\right)\le .01$ – that is, $𝒯$ sees an erasure with probability at most $.01$. By 4.5, the algorithm $𝒯$ is a $t$-online-erasure-resilient $\epsilon$-tester for ${𝒫}^{(\tau )}$. Moreover, since an erasure cannot increase number of distinct nonerased symbols in $x$, tester $𝒯$ has one-sided error. This completes the proof of Item 2.

To see why Item 3 holds, recall that by Lemma 4.6, there exists $\epsilon \in (0,1)$ such that for all $n,\tau \in \mathbb{N}$ with $\tau \le \frac{\sqrt{n}}{\log n}$, every $\epsilon$-tester for ${𝒫}^{(\tau )}$ has query complexity $\mathrm{\Omega }\left(\frac{\tau }{\log \tau }\right)$. Similarly every tester with one-sided error has query complexity $\mathrm{\Omega }(\tau )$. Thus, applying Lemma 4.3, the reduction from query complexity to randomness complexity, suffices to complete the proof. $◀$