We present improved algorithms for testing monotonicity of functions.
Namely, given the ability to query an unknown function $f$, where
$\Sigma$ and $\Xi$ are finite ordered sets, the test always accepts a
monotone $f$, and rejects $f$ with high probability if it is $\e$-far
from being monotone (i.e., every monotone ... more >>>

We consider testing graph expansion in the bounded-degree graph model.
Specifically, we refer to algorithms for testing whether the graph
has a second eigenvalue bounded above by a given threshold
or is far from any graph with such (or related) property.

We present a natural algorithm aimed towards ... more >>>

Let $P$ be a property of graphs. An $\epsilon$-test for $P$ is a
randomized algorithm which, given the ability to make queries whether
a desired pair of vertices of an input graph $G$ with $n$ vertices are
adjacent or not, distinguishes, with high probability, between the
case of $G$ satisfying ... more >>>

An $\epsilon$-test for a property $P$ of functions from
${\cal D}=\{1,\ldots,d\}$ to the positive integers is a randomized
algorithm, which makes queries on the value of an input function at
specified locations, and distinguishes with high probability between the
case of the function satisfying $P$, and the case that it ... more >>>

Property testing is a relaxation of decision problems
in which it is required to distinguish {\sc yes}-instances
(i.e., objects having a predetermined property) from instances
that are far from any {\sc yes}-instance.
We presents three theorems regarding testing graph
properties in the adjacency matrix representation.
more >>>

In model checking, program correctness on all inputs is verified
by considering the transition system underlying a given program.
In practice, the system can be intractably large.
In property testing, a property of a single input is verified
by looking at a small subset of that input.
We ... more >>>

We consider the problem of determining whether a given
function f : {0,1}^n -> {0,1} belongs to a certain class
of Boolean functions F or whether it is far from the class.
More precisely, given query access to the function f and given
a distance parameter epsilon, we would ... more >>>

We consider the problem of testing bipartiteness in the adjacency
matrix model. The best known algorithm, due to Alon and Krivelevich,
distinguishes between bipartite graphs and graphs that are
$\epsilon$-far from bipartite using $O((1/\epsilon^2)polylog(1/epsilon)$
queries. We show that this is optimal for non-adaptive algorithms,
up to the ... more >>>

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 $k$-uniform hypergraph $G$ of size $n$ is said to be $\varepsilon$-far from having an independent set of size $\rho n$ if one must remove at least $\varepsilon n^k$ edges of $G$ in order for the remaining hypergraph to have an independent set of size $\rho n$. In this work, ... more >>>

A standard property testing algorithm is required to determine
with high probability whether a given object has property
P or whether it is \epsilon-far from having P, for any given
distance parameter \epsilon. An object is said to be \epsilon-far
from having property P if ... more >>>

In this paper, we study two questions related to
the problem of testing whether a function is close to a homomorphism.
For two finite groups $G,H$ (not necessarily Abelian),
an arbitrary map $f:G \rightarrow H$, and a parameter $0 < \epsilon <1$,
say that $f$ is $\epsilon$-close to a homomorphism ... more >>>

In general property testing, we are given oracle access to a function $f$, and we wish to randomly test if the function satisfies a given property $P$, or it is $\epsilon$-far from having that property. In a more general setting, the domain on which the function is defined is equipped ... more >>>

Using a new statistical embedding of words which has similarities with the Parikh mapping, we first construct a tolerant tester for the equality of two words, whose complexity is independent of the string size, where the distance between inputs is measured by the normalized edit distance with moves. As a ... more >>>

We survey known results regarding locally testable codes
and locally testable proofs (known as PCPs),
with emphasis on the length of these constructs.
Locally testability refers to approximately testing
large objects based on a very small number of probes,
each retrieving a single bit in the representation ... more >>>

The notion of promise problems was introduced and initially studied
by Even, Selman and Yacobi
(Information and Control, Vol.~61, pages 159-173, 1984).
In this article we survey some of the applications that this
notion has found in the twenty years that elapsed.
These include the notion of ... more >>>

An error-correcting code is said to be {\em locally testable} if it has an
efficient spot-checking procedure that can distinguish codewords
from strings that are far from every codeword, looking at very few
locations of the input in doing so. Locally testable codes (LTCs) have
generated ... more >>>

Property-testers are fast randomized algorithms for distinguishing
between graphs (and other combinatorial structures) satisfying a
certain property, from those that are far from satisfying it. In
many cases one can design property-testers whose running time is in
fact {\em independent} of the size of the input. In this paper we
more >>>

A coloring of a graph is {\it convex} if it
induces a partition of the vertices into connected subgraphs.
Besides being an interesting property from a theoretical point of
view, tests for convexity have applications in various areas
involving large graphs. Our results concern the important subcase
of testing for ... more >>>

We initiate a general study of the randomness complexity of
property testing, aimed at reducing the randomness complexity of
testers without (significantly) increasing their query complexity.
One concrete motovation for this study is provided by the
observation that the product of the randomness and query complexity
of a tester determine ... more >>>

Motivated by a recent study of Zimand (22nd CCC, 2007),
we consider the average-case complexity of property testing
(focusing, for clarity, on testing properties of Boolean strings).
We make two observations:

1) In the context of average-case analysis with respect to
the uniform distribution (on all strings of ... more >>>

We show that random sparse binary linear codes are locally testable and locally decodable (under any linear encoding) with constant queries (with probability tending to one). By sparse, we mean that the code should have only polynomially many codewords. Our results are the first to show that local decodability and ... more >>>

We consider the problem of testing graph expansion in the bounded degree model. We give a property tester that given a graph with degree bound $d$, an expansion bound $\alpha$, and a parameter $\epsilon > 0$, accepts the graph with high probability if its expansion is more than $\alpha$, and ... more >>>

We describe a general method for testing whether a function on n input variables has a concise representation. The approach combines ideas from the junta test of Fischer et al. with ideas from learning theory, and yields property testers that make poly(s/epsilon) queries (independent of n) for Boolean function classes ... more >>>

This paper addresses the problem of testing whether a Boolean-valued function f is a halfspace, i.e. a function of the form f(x)=sgn(w &#8901; x - &#952;). We consider halfspaces over the continuous domain R^n (endowed with the standard multivariate Gaussian distribution) as well as halfspaces over the Boolean cube {-1,1}^n ... more >>>

We introduce the notion of a Canonical Tester for a class of properties, that is, a tester strong and
general enough that ``a property is testable if and only if the
Canonical Tester tests it''. We construct a Canonical Tester
for the class of symmetric properties of one or two
more >>>

Given a boolean function, let epsilon_M(f) denote the smallest distance between f and a monotone function on {0,1}^n. Let delta_M(f) denote the fraction of hypercube edges where f violates monotonicity. We give an alternative proof of the tight bound: delta_M(f) >= 2/n eps_M(f) for any boolean function f. This was ... 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 >>>

In this paper we consider two refined questions regarding
the query complexity of testing graph properties
in the adjacency matrix model.
The first question refers to the relation between adaptive
and non-adaptive testers, whereas the second question refers to
testability within complexity that
is inversely proportional to ... more >>>

For a permutation group $G$ acting on the set $\Omega$
we say that two strings $x,y\,:\,\Omega\to\boole$
are {\em $G$-isomorphic} if they are equivalent under
the action of $G$, \ie, if for some $\pi\in G$ we have
$x(i^{\pi})=y(i)$ for all $i\in\Omega$.
Cyclic Shift, Graph Isomorphism and ... more >>>

We initiate a systematic study of a special type of property testers.
These testers consist of repeating a basic test
for a number of times that depends on the proximity parameters,
whereas the basic test is oblivious of the proximity parameter.
We refer to such basic tests ... more >>>

We consider the task of testing properties of Boolean functions that
are invariant under linear transformations of the Boolean cube. Previous
work in property testing, including the linearity test and the test
for Reed-Muller codes, has mostly focused on such tasks for linear
properties. The one exception is a test ... more >>>

Referring to the query complexity of property testing,
we prove the existence of a rich hierarchy of corresponding
complexity classes. That is, for any relevant function $q$,
we prove the existence of properties that have testing
complexity Theta(q).
Such results are proven in three standard
domains often considered in property ... more >>>

A hypergraph dictatorship test is first introduced by Samorodnitsky
and Trevisan and serves as a key component in
their unique games based $\PCP$ construction. Such a test has oracle
access to a collection of functions and determines whether all the
functions are the same dictatorship, or all their low degree ... more >>>

We consider the problem of testing if a given function
$f : \F_2^n \rightarrow \F_2$ is close to any degree $d$ polynomial
in $n$ variables, also known as the Reed-Muller testing problem.
Alon et al.~\cite{AKKLR} proposed and analyzed a natural
$2^{d+1}$-query test for this property and showed that it accepts
more >>>

In this paper, we give surprisingly efficient algorithms for list-decoding and testing
{\em random} linear codes. Our main result is that random sparse linear codes are locally testable and locally list-decodable
in the {\em high-error} regime with only a {\em constant} number of queries.
More precisely, we show that for ... more >>>

Locally testable codes (LTCs) are error-correcting codes for which membership, in the code, of a given word can be tested by examining it in very few locations. Most known constructions of locally testable codes are linear codes, and give error-correcting codes
whose duals have (superlinearly) {\em many} small weight ... more >>>

We study the question of whether the value of mathematical programs such as
linear and semidefinite programming hierarchies on a graph $G$, is preserved
when taking a small random subgraph $G'$ of $G$. We show that the value of the
Goemans-Williamson (1995) semidefinite program (SDP) for \maxcut of $G'$ is
more >>>

Property testing considers the task of testing rapidly (in particular, with very few samples into the data), if some massive data satisfies some given property, or is far from satisfying the property. For ``global properties'', i.e., properties that really depend somewhat on every piece of the data, one could ask ... more >>>

The aim of this article is to introduce the reader to the study
of testing graph properties, while focusing on the main models
and issues involved. No attempt is made to provide a
comprehensive survey of this study, and specific results
are often mentioned merely as illustrations of general ... more >>>

In this paper we study the problem of testing structural equivalence (isomorphism) between a pair of Boolean
functions $f,g:\zo^n \to \zo$. Our main focus is on the most studied case, where one of the functions is given (explicitly), and the other function can be queried.

We prove that for every ... more >>>

The rich collection of successes in property testing raises a natural question: Why are so many different properties turning out to be locally testable? Are there some broad "features" of properties that make them testable? Kaufman and Sudan (STOC 2008) proposed the study of the relationship between the invariances satisfied ... more >>>

Properties of Boolean functions on the hypercube that are invariant
with respect to linear transformations of the domain are among some of
the most well-studied properties in the context of property testing.
In this paper, we study a particular natural class of linear-invariant
properties, called matroid freeness properties. These properties ... more >>>

Given two testable properties $\mathcal{P}_{1}$ and $\mathcal{P}_{2}$, under what conditions are the union, intersection or set-difference
of these two properties also testable?
We initiate a systematic study of these basic set-theoretic operations in the context of property
testing. As an application, we give a conceptually different proof that linearity is ... more >>>

We propose a framework for studying property testing of collections of distributions,
where the number of distributions in the collection is a parameter of the problem.
Previous work on property testing of distributions considered
single distributions or pairs of distributions. We suggest two models that differ
in the way the ... more >>>

We prove two new multivariate central limit theorems; the first relates the sum of independent distributions to the multivariate Gaussian of corresponding mean and covariance, under the earthmover distance matric (also known as the Wasserstein metric). We leverage this central limit theorem to prove a stronger but more specific central ... more >>>

We introduce a new approach to characterizing the unobserved portion of a distribution, which provides sublinear-sample additive estimators for a class of properties that includes entropy and distribution support size. Together with the lower bounds proven in the companion paper [29], this settles the longstanding question of the sample complexities ... more >>>

The last two decades have seen enormous progress in the development of sublinear-time algorithms --- i.e., algorithms that examine/reveal properties of ``data'' in less time than it would take to read all of the data. A large, and important, subclass of such properties turn out to be ``linear''. In particular, ... more >>>

Sublinear time algorithms represent a new paradigm
in computing, where an algorithm must give some sort
of an answer after inspecting only a very small portion
of the input. We discuss the types of answers that
one can hope to achieve in this setting.

Property testing is concerned with deciding whether an object
(e.g. a graph or a function) has a certain property or is ``far''
(for a prespecified distance measure) from every object with
that property. In this work we consider the property of being
computable by a read-once ... more >>>

A function $f : D \to R$ has Lipschitz constant $c$ if $d_R(f(x),f(y)) \leq c\cdot d_D(x,y)$ for all $x,y$ in $D$, where $d_R$ and $d_D$ denote the distance functions on the range and domain of $f$, respectively. We say a function is Lipschitz if it has Lipschitz constant 1. (Note ... more >>>

We consider the problem of testing if a given function $f : \F_q^n \rightarrow \F_q$ is close to a $n$-variate degree $d$ polynomial over the finite field $\F_q$ of $q$ elements. The natural, low-query, test for this property would be to pick the smallest dimension $t = t_{q,d}\approx d/q$ such ... more >>>

Call a function $f: \mathbb{F}_2^n \to \{0,1\}$ odd-cycle-free if there are no $x_1, \dots, x_k \in \mathbb{F}_2^n$ with $k$ an odd integer such that $f(x_1) = \cdots = f(x_k) = 1$ and $x_1 + \cdots + x_k = 0$. We show that one can distinguish odd-cycle-free functions from those $\epsilon$-far ... more >>>

Affine-invariant properties are an abstract class of properties that generalize some
central algebraic ones, such as linearity and low-degree-ness, that have been
studied extensively in the context of property testing. Affine invariant properties
consider functions mapping a big field $\mathbb{F}_{q^n}$ to the subfield $\mathbb{F}_q$ and include all
properties that form ... more >>>

In this paper, we study the problem of testing the conductance of a
given graph in the general graph model. Given distance parameter
$\varepsilon$ and any constant $\sigma>0$, there exists a tester
whose running time is $\mathcal{O}(\frac{m^{(1+\sigma)/2}\cdot\log
n\cdot\log\frac{1}{\varepsilon}}{\varepsilon\cdot\Phi^2})$, where
$n$ is the number of vertices and $m$ is the number ... more >>>

The problem of monotonicity testing of the boolean hypercube is a classic well-studied, yet unsolved
question in property testing. We are given query access to $f:\{0,1\}^n \mapsto R$
(for some ordered range $R$). The boolean hypercube ${\cal B}^n$ has a natural partial order, denoted by $\prec$ (defined by the product ... more >>>

Let $f:\{-1,1\}^n \to \mathbb{R}$ be a real function on the hypercube, given
by its discrete Fourier expansion, or, equivalently, represented as
a multilinear polynomial. We say that it is Boolean if its image is
in $\{-1,1\}$.

We show that every function on the hypercube with a sparse ... more >>>

Over a finite field $\F_q$ the $(n,d,q)$-Reed-Muller code is the code given by evaluations of $n$-variate polynomials of total degree at most $d$ on all points (of $\F_q^n$). The task of testing if a function $f:\F_q^n \to \F_q$ is close to a codeword of an $(n,d,q)$-Reed-Muller code has been of ... more >>>

We prove that the class of locally testable affine-invariant properties is closed under sums, intersections and "lifts". The sum and intersection are two natural operations on linear spaces of functions, where the sum of two properties is simply their sum as a vector space. The "lift" is a less natural ... more >>>