Reminder: This post contains 1982 words
· 6 min read
· by Xianbin
In this post, we will see how to use Yao’s minmax principle in Property Testing.
Definitions
We say that a function \(f: \{0,1\}^n \to \{0,1\}\) is monotone if \(f(x) \leq f(y)\) for all \(x \leq y\) (i.e., \(x_i \leq y_i ,\forall i\in[n]\)).
Now, let us consider monotone functions and graph labelings. Let \(\vec{G}= (V, E)\) be a directed graph. We say \(f\) is monotone on \(\vec{G}\) if \(f(u) \leq f(v)\) for all \((u,v) \in E\). A pair of vertices \((u,v)\) is violated if \(u \leq v\) and \(f(u) > f(v)\).
Notice that monotonicity of labelings of acyclic graphs corresponds to monotonicity of functions on posets.
A poset is a set \(P\) equipped with a binary relation \(\leq\) satisfying the following three properties:
- If \(x\in P\), then \(x\leq x\) in \(P\)(reflexive property)
- If \(x,y,z\in P\), \(x\leq y\) in \(P\) and \(y\leq x\) in \(P\), then \(x=y\)(antisymmetric)
- If \(x,y,z\in P\), \(x\leq y\) in \(P\) and \(y \leq z\) in \(P\), then \(x\leq z\) in \(P\) (transitive property)
The following graph is extremely useful.
\(\textbf{Ruzsá-Szemerédi Graph}\)(RS graph) Let \(U\) be an undirected graph. A matching \(M\) in \(U\) is called induced if the induced subgraph \(U[V(M)]\) contains only the edges of \(M\). A (bipartite) graph \(U = (X, Y; E)\) is called \((s,t)\)-Ruzsá-Szemerédi if its edge set can be partitioned into at least \(s\) induced matching \(M_1,\ldots, M_s\), each of which has size \(t\).
Lower Bounds
\(\textbf{Lemma}\). For infinitely many \(n\), there is an \((a,b)\)-RS graph \(U = (L, R;E)\) where \(a = n^{\Omega(\frac{1}{\log \log n})}, b = n/3 -o(1), \lvert L \rvert = \lvert R \rvert = n.\)
The above lemma shows the existence of the RS graph with large average degree. We will use such a RS graph to prove the lower bound.
\(\textbf{Theorem}\). Let \(U = (L, R; E)\) be an \((X, \epsilon n)\)-RS graph with \(\lvert L \rvert = \lvert R \rvert = n\). After directing all edges of \(U\) from \(L\) to \(R\), we obtain a DAG \(\vec{G}\). Then, any non-adaptive tester for monotonicity on \(G\) requires \(\Omega(\sqrt{X})\) queries.
To be continued.
Reference
[1]. Fischer, E., Lehman, E., Newman, I., Raskhodnikova, S., Rubinfeld, R. and Samorodnitsky, A., 2002, May. Monotonicity testing over general poset domains. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (pp. 474-483).