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 achieving the ... 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 specifically, these theorems relate ... 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 join the ... 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 like ... 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 polylogarithmic factor. We ... 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}) queries ... 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 at least an \epsilon-fraction of ... 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 of the object. ... 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 ``unique solutions'', the ... 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 a lot of interest ... 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 a fixed ... 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 ⋅ x - θ). 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 the proximity parameter, ... 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 Hypergraph Isomorphism are special cases, ... 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 by the term ... 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 codewords. ... 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 >>>