<p>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:</p>

<p><a href="http://portal.acm.org/citation.cfm?id=1255449">http://portal.acm.org/citation.cfm?id=1255449</a></p>

<p>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.</p>

CC BY-SA 2.5
2010-08-18T15:04:14.257Z
2010-08-18T15:04:14.257Z
Moritz
<p>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]).</p>

<p>See e.g Chapter 12 (Section 12.4) of Goldreich's <a href="http://www.wisdom.weizmann.ac.il/~oded/pt-intro.html" rel="nofollow noreferrer"><em>Introduction to Property Testing</em></a> for a discussion of testing with regard to edit and $L_p$ distances.</p>

<p>(Note that $L_1$ testing is <em>not</em> 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 <em>not</em> in distribution testing (as the mass is always $1$ by definition).</p>

<hr>

<p>[1] <em>$L_p$ Testing</em>. Berman, Raskhodnikova, and Yaroslavtsev, STOC'14.</p>

<p>[2] <em>Testing $k$-Monotonicity</em>. Canonne, Grigorescu, Guo, Kumar, and Wimmer, ITCS'17.</p>

CC BY-SA 3.0
2018-01-19T17:53:38.697Z
2018-01-19T21:05:03.900Z
2018-01-19T21:05:03.900Z
Clement C.
<p>Yes, there is!  I will give three examples:</p>

<ol>
<li><p>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.  <a href="http://doi.acm.org/10.1145/1060590.1060614">Friedl, Ivanyos, and Santha in STOC '05</a> showed that there is a property tester with query complexity polylog(|S|) when the distance measure is with respect to the <i>edit distance</i> 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 <a href="http://dx.doi.org/10.1006/jcss.1999.1692">Ergun, Kannan, Kumar, Rubinfeld and Viswanathan (JCSS '00)</a> where they showed query complexity of O~(|S|^{3/2}).</p></li>
<li><p>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.</p></li>
<li><p>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 (<a href="http://www.siam.org/proceedings/soda/2010/SODA10_006_adamaszekm.pdf">Adamaszek-Czumaj-Sohler, SODA '10</a>).</p></li>
</ol>

CC BY-SA 2.5
2010-08-18T23:29:26.237Z
if it's not too much trouble, could you link to the papers referenced ? ideally the doi/acm version.
Suresh Venkat
CC BY-SA 2.5
2010-08-18T15:41:50.527Z
To elaborate on #1, a even (IMHO) more natural problem is to test for monotonicity, where the distance is the # of positions to be deteled in a permutation to make it monotone. 
This has been studied in the aforementioned JCSS'00 paper (leading up to the most recent FOCS'10 paper by Comandur-Saks).
Alex Andoni
CC BY-SA 2.5
2010-08-18T15:00:33.813Z
2010-08-19T02:12:23.663Z
2010-08-19T02:12:23.663Z
arnab
<p>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: </p>

<ol>
<li><p>$f$ is a member of some class of functions $\mathcal{C}$</p></li>
<li><p>$f$ is $\varepsilon$-far from every function in class $\mathcal{C}$. </p></li>
</ol>

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

<p>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. </p>

<p>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? </p>

<reference-request><lg.learning><metrics><property-testing><black-box>
Property testing in other metrics?
Aaron Roth
# Property testing in other metrics?

(Asked by: username_0 on 2010-08-18)

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?

**Tags:** reference-request, lg.learning, metrics, property-testing, black-box


---

## 3 answers

### Answer by username_3 on 2010-08-18. Score: 19 | Accepted answer

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](http://doi.acm.org/10.1145/1060590.1060614) 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)](http://dx.doi.org/10.1006/jcss.1999.1692) 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](http://www.siam.org/proceedings/soda/2010/SODA10_006_adamaszekm.pdf)).

> **Comments:**
> **username_5**: To elaborate on #1, a even (IMHO) more natural problem is to test for monotonicity, where the distance is the # of positions to be deteled in a permutation to make it monotone.  This has been studied in the aforementioned JCSS'00 paper (leading up to the most recent FOCS'10 paper by Comandur-Saks).  
> **username_4**: if it's not too much trouble, could you link to the papers referenced ? ideally the doi/acm version.  

---

### Answer by username_1 on 2010-08-18. Score: 7

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 by username_2 on 2018-01-19. Score: 4

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*](http://www.wisdom.weizmann.ac.il/~oded/pt-intro.html) 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.


---

