Detecting and counting the number of copies of certain subgraphs (also known as {\em network motifs\/} or {\em graphlets\/}), is motivated by applications in a variety of areas ranging from Biology to the study of the World-Wide-Web. Several polynomial-time algorithms have been suggested for counting or detecting the number of ... 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 >>>

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 >>>

We raise the question of approximating compressibility of a string with respect to a fixed compression scheme, in sublinear time. We study this question in detail for two popular lossless compression schemes: run-length encoding (RLE) and Lempel-Ziv (LZ), and present algorithms and lower bounds for approximating compressibility with respect to ... more >>>

We consider the problem of estimating the size, $VC(G)$, of a minimum vertex cover of a graph $G$, in sublinear time, by querying the incidence relation of the graph. We say that an algorithm is an $(\alpha,\eps)$-approximation algorithm if it outputs with high probability an estimate $\widehat{VC}$ such that $VC(G) ... more >>>

Inspired by Feige ({\em 36th STOC}, 2004), we initiate a study of sublinear randomized algorithms for approximating average parameters of a graph. Specifically, we consider the average degree of a graph and the average distance between pairs of vertices in a graph. Since our focus is on sublinear algorithms, these ... more >>>

Following Feige, we consider the problem of estimating the average degree of a graph. Using ``neighbor queries'' as well as ``degree queries'', we show that the average degree can be approximated arbitrarily well in sublinear time, unless the graph is extremely sparse (e.g., unless the graph has a sublinear number ... 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 >>>

Traditionally, communication networks are composed of routing nodes, which relay and duplicate data. Work in recent years has shown that for the case of multicast, an improvement in both rate and code-construction complexity can be gained by replacing these routing nodes by linear coding nodes. These nodes transmit linear combinations ... 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 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 >>>

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 >>>

The Chinese Remainder Theorem states that a positive integer m is uniquely specified by its remainder modulo k relatively prime integers p_1,...,p_k, provided m < \prod_{i=1}^k p_i. Thus the residues of m modulo relatively prime integers p_1 < p_2 < ... < p_n form a redundant representation of m if ... more >>>

In a variety of PAC learning models, a tradeoff between time and information seems to exist: with unlimited time, a small amount of information suffices, but with time restrictions, more information sometimes seems to be required. In addition, it has long been known that there are concept classes that can ... more >>>

In this paper, we consider the question of determining whether a function $f$ has property $P$ or is $\e$-far from any function with property $P$. The property testing algorithm is given a sample of the value of $f$ on instances drawn according to some distribution. In some cases, it is ... more >>>