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

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

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 show that in the bounded degree model for graph property testing, adaptivity is essential. An algorithm is *non-adaptive* if it makes all queries to the input before receiving any answers. We call a property *non-trivial* if it does not depend only on the degree distribution of the nodes. We ... more >>>