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 PGsuch that P is testable using q queries if and only if PGis 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.

We consider the problem of distribution-free property-testing of functions. In this setting of property-testing, the distance between functions is measured with respect to a fixed but unknown distribution D on the domain. The testing algorithms are given oracle access to random sampling from the domain according to this distribution D. This notion of distribution-free testing was previously defined, but no distribution-free property-testing algorithm was known for any (non-trivial) property. We present the first such distribution-free property-testing algorithms for two of the central problems in this field. The testers are obtained by extending some known results (from “standard,” uniform distribution, property-testing): (1) A distribution-free testing algorithm for low-degree multivariate polynomials with query complexity $O(d^2 + d \cdot \epsilon^{-1})$, where d is the total degree of the polynomial. The same approach that is taken for the distribution-free testing of low-degree polynomials is shown to apply also to several other problems; (2) a distribution-free monotonicity testing algorithm for functions $f:[n]^d \rightarrow A$ for low dimensions (e.g., when d is a constant) with query complexity similar to the one achieved in the uniform setting. On the negative side, we prove an exponential gap between the query complexity required for uniform and distribution-free monotonicity testing in the high-dimensional case.

We derive lower bounds on the capacity of certain two-dimensional (2-D) constraints by considering bounds on the entropy of measures induced by bit-stuffing encoders. A more detailed analysis of a previously proposed bit-stuffing encoder for (d,/spl infin/)-runlength-limited (RLL) constraints on the square lattice yields improved lower bounds on the capacity for all d /spl ges/ 2. This encoding approach is extended to (d,/spl infin/)-RLL constraints on the hexagonal lattice, and a similar analysis yields lower bounds on the capacity for d /spl ges/ 2. For the hexagonal (1,/spl infin/)-RLL constraint, the exact coding ratio of the bit-stuffing encoder is calculated and is shown to be within 0.5% of the (known) capacity. Finally, a lower bound is presented on the coding ratio of a bit-stuffing encoder for the constraint on the square lattice where each bit is equal to at least one of its four closest neighbors, thereby providing a lower bound on the capacity of this constraint.

A parallel constrained coding scheme is considered where p-blocks of raw data are encoded simultaneously into q tracks such that the contents of each track belong to a given constraint S. It is shown that as q increases, there are parallel block-decodable encoders for S whose coding ratio p/q converges to the capacity of S. Examples are provided where parallel coding allows block-decodable encoders, while conventional coding, at the same rate, does not. Parallel encoders are then applied as building blocks in the construction of block-decodable encoders for certain families of two-dimensional constraints.