https://hal.inria.fr/inria-00455786Bshouty, Nader H.Nader H.BshoutyDepartment of Computer Science [Haifa] - University of Haifa [Haifa]Mazzawi, HannaHannaMazzawiDepartment of Computer Science [Haifa] - University of Haifa [Haifa]Optimal Query Complexity for Reconstructing HypergraphsHAL CCSD2010[INFO.INFO-LG] Computer Science [cs]/Machine Learning [cs.LG]Loria, PublicationsJean-Yves Marion and Thomas Schwentick2010-02-11 11:18:542010-02-22 10:50:252010-02-11 11:21:24enConference papersapplication/pdf1In this paper we consider the problem of reconstructing a hidden weighted hypergraph of constant rank using additive queries. We prove the following: Let $G$ be a weighted hidden hypergraph of constant rank with n vertices and $m$ hyperedges. For any $m$ there exists a non-adaptive algorithm that finds the edges of the graph and their weights using $$ O(\frac{m\log n}{\log m}) $$ additive queries. This solves the open problem in [S. Choi, J. H. Kim. Optimal Query Complexity Bounds for Finding Graphs. {\em STOC}, 749--758,~2008]. When the weights of the hypergraph are integers that are less than $O(poly(n^d/m))$ where $d$ is the rank of the hypergraph (and therefore for unweighted hypergraphs) there exists a non-adaptive algorithm that finds the edges of the graph and their weights using $$ O(\frac{m\log \frac{n^d}{m}}{\log m}). $$ additive queries. Using the information theoretic bound the above query complexities are tight.