Sublinear Algorithms for Estimating the Number of Hyperedges in Arbitrary Hypergraphs

Deeparnab Chakrabarty, Cooper LaPorte, C. Seshadhri

We study the problem of estimating the number of hyperedges in an arbitrary $n$-vertex hypergraph using sublinear in $n$ queries. Note that the number of hyperedges, $m$, can be ex…