1 paper · 1 filter
Lukas Michel, Alex Scott
We investigate the number of maximal independent set queries required to reconstruct the edges of a hidden graph. We show that randomised adaptive algorithms need at least $Ω(Δ^2 \…