Property testing in other metrics?

Question

There is a large literature on "property testing" -- the problem of making a small number of black box queries to a function $f\colon\{0,1\}^n \to R$ to distinguish between two cases:

1. $f$ is a member of some class of functions $\mathcal{C}$

2. $f$ is $\varepsilon$-far from every function in class $\mathcal{C}$.

The range $R$ of the function is sometimes Boolean: $R = \{0,1\}$, but not always.

Here, $\varepsilon$-far is generally taken to mean Hamming distance: the fraction of points of $f$ that would need to be changed in order to place $f$ in class $\mathcal{C}$. This is a natural metric if $f$ has a Boolean range, but seems less natural if the range is say real-valued.

My question: does there exist a strand of the property-testing literature that tests for closeness to some class $\mathcal{C}$ with respect to other metrics?

Answer 1

Yes, there is! I will give three examples:

1. Given a set S and a "multiplication table" over S x S, consider the problem of determining if the input describes an abelian group or whether it is far from one. Friedl, Ivanyos, and Santha in STOC '05 showed that there is a property tester with query complexity polylog(|S|) when the distance measure is with respect to the edit distance of multiplication tables which allows addition and deletion of rows and columns from the multiplication table. The same problem was also considered in the Hamming distance model by Ergun, Kannan, Kumar, Rubinfeld and Viswanathan (JCSS '00) where they showed query complexity of O~(|S|^{3/2}).

2. There is a large amount of work done on testing graph properties where the graphs are represented using adjacency lists and there is a bound on the degree of each vertex. In this case, the distance model is not exactly Hamming distance but rather how many edges can be added or deleted while preserving the degree bound.

3. In the closely related study of testing properties of distributions, various notions of distance between distributions have been studied. In this model, the input is a probability distribution over some set and the algorithm gets access to it by sampling from the set according to the unknown distribution. The algorithm is then required to determine if the distribution satisfies some property or is "far" from it. Various notions of distance have been studied here, such as L_1, L_2, earthmover. Probability distributions over infinite domains have also been studied here (Adamaszek-Czumaj-Sohler, SODA '10).

Answer 2

It's usually not called property testing (and it really isn't), but there is a large body of work on deciding properties of a matrix by looking at a small induced minor. This is very similar to the goal in property testing. See for instance the paper by Rudelson and Vershynin:

http://portal.acm.org/citation.cfm?id=1255449

There are earlier papers by Frieze-Kannan. The point is that typically the metric they use is some matrix norm such as spectral norm, frobenius norm or cut norm. If you want, you can think of some of these results as property testing algorithms in a metric other than Hamming distance.

Answer 3

The work of Berman, Raskhodnikova, and Yaroslavtsev [1] introduces testing of functions $f\colon [n]^d\to \mathbb{R}$ with regard to $L_p$ distances, for $p\geq 1$. It is meant to capture situations where the magnitude of the noise is what matters (rather than the more brittle Hamming distance). (Some results pertaining to $L_p$ distances can also be found in [2]).

See e.g Chapter 12 (Section 12.4) of Goldreich's Introduction to Property Testing for a discussion of testing with regard to edit and $L_p$ distances.

(Note that $L_1$ testing is not the same as distribution testing (typically with regard to $L_1$/total variation) as (i) the object testing is not the same (functions whether probability distributions), (ii) the type of access is different (query- vs. sample-based, typically), and (iii) the $L_1$ distance as defined in [1] is normalized (by $n$) for scaling issues, and is not in distribution testing (as the mass is always $1$ by definition).

---

[1] $L_p$ Testing. Berman, Raskhodnikova, and Yaroslavtsev, STOC'14.

[2] Testing $k$-Monotonicity. Canonne, Grigorescu, Guo, Kumar, and Wimmer, ITCS'17.