Property Testing of Massively Parametrized problems -- A survey <s> Open Problems <s> The field of property testing studies algorithms that distinguish, using a small number of queries, between inputs which satisfy a given property, and those that are `far' from satisfying the property. Testing properties that are defined in terms of monotonicity has been extensively investigated, primarily in the context of the monotonicity of a sequence of integers, or the monotonicity of a function over the n-dimensional hypercube {1,l,m}n. These works resulted in monotonicity testers whose query complexity is at most polylogarithmic in the size of the domain.We show that in its most general setting, testing that Boolean functions are close to monotone is equivalent, with respect to the number of required queries, to several other testing problems in logic and graph theory. These problems include: testing that a Boolean assignment of variables is close to an assignment that satisfies a specific 2-CNF formula, testing that a set of vertices is close to one that is a vertex cover of a specific graph, and testing that a set of vertices is close to a clique.We then investigate the query complexity of monotonicity testing of both Boolean and integer functions over general partial orders. We give algorithms and lower bounds for the general problem, as well as for some interesting special cases. In proving a general lower bound, we construct graphs with combinatorial properties that may be of independent interest. <s> BIB001 </s> Property Testing of Massively Parametrized problems -- A survey <s> Open Problems <s> Combinatorial property testing, initiated formally by Goldreich, Goldwasser, and Ron in [J. ACM, 45 (1998), pp. 653--750] and inspired by Rubinfeld and Sudan [SIAM J. Comput., 25 (1996), pp. 252--271], deals with the following relaxation of decision problems: Given a fixed property and an input x, one wants to decide whether x has the property or is "far" from having the property. ::: The main result here is that, if ${\cal G}= \{ g_n:\{0,1\}^n \rightarrow \{0,1\} \}$ is a family of Boolean functions which have oblivious read-once branching programs of width w, then, for every n and $\epsilon > 0$, there is a randomized algorithm that always accepts every $x \in \{0,1\}^n$ if $g_n(x)=1$ and rejects it with high probability if at least $\epsilon n$ bits of $x$ should be modified in order for it to be in gn-1(1). The algorithm makes $(\frac{2^{w}}{\epsilon})^{O(w)}$ queries. In particular, for constant $\epsilon$ and w, the query complexity is O(1). ::: This generalizes the results of Alon et al.\ [Proceedings of the40th IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, 1999, pp. 645--655] asserting that regular languages are $\epsilon$-testable for every $\epsilon > 0$. <s> BIB002
There are many open problems that arise in view of the results above. I will mention here but some. 1. There are nearly no testability results for any interesting subgraph-property of a given undirected underlying graph. There are no interesting results at all on the induced analog (namely, where the subgraph is defined by vertex labeling). 2. Testing monotonicity is not a main theme here. However, testing monotonicity in general posets does fall into this context. In view of the large gap between the upper and lower bounds in BIB001 this gives rise to a interesting open problem. One should mention that even for the Boolean cube, the complexity of testing monotonicity of Boolean functions (2-sided error) is far from being understood. 3. In BIB002 the dependence in the width is doubly exponential. There is no matching lower bound for this dependence (see also [19] for further related details). As this result is what partially determines the dependence in in the result for testing s − t-connectivity (Section 4.2), this further motivates resolving the question of the exact dependence in of both testing problems. 4. A general result on testing strong connectivity for G-orientations, or a non-testability result are still missing. It still might be the case that for every underlying graph this problem is testable. On the other hand, we don't have any non-trivial upper bound even of the form n α for α < 1. Similarly the variants of s − t strong connectivity and s-connectivity (namely, that s can reach every other vertex) are open.