Nearly optimal independence oracle algorithms for edge estimation in hypergraphs

Holger Dell, John Lapinskas, Kitty Meeks

We study a query model of computation in which an n-vertex k-hypergraph can be accessed only via its independence oracle or via its colourful independence oracle, and each oracle q…