Property Testing of Massively Parametrized problems -- A survey <s> Testing general Read-Once-formulae <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> BIB001 </s> Property Testing of Massively Parametrized problems -- A survey <s> Testing general Read-Once-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
Here we discuss testing membership in other restricted formulae that are not the results of BIB001 or BIB002 . Read-Once formulae are Boolean formulae with ∧ (AND) and ∨ (OR) gates in which every variable appears at most once. In addition, in what follows, we will assume that each variable appear unnegated, thus such formulae represent monotone Boolean functions.  Read-Once formulae have been studied extensively in the past, but surprisingly, not with respect to whether their corresponding membership problem is testable. We note that bounded depth read-once formulae are represented by constant width branching program, thus their testability follows from BIB001 . We present here a result of Fischer, Lachish and Nimbhorkar that is much stronger. Theorem 12 [14] For every read-once formula F, the membership problem for F is 1-sided error testable. We present a relatively detailed proof as the idea here is somewhat different from the standard ideas one meets in property testing. The analysis we bring here implies an -test that has query complexity (1/ ) O(1/ ) , and that the test can be constructed (that is, the preprocessing) in polynomial time. A variation of this idea and better analysis [14] implies a much better dependence on . Proof. (Sketch ), Along the sequel we identify the formula F with the Boolean function that it computes F : {0, 1} n → {0, 1}. We say that F is an ∨-formula if its top gate is ∨, similarly ∧-formulae are defined. A single variable is considered both a ∨-formula and an ∧-formula. We first note that the formula F may be assumed to be layered so that the entries to each ∨-gate are variables or come from ∧-gates, and the entries for ∧-gates are variable or come from ∨-gates. The test will be recursive w.r.t , that is, an -test for a ∨-formula will call a δ-test for a ∧-subformula, with δ significantly larger than , while the test for ∧-formula will call a test for ∨-formula with nearly the same . For this to end we first note that for any read-once ∨-formula F on at least two variables, any assignment is 1/2-close to For any assignment x to F , x is naturally being partitioned to x 1 , . . . x k , where x i , i = 1, . . . , k is an assignment to the variables in F i . We keep this notation and for each assignment x to F refer to x 1 , . . . , x k as the corresponding assignments for F 1 , . . . , F k . We next describe a ∧-test for ∧-formulae and ∨-test for ∨-formula. In the following n is the number of variables of F . Otherwise, independently for 9/ 2 times pick an i ∈ [k] with probability s i /n and δ-∨-test F i independently twice, with δ = (1 − /3). If for the chosen i, both tests answer 1, set T i = 1 and otherwise set T i = 0. If for any of the chosen i's T i = 0 stop and output 0 (that is reject x as not being in F −1 (1)), and otherwise (if for all i's T i = 1) accept x (as being -close to If k = 1 and F 1 is a single variable, deterministically test F 1 using one query. If for some i, s i < n, or if ≥ 1/2 stop and accept x (as being -close to F −1 (1)). Otherwise, for every i ∈ [k] set α i = · n/s i and perform = 1 + log 3 k independent times α i -∧-test for F i . For such i set T i = 1 if all the independent tests return 1 and 0 otherwise. If any of the T i , i = 1, . . . , k has returned 1 accept x (as being -close to F −1 (1)). Otherwise (if for every i, T i = 0 ) reject x as being -far from F −1 (1). To assert the correctness of the tests, assume inductively that both tests are 1-sided error and have error probability at most 1/3 on smaller formulae for any (the reader may check this for the base case of one gate formulae). It is easy to verify that both tests have 1-sided error assuming inductively that they do on subformulae. To assess the error probability of the ∧-test, assume that x is -far from a ∧-formula F . Then x i is i -far from being a member of F i with i · s i n = . From this it follows, by simple average-argument, that there are at most 1 − 2 /3-fraction of the variables that may appear in F i for which x i is (1 − /3) -close to F i . Thus an error will occur on x only if all 9/ 2 i's that are sampled resulted in F i for which x i is (1 − /3) -close to F i , or when an i for which x i is (1 − /3) -far from F i is sampled, and the ∨-test for F i errs twice. The former event happens with probability smaller than e −3 and the later with probability at most 1/9, resulting a total error bounded by 1/3. For the ∨-test, note that if x is -far from being a member of F , namely one needs to change at least n bits of x in order to become in F −1 (1), then in each x i one should change at least n bits to become a member of F −1 i (1). It follows that x i is at least α i -far from F i . Hence, an error on x occurs only if at least one of the T i 's is wrong, meaning that all tests were wrong for F i . By the union bound this will happen with probability at most k · 1/(3k) ≤ 1/3. We end by estimating the query complexity. Let t ∨ ( ), t ∧ ( ) denote the corresponding complexity of the ∨ and ∧ tests. Note first that for ≥ 1/2 t ∨ ( ) = 1. Also, this is the case if F is ∨-formula with k > 1/ , or s i < n. Thus we get t ∨ ( ) ≤ log(1/ ) · t ∧ ( /(1 − )). (Since s i ≥ (1 − )n for all i's, which implies that α i ≤ 1− ). Similarly, ∧-test takes 1-query for k = 1, and for general it takes t ∧ ( ) ≤ 6 2 ·t ∨ ( (1− )). Solving the recurrence implies the result.