A property is said to be invariant under a permutation $\pi$ if permuting the data points by this permutation leaves the property unchanged.

Invariance under permutations seems to help with property testing, see e.g. Algebraic Property Testing: The Role of Invariance by Tali Kaufman and Madhu Sudan, Property Testing of Equivalence under a Permutation Group Action by Sourav Chakraborty and Laszlo Babai, and Invariance in Property Testing by Madhu Sudan.

What is the general intuition for the invariance under permutations helping testing properties, e.g. testing properties of graphs?


1 Answer 1


The very general intuition is that the larger the symmetry group of a property, the easier it is to analyze its testability.

The idea is the following. Suppose you have a property $\mathcal{P}$, defined as a collection of subsets of some domain $D$, and suppose that $\mathcal{P}$ is invariant under a permutation $\pi : D \to D$. In other words, a subset $S \subseteq D$ is in $\mathcal{P}$ iff $\pi(S)$ is also in $\mathcal{P}$. In testing, we want to determine whether a given set $S$ is in $\mathcal{P}$ or "far" from $\mathcal{P}$ by choosing a small number of points $X_1,\dots,X_q \in D$, querying whether each of them is a member of $S$ or not, and then making a decision based on the results of the queries. Suppose that a particular choice of points $z_1,\dots,z_q \in D$ constitutes a valid test. Then, the observation is that $\pi^{-1}(z_1),\dots,\pi^{-1}(z_q)$ also must constitute a valid test. Because using the test $\pi^{-1}(z_1),\dots,\pi^{-1}(z_q)$ on $S$ is the same as using the test $z_1, \dots, z_q$ on $\pi(S)$, and we know that $S \in \mathcal{P}$ iff $\pi(S) \in \mathcal{P}$. So, if $\mathcal{P}$ has a group of symmetry $\Pi \leq \mathsf{Sym}(D)$, then the entire orbit $\{(\pi(z_1),\dots,\pi(z_q)): \pi \in \Pi\}$ consists of valid tests. Thus, the larger the group $\Pi$ is, the more tests can be generated from a single test, and in fact, for many natural invariance groups, all possible tests can be generated from the orbits of a very restricted class of tests. When this is the case, it becomes much easier to give conditions for when a property is testable and when it's not.

Now, coming back to graph properties, because every graph property is invariant under relabeling of vertices, Goldreich and Trevisan (2003) formalized this above argument to show that the test for any graph property consists of querying induced subgraphs from the given graph. This result was crucial in a later combinatorial characterization of testability for graph properties.

In your question, you seem to be asking what happens if there are even more symmetries known for the graph property at hand. As far as I know, there's no general study of this question, mainly because there's already a precise characterization of testability for general graph properties. It might be interesting to ask which graph properties are "easily testable", meaning the query complexity is polynomial in the proximity parameter, and here there's no general characterization known...so putting additional symmetry restrictions on the property might make answering the question easier.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.