Sayan Mukherjee, December 2021 Given a partition of a graph into connected components, the membership oracle asserts whether any two vertices of the graph lie in the same component or not. We prove that for n≥k≥2, learning the components of an n-vertex hidden graph with k components requires at least 12(n−k)(k−1) membership queries. This proves the optimality of the O(nk) algorithm proposed by Reyzin and Srivastava (2007) for this problem, improving on the best known information-theoretic bound of Ω(nlogk) queries. Further, we construct an oracle that can learn the number of components of G in asymptotically fewer queries than learning the full partition, thus answering another question posed by the same authors. Lastly, we introduce a more applicable version of this oracle, and prove asymptotically tight bounds of Θ˜(m) queries for both learning and verifying an m-edge hidden graph G using this oracle. <a href="http://learningtheory.org/colt2022/accepted-papers.html" rel="noopener noreferrer" target="_blank" style="background-color: rgb(255, 255, 255); color: rgb(2, 79, 159);">COLT2022</a><a href="https://arxiv.org/abs/2112.07897" rel="noopener noreferrer" target="_blank" style="color: var(--corvid-color,rgb(var(--txt,var(--color_15)))); background-color: transparent;">arXiv</a>

Tight Query Complexity Bounds for Learning Graph Partitions, December 2021

blueqat research