%% ToC#249, v002/a009.tex Fischer - Fortnow \documentclass{toc} \tocdetails{% volume=2, number=9, year=2006, firstpage=173, received={April 3, 2006}, published={September 25, 2006} } \bibliographystyle{tocplain} \runningauthor{E. Fischer and L. Fortnow} \runningtitle{Tolerant Versus Intolerant Testing} \copyrightauthor{Eldar Fischer and Lance Fortnow} \begin{document} \begin{frontmatter}[classification=text] \title{Tolerant Versus Intolerant Testing for Boolean Properties} \tocpdftitle{Tolerant Versus Intolerant Testing} \tocpdfauthor{Eldar Fischer and Lance Fortnow} \author[Eldar]{Eldar Fischer\thanks{Research supported in part by an Israel Science Foundation grant number 55/03.}}% \author[Lance]{Lance Fortnow}% \tockeywords{Property Testing, Tolerant Testing, PCP of Proximity} \begin{abstract} A property tester with high probability accepts inputs satisfying a given property and rejects inputs that are far from satisfying it. A tolerant property tester, as defined by Parnas, Ron and Rubinfeld, must also accept inputs that are close enough to satisfying the property. We construct two properties of binary functions for which there exists a test making a constant number of queries, but yet there exists no such tolerant test. The first construction uses Hadamard codes and long codes. Then, using Probabilistically Checkable Proofs of Proximity as constructed by Ben-Sasson et\ al., we exhibit a property which has constant query intolerant testers but for which any tolerant tester requires $n^{\Omega(1)}$ queries. \end{abstract} \tocams{68Q99, 68W20} \tocacm{G.3, F.2.2} \end{frontmatter} \section{Introduction}\label{i} Combinatorial property testing deals with the following task: For a fixed $\epsilon>0$ and a fixed property $R$, distinguish using as few queries as possible (with high confidence) between the case that an input of length $m$ satisfies $R$, and the case that the input is $\epsilon$-far from satisfying $R$, \ie, the input differs in at least an $\epsilon$-fraction of the bits from every string satisfying $R$. In our context the inputs are Boolean, and the distance from $R$ is measured by the minimum number of bits that have to be modified in the input to make it satisfy $R$, divided by the input length $m$. For the purpose here we are mainly interested in tests that have a number of queries that depends only on the approximation parameter $\epsilon$ and is independent of the input length. Properties that admit such algorithms are called \emph{testable}. Blum, Luby, and Rubinfeld~\cite{blr} were the first to investigate a question formulated in terms of property testing, and Rubinfeld and Sudan~\cite{rsc} formally defined the general notion of property testing. Goldreich, Goldwasser, and Ron~\cite{ggr} investigated property testing in the combinatorial context, where they first formalized the testing of combinatorial objects such as graphs. In recent years the field of property testing has enjoyed rapid growth, as witnessed in the surveys of Ron~\cite{rtt} and Fischer~\cite{fts}. Since even a correct input may have a small amount of noise, Parnas, Ron, and Rubinfeld~\cite{prr} have recently started investigating property testing algorithms which are guaranteed to accept (with high confidence) not only inputs that satisfy the property, but also inputs that are sufficiently close to satisfying it. The following formal definition highlights this distinction. \begin{definition} Given a property $R$, an \emph{$\epsilon$-test} for $R$ is a randomized algorithm that is guaranteed to accept with probability at least $\frac{2}{3}$ any input that satisfies $R$, and is guaranteed to reject with probability at least $\frac{2}{3}$ any input that is $\epsilon$-far from satisfying $R$. We say that the property is \emph{testable} if for every $\epsilon>0$ there exists an $\epsilon$-test whose number of queries is independent of the input size $m$. A \emph{$1$-sided $\epsilon$-test} for $R$ is an $\epsilon$-test as above that in addition is guaranteed to accept any input that satisfies $R$ with probability $1$. A \emph{tolerant $(\epsilon,\delta)$-test} for $R$ is an $\epsilon$-test for $R$ that in addition is guaranteed to accept with probability at least $\frac{2}{3}$ any input that is $\delta$-close to satisfying $R$, where an input is said to be \emph{$\delta$-close to satisfying $R$} if it is not $\delta$-far from satisfying $R$. We say that a property is \emph{tolerantly testable} if for every $\epsilon>0$ there exists a constant $\delta>0$ for which there exists a $(\epsilon,\delta)$-test whose number of queries is independent of $m$. \end{definition} Many properties that are testable as per the definition above are also tolerantly testable. Alon et\ al.~\cite{aet} implicitly give tolerant tests for the testable graph properties, and such tests also follow from the canonical testing result of Goldreich and Trevisan~\cite{gtt}. Fischer and Newman~\cite{fne} prove an even stronger result that every testable graph property is also $(\epsilon,\delta)$-testable for \emph{any} $\delta<\epsilon$, showing that for the dense graph model testability in fact implies that the distance of an input graph from a property can be estimated using a number of queries that depends only on the additive approximation term. For non-Boolean properties there are easy examples of properties where the number of queries required for an $\epsilon$-test may be much smaller than the number required for an $(\epsilon,\delta)$-test. Consider the following example that uses bounds on testing invertability and inverseness of functions, implicit in the works of Erg\"un et\ al.~\cite{ees} and Erg\"un, Kumar, and Rubinfeld~\cite{ekr} about testing for element distinctness and multiset equality. Consider the property of a sequence of $n^2$ numbers consisting of (the representation of) $n-1$ copies of a function $f:\{1,\ldots,n\}\to\{1,\ldots,n\}$ and one copy of its inverse function $g$. An easy test follows from uniformly sampling values $i$ and checking that indeed $f(g(i))=g(f(i))=i$ (as well as sampling from the supposed $n-1$ copies of $f$ and checking that they agree with each other on $i$). On the other hand, a tolerant test would have to ignore the representation of $g$ altogether because the encoding of $g$ makes up only a tiny part of the total input, and testing whether a function $f$ has some inverse is hard. If we try to directly convert such examples to properties of Boolean functions, for example by taking the Boolean representation of the values of $f$ and $g$, then with some tweaking we can see a difference in the number of required queries between a tolerant and an intolerant test, but it will typically be between two different constants. This still leaves open the question of whether every property, for which there exists a (constant query complexity) $\epsilon$-test for every $\epsilon>0$, admits also constant query complexity tolerant tests. In this paper we prove that this is not the case, and construct properties that admit intolerant tests with a constant number of queries but admit no such tolerant tests. \begin{theorem}\label{mnt} There exists a property $R$, such that for every $\epsilon$ there exists an $\epsilon$-test for $R$ making a number of queries that depends only on $\epsilon$ (and not on the input size), while for every constant $0<\delta<\frac{1}{4}$ and $q$ there exists no tolerant $(\frac{1}{4},\delta)$-test making only $q$ queries (for large enough inputs). \end{theorem} The proof of the above combines results from several topics of property testing, including one of the very first results in this field, linearity testing~\cite{blr}. Alternatively, using the recently constructed Probabilistically Checkable Proofs of Proximity by Ben-Sasson et\ al.~\cite{bep} we can prove a strengthening of \expref{Theorem}{mnt}. \begin{theorem}\label{mnt2} There exists a property $R$, such that for every $\epsilon$ there exists an $\epsilon$-test for $R$ making a number of queries that depends only on $\epsilon$ (and not on the input size), while there exists a constant $c>0$ such that for every constant $0<\delta<\frac14$ there exists no tolerant $(\frac{1}{4},\delta)$-test making only $n^c$ queries (for large enough inputs). \end{theorem} The proof of \expref{Theorem}{mnt2} relies on the heavy machinery of Probabilistically Checkable Proofs. We present its proof following a separate direct proof of \expref{Theorem}{mnt} (which, if analyzed carefully, would have given an $\Omega(\log \log n)$ lower bound on the query complexity). The rest of the paper is organized as follows. In \expref{Section}{p} we present the basic building blocks for the proof of \expref{Theorem}{mnt}, for which we need results that were proven all throughout the history of the field, and in \expref{Section}{m} we string them together proving \expref{Theorem}{mnt}. \expref{Section}{s} contains the proof of \expref{Theorem}{mnt2}, which gives better lower bounds but requires less direct methods. These results originally appeared in the Proceedings of the 20th IEEE Conference on Computational Complexity~\cite{conf}. \section{Preliminaries}\label{p} We base our first property on Hadamard codes and long codes. In the following we somewhat abuse notation, and when clear from context refer by the word ``code'' both to a legal codeword, and to the set of all allowed codewords. In particular, the term ``a property of a code'' refers to a subset of the set of codewords. In the following we will use the fact that some properties of codes are testable (\ie\ there exists an $\epsilon$-test for the property in the usual sense if we know in advance that the input is a legal codeword), while other properties of codes are not testable. A \emph{Hadamard code} is a string $x$ of length $2^n$, for which there exists a string $y$ of length $n$ such that for every $i$ the $i$th bit of $x$ is equal to $y\cdot i$ (where we use the binary representation of $i$, and the ``dot product'' is defined over $\mathbb{Z}_2$ as $a\cdot b=\bigoplus_{j=1}^na_jb_j$). Equivalently, a string $x$ is a Hadamard code if and only if $f(i)=x_i$ is a linear function over $\mathbb{Z}_2$. We shall use the two definitions interchangeably. Let $f_1,\ldots,f_{2^{2^n}}$ be an enumeration of all of the functions on inputs of length $n$, according to the lexicographic order on the sequence of their values on the domain $\{0,1\}^n$. A \emph{long code} is a string $x$ of length $2^{2^n}$ such that $x_i=f_i(y)$ for every $j$ for some fixed $y$ of length $n$. Here too there is a useful equivalence. The string $x$ is a long code if and only if $g(i)=x_i$ is a dictator function, \ie, when there exists a $j$ for the above $g:\{0,1\}^{2^n}\to\{0,1\}$ such that for all $z\in\{0,1\}^{2^n}$, $g(z)=z_j$ (note that in particular a long code is also linear). We get the correspondence by setting $g(i)=f_i(j)$. The extreme redundancy of long codes has proven itself to be very useful in complexity theory, for example in the optimal inapproximability results of H\r{a}stad~\cite{hoi}. The possibility for testing that a function is a Hadamard code in fact stems from one of the very first results in the field of property testing. \begin{lemma}[\cite{blr}] \label{blrlem} For every $\epsilon$, the property that a Boolean function $f:\{0,1\}^n\to\{0,1\}$ is linear (over the field $\mathbb{Z}_2$) is testable with a $1$-sided test using a number of queries that depends only on $\epsilon$. \end{lemma} Since the property that a function $h:\{0,1\}^n\to\{0,1\}$ is a Hadamard code of some $y=b_1,\ldots, b_n$ is identical to the property of $h$ being linear over $\mathbb{Z}_2$, we can use the above for testing this. Testing for long codes follows from somewhat more recent results. \begin{lemma}[\cite{bgs,prs}] \label{bgslem} For every $\epsilon$, the property that a Boolean function $f:\{0,1\}^m\to\{0,1\}$ is a dictator function is testable with a $1$-sided test using a number of queries that depends only on $\epsilon$. \end{lemma} Properties of long codes of binary strings can be easily tested for, since a proper long code of a string contains its corresponding value for every possible function. Thus, given a code $L$, we can test it by looking at its value for the function that describes the tested property itself. Further details are provided in the proof of \expref{Lemma}{rlem} below. On the other hand, there exist properties of Hadamard codes that are hard to test. Such properties have been used to prove the existence of properties that can be easily tested only using a quantum algorithm, by Buhrman, Fortnow, Newman, and R\"{o}hrig~\cite{beq}, and another property of Hadamard codes with additional features was implicitly used also by Fischer et\ al.~\cite{fej}. \begin{lemma}[\cite{beq}] \label{uhl} There exist properties of Hadamard codes that cannot be $\frac{1}{3}$-tested (even by a $2$-sided test) with a constant number of queries. \end{lemma} The work of Fischer et\ al.~\cite{fej} implies that one cannot distinguish with a constant number of queries between a linear Boolean function depending on exactly $\lfloor\frac{1}{2}n\rfloor$ variables and one that depends on exactly $\lfloor\frac{1}{2}n\rfloor+2$ variables, and so the property of being a Hadamard code of a string with exactly $\lfloor\frac{1}{2}n\rfloor$ nonzero bits is not testable. We use such a property of a Hadamard code because it will always yield an easy ``long-code assisted test,'' despite the Hadamard code being hard to test in an ``unassisted'' manner. In essence, our input is supposed to contain a Hadamard code and a long code that extends the Hadamard code (\ie\ both codes encode the same ``original value''). Using the discussion above together with the self-correction features of Hadamard codes and long codes, we will show how to create a test by checking the Hadamard code against the long code, and then testing the long code for our property. However, we cannot test the Hadamard code alone if we are not allowed to look at the long code. The notion of ``assisted tests'' reminds one of the essence of the work of Erg\"{u}n, Kumar, and Rubinfeld~\cite{ekr} and Batu, Rubinfeld, and White~\cite{brw}, only here the ``witness'' can have exponential size because we can do weighting by replication. For the construction with the better lower bounds, we will use a strong result of Ben-Sasson et\ al.~\cite{bep} about assisted tests. With all the above components in hand, we are now ready to construct a property that has an easy test but not a tolerant one. \section{Proof of \expref{Theorem}{mnt}}\label{m} In the following, for a parameter $n$, we consider inputs whose size is $(2^n+1)2^{2^n}$. We consider the input as composed of one function $L$ from the set of functions $\{f \mid f:\{0,1\}^n\to\{0,1\}\}$ to $\{0,1\}$ (the function $L$ takes $2^{2^n}$ bits to write down), and $l=2^{2^n}$ functions $h_1,\ldots,h_l$ from $\{0,1\}^n$ to $\{0,1\}$ (each such function takes $2^n$ bits to write down), where all functions are represented by their truth tables. We pick a property $U$ of Hadamard codes that satisfies \expref{Lemma}{uhl}, and define \emph{Property R} as the property of the input satisfying the following: \emph{All the functions $h_1,\ldots,h_l$ are identical and are equal to a Hadamard code of some $x\in\{0,1\}^n$ that satisfies property $U$, and the function $L$ is the long code of this same $x$}. \begin{lemma} \label{rlem} Property $R$ admits a $1$-sided $\epsilon$-test with a constant number of queries for every $\epsilon$. \end{lemma} \begin{proof} We assume that $\epsilon<\frac{1}{8}$, and do the following. \begin{itemize} \item Repeating independently $100\epsilon^{-1}$ times, we select a uniformly random $x\in\{0,1\}^n$, a uniformly random $1\leq i\leq l$, and check that the bit corresponding to $h_1(x)$ is indeed equal to that of $h_i(x)$. If any of these checks fails, we reject the input. \item Using \expref{Lemma}{blrlem} we perform a $\frac12\epsilon$-test of $h_1(x)$ for the property of being a linear function (\ie\ being a Hadamard code of some $b_1,\ldots,b_n$). We amplify the success probability of the test to $\frac{19}{20}$, so that the probability of a false positive answer will be no greater than $\frac{1}{20}$. \item Using \expref{Lemma}{bgslem} we perform an $\epsilon$-test of $L(f)$ for the property of being a long code of some $x\in\{0,1\}^n$. Again we amplify the success probability of the test to $\frac{19}{20}$. \item Denote for any $y\in\{0,1\}^n$ by $\chi_y:\{0,1\}^n\to\{0,1\}$ the corresponding Hadamard code (\ie\ for $y=(a_1,\ldots,a_n)$, we set $\chi_y(b_1,\ldots,b_n)=\bigoplus_{i=1}^n a_ib_i$). We perform 100 iterations of the following: We select a uniformly random $y\in\{0,1\}^n$, a uniformly random $f:\{0,1\}^n\to\{0,1\}$, and check that $h_1(y)=L(f)\oplus L(f\oplus \chi_y)$, rejecting the input if any of the checks fail. \item Now let $u(x):\{0,1\}^n\to\{0,1\}$ denote the indicator function of Property $U$, \ie\ $u(x)=1$ if and only if the Hadamard code of $x$ satisfies Property $U$. We now perform 100 iterations of choosing a uniformly random $f:\{0,1\}^n\to\{0,1\}$, and checking that $L(f)\oplus L(f\oplus u)=1$, rejecting if any of these checks fail. \end{itemize} On one hand, it is clear that an input that satisfies Property $R$ will be accepted with probability $1$. On the other hand, if an input is accepted with probability at least $\frac{2}{3}$, then all of the following hold. \begin{itemize} \item The portion of the input that corresponds to $h_2(x),\ldots,h_l(x)$ is $\frac12\epsilon$-close to being $l-1$ copies of the function $h_1(x)$. \item $h_1(x)$ is $\frac12\epsilon$-close to being the Hadamard code of some $(b_1,\ldots,b_n)\in\{0,1\}^n$. With the previous item this means that the restriction of the input to $h_1(x),\ldots,h_l(x)$ is $\epsilon$-close to being $l$ copies of the Hadamard code of $b_1,\ldots,b_n$. \item $L(f)$ is $\epsilon$-close to being a long code of some $(c_1,\ldots,c_n)\in\{0,1\}^n$. \item $(b_1,\ldots,b_n)=(c_1,\ldots,c_n)$. Otherwise every iteration of the check in the fourth item above would fail with probability at least $\frac{1}{8}$. This is since doing such a check between an actual Hadamard code and an actual long code of differing strings would fail with probability $\frac12$; the additional loss of $\frac{3}{8}$ in the probability is because $h_1(x)$ is only guaranteed to be $\frac{1}{16}$ close to being the Hadamard code of $b_1,\ldots,b_n$, and $L(f)$ is only guaranteed to be $\frac{1}{8}$-close to the long code of $c_1,\ldots,c_n$. \item $b_1,\ldots,b_n$ satisfy Property $U$ (and with the above items this means that the input as a whole is in fact $\epsilon$-close to satisfying Property $R$). The reason is that otherwise every iteration of the check in the fifth item of the test would fail with probability at least $1-2\epsilon>\frac{3}{4}$. \end{itemize} The above complete the proof of the test. \end{proof} \begin{lemma} There exist no constants $\delta$ and $q$, for which property $R$ can be $(\frac{1}{4},\delta)$-tested for every $n$ using only $q$ queries. \end{lemma} \begin{proof} We may assume that $\delta<\frac{1}{12}$. We show that if there exists a $(\frac{1}{4},\delta)$-test for $R$, then for every large enough $n$ there exists a $\frac{1}{3}$-test for $U$ (not necessarily a tolerant one) making only $q$ queries, which is known not to exist by \expref{Lemma}{uhl}. Given an input $h:\{0,1\}^n\to\{0,1\}$ which we would like to test for Property $U$, we construct an input for Property $R$ as follows: $h_1,\ldots,h_l$ will all be identical to $h$, and $L$ will be arbitrarily set to the all-zero function. Note that any single query to the new input can be answered by making a single query (or no query) to the original input. The next thing to note is that for $n$ large enough, if $h$ satisfies $U$ then the new input is $\delta$-close to satisfying $R$, because for $n$ large enough the number of bits in the function $L$ is less than a $\delta$-fraction of the total number of bits in the input, while $h_1,\ldots,h_l$ clearly satisfy all requirements not concerning $L$ in the definition of $R$. On the other hand, if the new input is $\frac{1}{4}$-close to satisfying Property $R$, then $h$ is necessarily $\frac{1}{3}$-close to satisfying Property $U$, because of what the definition of Property $R$ states for $h_1,\ldots,h_l$. We thus obtain our $\frac13$-test for $U$. \end{proof} The above two lemmas complete the proof of \expref{Theorem}{mnt}. \section{PCPs of Proximity and \expref{Theorem}{mnt2}}\label{s} This section gives a proof of \expref{Theorem}{mnt2} that strengthens \expref{Theorem}{mnt}. We first define the construction and cite the main lemma that we will use. Property testing has some common origins with Probabilistically Checkable Proofs, and Erg\"{u}n et\ al.~\cite{ekr} and Batu et\ al.~\cite{brw} investigated this connection further, with regards to using a PCP witness for an input. \begin{definition} Given a promise problem and a Boolean input $v_1,\ldots,v_n$, a ($1$-sided) \emph{PCP witness} for the problem is a set of functions $f_1,\ldots,f_l$, where $l$ is polynomial in $n$, satisfying the following. \begin{itemize} \item Each of the functions has a number of variables bounded by a constant independent of $n$, that may include variables from $v_1,\ldots,v_n$ as well as from an additional set of (polynomially many) Boolean variables $w_1,\ldots,w_m$. \item If $v_1,\ldots,v_n$ should be accepted according to the promise problem, then there exists an assignment to $w_1,\ldots,w_m$ that together with $v_1,\ldots,v_n$ satisfies all the functions $f_1,\ldots,f_l$. \item If $v_1,\ldots,v_n$ should be rejected according to the promise problem, then there exists no assignment to $w_1,\ldots,w_m$ for which more than $\frac{1}{2}l$ of the functions are satisfied. \end{itemize} A \emph{PCP of Proximity} is a PCP witness for the promise problem of accepting all inputs that satisfy a given property $P$, and rejecting all inputs that are $\epsilon$-far from $P$ for a given distance parameter $\epsilon$. \end{definition} A recent strong result, concerning the existence of PCPs of Proximity for all properties decidable in polynomial time, is given by Ben-Sasson et\ al.~\cite{bep}. \begin{lemma}[Special case of~\cite{bep}]\label{ppl} If $P$ is a property of $v_1,\ldots,v_n$ that is decidable by a circuit of size $k$, and $t<\log\log k/\log\log\log k$, then there exists a PCP of Proximity for $P$ with distance parameter $1/t$. Moreover, the number of additional variables and the number of functions are both bounded by $k^2$, and each function depends on $O(t)$ variables. \end{lemma} On the other hand, there is a plethora of lower bound results for properties which belong to low complexity classes (\eg\ \cite{aer,bhr,fns}) and most of them would work fine for us. We will choose the property $U=\{uu^Rvv^R \mid u,v\in\{0,1\}^*\}$, where $w^R$ denotes the reversal of the word $w$. \begin{lemma}[Alon et\ al.~\cite{aer}]\label{npl} Property $U$ can be computed in polynomial time, while any $\frac{1}{3}$-test for $U$ requires at least $\Omega(\sqrt{n})$ queries (where $n$ is the input size). \end{lemma} We let $p(n)$ be a polynomial bound on the circuit size for deciding Property $U$ on inputs of size $n$. To construct the property to fulfill \expref{Theorem}{mnt2}, we first assume without loss of generality that $n$ divides $p(n)$ and set $t_n=\lfloor\log\log\log p(n)\rfloor$, so in particular $t_n<\log\log p(n)/\log\log\log p(n)$ for a sufficiently large $n$. We consider inputs of size $n(p(n))^2$. We label the first $(n-t_n)(p(n))^2$ bits by $(v_{i,j})_{1\leq i\leq n,1\leq j\leq (n-t_n)(p(n))^2/n}$, and the rest of the bits by $(w_{i,j})_{1\leq i\leq (p(n))^2,1\leq j\leq t_n}$. We define \emph{Property $R$} as the set of inputs satisfying all of the following. \begin{itemize} \item For every $i$, $1\leq i\leq n$, and $j$, $13/\epsilon$, and do the following. \begin{itemize} \item Repeating independently $100\epsilon^{-1}$ times, we select a uniformly random $i$, $1\leq i\leq n$, a uniformly random $j$, $10$, so that there exists no $\delta$ for which Property $R$ can be $(\frac{1}{4},\delta)$-tested with $n^c$ queries. \end{lemma} \begin{proof} We assume that $\delta<\frac{1}{12}$. Let $c_1>0$ be such that Property $U$ cannot be $\frac{1}{3}$-tested with $n^{c_1}$ queries, and let $c_2>0$ be such that $n(p(n))^21$. We set $c=c_1c_2$, and prove that a $(\frac{1}{4},\delta)$-test with $n^c$ queries for Property $R$ implies (for all $n$ large enough) a $\frac{1}{3}$-test with $n^{c_1}$ queries for Property $U$, leading to a contradiction. Given an input $v_1,\ldots,v_n$ which we would like to $\frac{1}{3}$-test, we construct an input of size $n(p(n))^2$ to test for Property $R$ as follows. We set $v_{i,j}=v_i$ for all $1\leq i\leq n$ and $1\leq j\leq (n-t_n)(p(n))^2/n$, and arbitrarily set $w_{i,j}=0$. As in \expref{Section}{m}, it is clear that a query to the new input can be simulated by performing at most one query to the original input. Also, for $n$ large enough, if $v_1,\ldots,v_n$ satisfy Property $U$ then the new input is $\delta$-close to satisfying Property $R$ (because the $w_{i,j}$ form less than a $\delta$ fraction of the input bits). On the other hand if the new input is $\frac{1}{4}$-close to satisfying Property $R$ then the original input was $\frac{1}{3}$-close to satisfying Property $U$. The above implies that a $(\frac{1}{4},\delta)$-test for Property $R$ that makes at most $(n(p(n))^2)^c