Power of Conditional Sampling on Hypergraphs
This work investigates using conditional sampling oracles to estimate hyperedge counts in d-uniform hypergraphs. It introduces a hierarchy of 's-colorful' random certificate oracles, which provide a significant power boost over standard uniform sampling. The results show that these certificates allow for much faster estimation with fewer queries than traditional methods.