Property Testing of Massively Parametrized problems -- A survey <s> Constraint graph formulae <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> BIB001 </s> Property Testing of Massively Parametrized problems -- A survey <s> Constraint graph formulae <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> BIB002
We start with a model for formulae that is quite related to the orientation model discussed in Section 4.1, and that was formulated in BIB002 . A constraint-graph is a labeled multi-graph (a graph where loops and parallel edges are allowed), where each edge is labeled by a distinct Boolean variable, and every vertex is associate 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 BIB001 . We associate with a constraint-graph G the property of all assignments satisfying G, denoted SAT (G). Thus, e.g., the property of subgraphs (or of G-orientations) of being Eulerian can be expressed in an obvious way. Similarly, the property of G-orientations of not having a source vertex can be expressed, as well as the property of edge bi-coloring so that each vertex sees both colors. Obviously, formulae represented by constraint graphs are general enough to represent any Boolean formula (as one can take a two vertex graph, with many parallel edges between the two vertices, and any complex formula on one of the vertices). Hence, the interesting case is when further restrictions are put on the complexity of the vertex formulae. The main result of BIB002 is a test for the following class of Boolean formulae. For a vertex v ∈ V (G) let E v = {(v, w) ∈ E(G)}, namely all edges adjacent to v. For an assignment σ ∈ {0, 1} E and F ⊆ E we denote by σ(F ) the restriction of the assignment σ on F .