Testing triangular properties (2/2)

novembre, 18, 2009

To find the beginning of the triangular adventure, you should read this post.

To prove the lemma we use the following theorem that I am not proving in this post (if you want the proof, just let me know).

Consider N urns each filled with m balls, and the following process: pick a ball in an urn chosen uniformly at random until the chosen urn is empty. The probability that one had to pick more than O(N^{\frac{m-1}{m}}) balls tends to a nonzero constant as N goes to infinity.

Proof (of the lemma)
To each triangle in C associate an urn, filled with 3 balls labeled with the vertices of the triangle corresponding to the urn in which they are put. It is clear that if one applies the process described in the theorem above then in time \Theta(|C|^{2/3}) one will have picked the three balls of an urn with constant probability, and the labels of these balls form a triangle in C.

Now we can characterize the number of elements that must be pick at random in order to obtain a complete triangle (since we cannot directly sample triangles but only atomic elements). The following lemma gives the result.

Let C be a family of triangles as defined in one of the previous lemma.
If one picks \Theta(\epsilon^{-1/3}n^{2/3}) different elements in V uniformly at random, then one has picked a complete triangle in C with a probability that tends to a constant as n goes to infinity.

Let N=k\epsilon^{-1/3}n^{2/3} where k is a constant, and suppose (X_i)_{1\leq i\leq N} is a family of random variables such that X_i is chosen uniformly at random in V-\{X_1,\ldots,X_{i-1}\}. The variable X_i takes its value inside \hat{C} with probability \frac{|\hat{C}-\{X_1,\ldots,X_{i-1}|\}}{|V|} which is greater than

\frac{|\hat{C}|-N}{|V|} \geq \frac{\epsilon n-N}{n} \geq \epsilon - k(\epsilon n)^{-1/3}.

where the first inequality comes from one of our lemmas.
So, the expectation of the number N_C of elements chosen in \hat{C} is lower-bounded as follows:

\exp[N_C]\geq N\cdot(\epsilon - k(\epsilon n)^{-1/3})=k(\epsilon n)^{2/3}-k^2(\epsilon n)^{1/3}.

Then, using the Chernoff bound (see for instance the book by Motwani and Raghavan) we obtain

Prob[N_C<\frac{k(\epsilon n)^{2/3}}{2}]\leq Prob[N_C<\frac{\exp[N_C]+k(\epsilon n)^{1/3}}{2}]

Prob[N_C<\frac{k(\epsilon n)^{2/3}}{2}] \leq prob[N_C<\exp[N_C](1-\frac{1}{2}+\frac{k(\epsilon n)^{1/3}}{2\exp[N_C]})]

Prob[N_C<\frac{k(\epsilon n)^{2/3}}{2}] \leq prob[N_C<\exp[N_C](1-\frac{1}{2}+\frac{k(\epsilon n)^{1/3}}{2\exp[N_C]})]

Prob[N_C<\frac{k(\epsilon n)^{2/3}}{2}] < e^{-\frac{1}{2}\exp[N_C]\cdot(\frac{1}{2}-\frac{k(\epsilon n)^{1/3}}{2\exp[N_C]})^2}

But from one of the previous equation it follows that (\frac{1}{2}-\frac{k(\epsilon n)^{1/3}}{2\exp[N_C]})^2 tends to 1/2 as n goes to infinity, implying that Prob[N_C<k(\epsilon n)^{2/3}/2] tends to 0 as n goes to infinity.

One shoud notice that k(\epsilon n)^{2/3}/2=\Theta(|C|^{2/3}), so that with with high-probability one can apply the previous lemma as N_C\geq k(\epsilon n)^{2/3}/2, which concludes the proof.

At last, we have now our final result…

The following algorithm is a one-sided \epsilon-tester for any triangular property P, which requests O(\epsilon^{-2/3}n^{4/3}) values of the function \phi that is to be tested.

The algorithm
\epsilon-tester for any triangular property
Input: a function \phi:V\times V \rightarrow S and a triangular property P.
Output: the answer to whether or not \phi is \epsilon-far from having property P.

  • Select a random set of vertices V’ of size \epsilon^{-1/3}n^{2/3}.
  • Request all the values of the restriction of \phi to the complete graph K_{\epsilon^{-1/3}n^{2/3}} induced by V’
  • Check on all the triangles whether P is satisfied or not.
  • Return 0 if a triangle is bad, and 1 else.

The last thing to do? proving the proposition…

It is clear that if the function \phi has property P then it is also true for its restriction to the induced subgraph, so the algorithm accepts. If \phi is \epsilon-far from having property P, then the first lemma implies the existence of a set B which in turn implies the existence of a set C as described in the second lemma. The third lemma then implies that with high probability the restriction of \phi to the chosen subgraph will not have property P, which is exactly what is checked by the algorithm. So, The algorithm will reject with high probability. This concludes the proof.

Comments are closed.

Picture: courtesy of Abby Blank