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) - \eps n \leq \widehat{VC} \leq \alpha\cdot VC(G) + \eps n$,
where $n$ is the number of vertices of $G$.

We show that the query complexity of such algorithms must grow at
least linearly with the average degree $\bd$ of the graph. In particular
this means that for dense graphs it is not possible to design
an algorithm whose complexity is $o(n)$.

On the positive side we first describe a
simple $(O(\log(\bd/\eps),\eps)$-approximation algorithm,
whose query complexity is $\eps^{-2}\cdot (\bd/\eps)^{\log(\bd/\eps)+O(1)}$.

We then show a reduction from local distributed approximation algorithms
to sublinear approximation algorithms.
Using this reduction and the distributed algorithm of
Kuhn, Moscibroda, and Wattenhofer~\cite{KMW}
we can get an $(O(1),\eps)$-approximation algorithm,
whose query complexity is
$\eps^{-2}\cdot (\bd/\eps)^{O(\log(\bd/\eps)}$.

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) - \eps n \leq \widehat{VC} \leq \alpha\cdot VC(G) + \eps n$,
where $n$ is the number of vertices of $G$.

We show that the query complexity of such algorithms must grow at
least linearly with the average degree $\bd$ of the graph.
In particular this means that for dense graphs it is not possible
to design an algorithm whose complexity is $o(n)$.

On the positive side we first describe a
simple $(O(\log(\bd/\eps),\eps)$-approximation algorithm,
whose query complexity is
$\eps^{-2}\cdot (\bd/\eps)^{\log(\bd/\eps)+O(1)}$.

We then show a reduction from local distributed approximation
algorithms to sublinear approximation algorithms.
Using this reduction and the distributed algorithm of
Kuhn, Moscibroda, and Wattenhofer~\cite{KMW}
we can get an $(O(1),\eps)$-approximation algorithm,
whose query complexity is
$\eps^{-2}\cdot (\bd/\eps)^{O(\log(\bd/\eps)}$.