Oded Goldreich, Dana Ron

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