Let’s Try to Be More Tolerant: On Tolerant Property Testing and Distance Approximation

The first observation is that tolerant testing and distance approximation are essentially equivalent. In order to be more precise and concrete, fixing a property $𝒫$, we consider the following versions of the two notions. The tolerant-testing algorithm should work for every (with a dependence on $1/({ϵ}_2-{ϵ}_1)$), and the distance-approximation algorithm should provide an estimate that is within an additive term of $\delta$ from ${\text{dist}}_{𝒫}(O)$ (with a dependence on $1/\delta$). As stated above, in both cases the algorithm is allowed a small constant failure probability which we set to $1/3$, and the distance measure is assumed to be normalized to the range $[0,1]$.

Suppose first that we have a distance-approximation algorithm $𝒟𝒜$ for $𝒫$. In order to obtain a tolerant-testing algorithm $𝒯𝒯$, given , we simply run $𝒟𝒜$ with $\delta$ set to $({ϵ}_2-{ϵ}_1)/2$. If the estimate of ${\text{dist}}_{𝒫}(O)$ that $𝒟𝒜$ returns is at most ${ϵ}_1+\delta$, then $𝒯𝒯$ accepts, otherwise it rejects. The correctness of $𝒯𝒯$ follows directly from that of $𝒟𝒜$, and if the complexity of $𝒟𝒜$ grows with $g(1/\delta )$, then complexity of $𝒯𝒯$ grows with $g(2/({ϵ}_2-{ϵ}_1))$.

The other direction is slightly less straightforward. Suppose we have a tolerant testing algorithm $𝒯𝒯$. In order to obtain a distance-approximation algorithm $𝒟𝒜$, we perform an iterative geometric search for (an estimate of) ${\text{dist}}_{𝒫}(O)$ using $𝒯𝒯$. Initially we know that ${\text{dist}}_{𝒫}(O)\in [0,1]$, and we start by running $𝒯𝒯$ with ${ϵ}_1=1/3$ and ${ϵ}_2=2/3$. Depending on the outcome, we continue the search in either $[0,2/3]$ or $[1/3,1]$. In general, in each iteration the interval we consider is cut by a factor of $2/3$, until it reaches a size of $2\delta$, and the midpoint of the interval is returned. In order to bound the failure probability of $𝒟𝒜$, within each iteration we actually run $𝒯𝒯$ several times and take the majority outcome. Here too the correctness of $𝒟𝒜$ follows directly from that of $𝒯𝒯$. As for the complexity, there is at most an extra multiplicative factor of $\tilde{O}(\log (1/\delta ))$ due to the number of iterations and the number of repetitions in each iteration.

Transformations similar to the above can be applied to other (related) versions of tolerant testing and distance approximation, i.e., when the tolerant-testing algorithm works for $({ϵ}_1,{ϵ}_2)$ that are constrained and the distance-approximation algorithm is not purely additive.

Given the close relation between the two notions, we shall refer to the two interchangeably, and present results according to one of the two notions, where the choice depends on which is more natural/simpler to present.

The second observation is that if the queries of a standard testing algorithm are uniformly distributed (though not necessarily independent), then the algorithm provides some tolerance. Specifically, if the query complexity of the testing algorithm is $q(ϵ,n)$ (where $n$ is the size of the tested object), then it is a tolerant testing algorithm for ${ϵ}_1=O\left(1/q(ϵ,n)\right)$ and ${ϵ}_2=ϵ$. Hence, if $q(ϵ,n)=O(1/ϵ)$ (as is the case for example for testing linearity [10]), then we get a tolerant tester with ${ϵ}_1={ϵ}_2/c$, but the larger the query complexity, the weaker is the tolerance ensured.

In the context of standard testing, a simple argument [31] shows that if we have a proper learning algorithm (using queries and working under the uniform distribution) for a family of functions $ℱ$,²²2Such an algorithm performs queries to an unknown function $f$ that is promised to be in $ℱ$, and with high probability returns a hypothesis $h$ that belongs to $ℱ$ such that $h$ is $ϵ$-close to $f$ (with respect to the uniform distribution) then we can use it to obtain a testing algorithm for the property of membership in $ℱ$ with essentially the same complexity. An analogous statement holds regarding agnostic learning³³3An agnostic learning algorithm (using queries and working under the uniform distribution) is given query access to an unknown function $f$ that is not ensured to belong to $ℱ$ and returns a hypothesis $h$ that is $ϵ$-close a function $f^{\prime }$ in $ℱ$ that is closest to $f$. and tolerant testing.

While, as we shall see in the next sections, for some properties, tolerant testing is not (much) harder (in terms of its query complexity), than standard testing, in some cases it is much harder. This was initially shown by Fischer and Fortnow [26], and later strengthened by Ben-Eliezer, Fischer, Levi and Rothblum [4]. Both works provide properties of strings for which there is a standard tester whose complexity depends only on $ϵ$, while tolerant testing requires a number of queries that depends on the length, $n$ of the string. In [26] the latter is $\mathrm{\Omega }(n^{\alpha })$ for a constant $\alpha$ and in [4] it is $\mathrm{\Omega }(n/\text{polylog}(n))$.

A function $f:[n]\to R$, where $[n]=\{1,\mathrm{\dots },n\}$ and $R$ is a fully ordered range is monotone if $f(i)\le f(j)$ for every . The distance of $f$ to monotonicity, denoted ${\text{dist}}_{\text{mon}}(f)$, is the minimum fraction of elements in the domain $[n]$ on which the function $f$ should be modified so as to obtain a monotone function. In what follows, $f$ is viewed as an array with values in the range $R$, where the $i\text{<sup class="ltx\_sup">th</sup>}$ element of the array is $f(i)$. The first testing algorithm for monotonicity, by Ergun, Kannan, Kumar, Rubinfeld and Viswanathan [22], is nice and simple, and works as follows (assuming the values of $f$ are distinct, which can be assumed without loss of generality).

1. 1.

   Select, uniformly, independently at random, a sample of $s=2/ϵ$ indices in $[n]$, denoted $i_1,\mathrm{\dots },i_s$.

2. 2.

   For each selected index $i_r$, query $f$ on $i_r$, set $x_r=f(i_r)$, and perform a binary search on $f$ for $x_r$.

3. 3.

   If for some $x_r$, the binary search fails to return $i_r$, then Reject, otherwise, Accept.

Clearly, if $f$ is monotone (and its values are distinct), then the algorithm always accepts. On the other hand, if $f$ is $ϵ$-far from monotone, i.e., ${\text{dist}}_{\text{mon}}(f)>ϵ$, then it can be proved that at least an $ϵ$-fraction of the indices $i\in [n]$ will fail the binary search (i.e., a search for $f(i)$ does not end at $i$).

A naive idea for modifying this algorithm in order to obtain a distance-approximation algorithm (and hence a tolerant testing algorithm), is to estimate the fraction of indices $i$ for which the binary search fails, and to use this estimate for ${\text{dist}}_{\text{mon}}(f)$. This approach unfortunately does not work. While there are cases in which this fraction is a fairly good estimate of ${\text{dist}}_{\text{mon}}(f)$, in others it might significantly differ from ${\text{dist}}_{\text{mon}}(f)$. As an example for the former case, suppose (writing $f$ as an array), $f=[2,1,4,3,\mathrm{\dots },n,n-1]$. Then ${\text{dist}}_{\text{mon}}(f)$ equals $1/2$ (since it is both necessary and sufficient to modify half of the values of $f$ in order to obtain a monotone function), and the binary search would indeed fail on half of the indices $i\in [n]$. As an example of the latter case, consider $f=[1,2,\mathrm{\dots },n/2-1,n,n/2,\mathrm{\dots },n-1]$. Then ${\text{dist}}_{\text{mon}}(f)=1/n$, while the binary search will, here too, fail on half of the indices $i\in [n]$.

In [47] a tolerant testing algorithm for monotonicity was presented, which works for any ${ϵ}_1\ge 0$ and ${ϵ}_2=2{ϵ}_1+\delta$, whose query complexity is $\text{poly}(\log n,1/\delta )$. Consider the violation graph induced by $f$, denoted $G_f$. For each index $i$ there is a vertex in $G_f$, and there is an edge between $i$ and $j$ for if (and only if) $f(i)>f(j)$. It is not hard to verify that ${\text{dist}}_{\text{mon}}(f)$ equals the size of the minimum vertex cover in $G_f$. The algorithm in [47] works by approximating the size of a maximal matching in $G_f$.

At the heart of the algorithm is the following observation. Suppose we knew the median value of $f$, denoted $\text{med}(f)$. Then there is a perfect matching between $i\in \{1,\mathrm{\dots },n/2\}$ where $f(i)>\text{med}(f)$ and $j\in \{n/2+1,\mathrm{\dots },n\}$ where $f(j)\le \text{med}(f)$. The size of such a perfect matching can be estimated by sampling, and all remaining edges in $G_f$ are between pairs of vertices that are either both in $\{1,\mathrm{\dots },n/2\}$ or both in $\{n/2+1,\mathrm{\dots },n\}$. This suggests to continue recursively, using the “median based” approach taking care not to match vertices that were already matched in a higher level of the recursion. While a straightforward recursive implementation would be too costly (in particular due to the size of the recursion tree), as shown in [47], this can be overcome by defining a type of “approximate recursion tree” and sampling paths in it.

The aforementioned algorithm is indeed sublinear, and further has a polylogarithmic dependence on $n$, but the exponent of the polylog is $7$. Ailon, Chazelle, Comandur and Liu [1] were able to reduce the polylogarithmic dependence to logarithmic. To be precise, they provide an estimate in $[{\text{dist}}_{\text{mon}}(f),(2+\gamma )\cdot {\text{dist}}_{\text{mon}}(f)]$ for constant $\gamma$ by performing $\tilde{O}(\log n/{\text{dist}}_{\text{mon}}(f))$ queries. Saks and Seshadhri [51] showed how to get rid of the factor of $2$ in the quality of the estimate. Their algorithm computes an estimate in $[{\text{dist}}_{\text{mon}}(f),(1+\tau )\cdot {\text{dist}}_{\text{mon}}(f)]$ by performing $O{(1/({\text{dist}}_{\text{mon}}(f)\cdot \tau ))}^{O(1/\tau )})\cdot \text{poly}(\log n)$ queries.

There is a large body of work on testing monotonicity of functions $f:{\{0,1\}}^d\to \{0,1\}$, as well as some more recent works on tolerant testing. A sequence of works, starting with [30, 21], culminated in the work of Khot, Minzer and Safra [38], who gave a (non-adaptive) testing algorithm with query complexity $\tilde{O}(d^{1/2}/{ϵ}^2)$ (the square-root dependence on $d$ is necessary for non-adaptive algorithms [27]).

Tolerant testing in this context turns out to be much harder. Chen, De, Li, Nadimpali and Servedio [14] proved a lower bound of $\exp (d^{1/4}/{({ϵ}_2-{ϵ}_1)}^{1/2})$ for non-adaptive algorithms (an upper bound of $\exp (d^{1/2}/{({ϵ}_2-{ϵ}_1)}^{1/2})$ directly follows from what is known for agnostic learning). On the positive side, Pallavoor, Raskhodnikova and Waingerten [45] give a factor-$\tilde{O}(d^{1/2})$ approximation algorithm that is non adaptive and performs $\text{poly}(d,1/\alpha )$ queries where $\alpha$ is a lower bound on the distance to monotonicity of $f$ (they also show that this is essentially tight for non-adaptive algorithms). We note that Black, Kalemaj and Raskhodnikova [7] show that this result extends to real valued functions over the Boolean hypercube (improving on [24]).

Other properties of sparse graphs that were studied in the context of distance approximation include $k$-edge connectivity, subgraph-freeness, cycle-freeness and Eulerianity [43], strong connectivity in directed graphs and bounded diameter [11], as well as $3$-colorability in planar graphs [35]. A strong separation result between standard and tolerant testing for bounded-degree graphs was proved by Goldreich and Wigderson [33].

Much of the focus in the property-testing literature has been on testing properties of graphs in the adjacency-matrix model. In this model, which is appropriate for studying properties of dense graphs, graphs are represented by their $n\times n$ adjacency matrices, so an algorithm may perform vertex-pair queries. Namely, for any choice of two vertices $u$ and $v$, an algorithm can query whether there is an edge between $u$ and $v$. The distance to a property is defined as the fraction of entries in the matrix that should be modified so as to obtain the property (i.e., the minimum number of edges that should be added/removed to obtain the property, divided by $n^2$).

Fischer and Newman [28] proved that every graph property for which there is a (standard) testing algorithm in the adjacency-matrix model that performs $q(ϵ)$ queries, has an additive distance-approximation algorithm that performs $q^{\prime }(\delta )$ queries, where $\delta$ is the additive approximation parameter. They showed that $q^{\prime }(\delta )$ is upper bounded by a function that is a tower of exponentials of height $q(\delta /2)$. Gishboliner, Kushnir and Shapira [29] significantly improved this upper bound on $q^{\prime }(\delta )$ to double exponential in $q(\delta /2)$, and also showed that for hereditary properties the transformation loss is single-exponential (improving on [36]). Finally we note that for some properties there are known additive distance-approximation algorithms with query complexity $\text{poly}(1/\delta )$. These include $k$-colorability (by approximating the size of the maximum-$k$-cut) [31] as well as more general hereditary partition properties, induced $P_3$ and $P_4$-freeness, and chordality [25].