Property Testing of Massively Parametrized problems -- A survey <s> Definition 3 Let <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> Definition 3 Let <s> For a Boolean formula $\phi$ on n variables, the associated property $P_\phi$ is the collection of n-bit strings that satisfy $\phi$. We study the query complexity of tests that distinguish (with high probability) between strings in $P_\phi$ and strings that are far from $P_\phi$ in Hamming distance. We prove that there are 3CNF formulae (with O(n) clauses) such that testing for the associated property requires $\Omega(n)$ queries, even with adaptive tests. This contrasts with 2CNF formulae, whose associated properties are always testable with $O(\sqrt{n})$ queries [E. Fischer et al., Monotonicity testing over general poset domains, in Proceedings of the 34th Annual ACM Symposium on Theory of Computing, ACM, New York, 2002, pp. 474--483]. Notice that for every negative instance (i.e., an assignment that does not satisfy $\phi$) there are three bit queries that witness this fact. Nevertheless, finding such a short witness requires reading a constant fraction of the input, even when the input is very far from satisfying the formula that is associated with the property. ::: A property is linear if its elements form a linear space. We provide sufficient conditions for linear properties to be hard to test, and in the course of the proof include the following observations which are of independent interest: ::: In the context of testing for linear properties, adaptive two-sided error tests have no more power than nonadaptive one-sided error tests. Moreover, without loss of generality, any test for a linear property is a linear test. A linear test verifies that a portion of the input satisfies a set of linear constraints, which define the property, and rejects if and only if it finds a falsified constraint. A linear test is by definition nonadaptive and, when applied to linear properties, has a one-sided error. ::: Random low density parity check codes (which are known to have linear distance and constant rate) are not locally testable. In fact, testing such a code of length n requires $\Omega(n)$ queries. <s> BIB002 </s> Property Testing of Massively Parametrized problems -- A survey <s> Definition 3 Let <s> We study a model of graph related formulae that we call the constraint-graph model. A constraint-graph is a labeled multi-graph (a graph where loops and parallel edges are allowed), where each edge e is labeled by a distinct Boolean variable and every vertex is associated with a Boolean function over the variables that label its adjacent edges. A Boolean assignment to the variables satisfies the constraint graph if it satisfies every vertex function. We associate with a constraint-graph G the property that consists of all assignments satisfying G, denoted SAT(G). We show that the above model is quite general. That is, for every property of strings P there exists a property of constraint-graphs PG such that P is testable using q queries if and only if PG is thus testable. In addition, we present a large family of constraint-graphs for which SAT(G) is testable with constant number of queries. As an implication of this, we infer the testability of some edge coloring problems (e.g. the property of two coloring of the edges in which every node is adjacent to at least one vertex of each color). Another implication is that every property of Boolean strings that can be represented by a read-twice CNF formula is testable. We note that this is the best possible in terms of the number of occurrences of every variable in a formula. <s> BIB003
Theorem 11 BIB003 For every constraint-graph G ∈ LD 3 there exists a 1-sided error, non-adaptive The test is too complicated to be described here. We further mention that it is a generalization of a test for the property of G-orientations of not containing a source. The preprocessing involved in constructing the test, given G, is in polynomial time. We also note that this property, as well as the property of edge bi-coloring in which each vertex sees edges of both colors are in the family LD 3 (while the property of being Eulerian is not). An interesting application of Theorem 11 is to better understand the testability 'boundary' of the membership problem for restricted CNF formulae. Obviously general CNF formulae are hard to test. In BIB002 the authors show that there exists family of 3-CNF formulae that are highly non-testable (every test requires linear number of queries). Hence some restriction on the formulae has to be put in order to allow testability. A Read-k-times formula is a formula in which every variable appears at most k times. By standard arguments the result of BIB002 can also be extended to read-three times formulae (and any constant k ≥ 3 size clauses). What about 2CNF ? It turns out that this does not yet allow testability either. A corollary from the lower bound of BIB001 for testing monotonicity over general posets is that even monotone 2CNF are hard to test (although the lower bound is far from being linear). This is so as in BIB001 a two leveled poset is constructed for which monotonicity is hard to test. Thus this hard to test property can be expressed as 2CNF. Moreover, by renaming the variables it is, in fact, a monotone 2CNF  . Theorem 11 implies that restricting the CNF to be Read-2-times (a.k.a 'read-twice') already guarantee testability, disregarding the clause size. In view of the discussion above, this seems best possible in this respect. Proof. A read-twice formula can obviously be represented by a constraint graph. Further, as per the definition of LD 3 , clauses of size smaller than 3 pose no restrictions. Since every clause as only one 0-assignment, every two non identical 0-assignments that falsify a clause of size 3 or more differ on at least 3 variables. Thus Theorem 11 applies, and implies the claim. One may wonder whether LD 3 is coincidental, namely are LD 2 formulae testable. Indeed [10] (see more details in BIB003 ) noted that this is not the case: For every Boolean formula θ there is a formulae φ ∈ LD 2 so that for any q, there is an -test for θ-membership with q queries if and only if there is an -test for φ-membership using q queries. To see this let θ be a Boolean formula over a set variables X = {x 1 , . . . , x n }. Let G be the constraint-graph on two vertices {v, t}, that has n + 1 parallel edges between v and t, one that is associated with the variable y and the rest n edges are labeled each with a distinct variable in Obviously the resulting graph G is in LD 2 . Given a test for one of the properties it is straightforward to build a test for the other property.