Approximately counting and sampling small witnesses using a colourful decision oracle

Understand

In this paper, we design efficient algorithms to approximately count the number of edges of a given $k$-hypergraph, and to sample an approximately uniform random edge.

• The hypergraph is not given explicitly, and can be accessed only through its colourful independence oracle: The colourful independence oracle returns yes or no depending on whether a given subset of the vertices contains an edge that is colourful with respect to a given vertex-colouring.
• Our results extend and/or strengthen recent results in the graph oracle literature due to Beame et al.
• (ITCS 2018), Dell and Lapinskas (STOC 2018), and Bhattacharya et al.