common.title

Docs
Quantum Circuit
TYTAN CLOUD

QUANTUM GAMING


Overview
Contact
Event
Project
Research

Terms of service (Web service)

Terms of service (Quantum and ML Cloud service)

Privacy policy


Sign in
Sign up
common.title

Tight Query Complexity Bounds for Learning Graph Partitions, December 2021

blueqat research

2021/12/18 02:01

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.

COLT2022

arXiv

© 2025, blueqat Inc. All rights reserved