Hyperedge Estimation using Polylogarithmic Subset Queries

Understand

In this work, we estimate the number of hyperedges in a hypergraph ${\cal H}(U({\cal H}), {\cal F}({\cal H}))$, where $U({\cal H})$ denotes the set of vertices and ${\cal F}({\cal H}))$ denotes the set of hyperedges.

• We assume a query oracle access to the hypergraph ${\cal H}$.
• Estimating the number of edges, triangles or small subgraphs in a graph is a well studied problem.
• Beame \etal~and Bhattacharya \etal~gave algorithms to estimate the number of edges and triangles in a graph using queries to the {\sc Bipartite Independent Set} ({\sc BIS}) and the {\sc Tripartite Independent Set} ({\sc TIS}) oracles, respectively.