For a boolean formula \phi on n variables, the associated property
P_\phi is the collection of n-bit strings that satisfy \phi. We prove
that there are 3CNF properties that require a linear number of queries,
even for adaptive tests. This contrasts with 2CNF properties
that are testable with O(\sqrt{n}) ... more >>>

A basic goal in Property Testing is to identify a
minimal set of features that make a property testable.
For the case when the property to be tested is membership
in a binary linear error-correcting code, Alon et al.~\cite{AKKLR}
had conjectured that the presence of a {\em single} low weight
more >>>

The well-known DeMillo-Lipton-Schwartz-Zippel lemma says that $n$-variate
polynomials of total degree at most $d$ over
grids, i.e. sets of the form $A_1 \times A_2 \times \cdots \times A_n$, form
error-correcting codes (of distance at least $2^{-d}$ provided $\min_i\{|A_i|\}\geq 2$).
In this work we explore their local
decodability and local testability. ... more >>>

We study testing of local properties in one-dimensional and multi-dimensional arrays. A property of $d$-dimensional arrays $f:[n]^d \to \Sigma$ is $k$-local if it can be defined by a family of $k \times \ldots \times k$ forbidden consecutive patterns. This definition captures numerous interesting properties. For example, monotonicity, Lipschitz continuity and ... more >>>

The classical Reed-Muller codes over a finite field $\mathbb{F}_q$ are based on evaluations of $m$-variate polynomials of degree at most $d$ over a product set $U^m$, for some $d$ less than $|U|$. Because of their good distance properties, as well as the ubiquity and expressive power of polynomials, these codes ... more >>>