Testing monotonicity of Boolean functions over the hypergrid, $f:[n]^d \to \{0,1\}$, is a classic problem in property testing. When the range is real-valued, there are $\Theta(d\log n)$-query testers and this is tight. In contrast, the Boolean range qualitatively differs in two ways:
(1) Independence of $n$: There are testers ... more >>>

Let $f:\{0,1\}^{n}\to\{0,1\}^{m}$ be a function computable by a circuit with
unbounded fan-in, arbitrary gates, $w$ wires and depth $d$. With
a very simple argument we show that the $m$-query problem corresponding
to $f$ has data structures with space $s=n+r$ and time $(w/r)^{d}$,
for any $r$. As a consequence, in the ... more >>>

In this work we study the testability of a family of graph partition properties that generalizes a family previously studied by Goldreich, Goldwasser, and Ron (Journal of the ACM, 1998). While the family studied by Goldreich et al. includes a variety of natural properties, such as k-colorability and containing a ... more >>>