2010/01/03 by Nader H. Bshouty, Hanna Mazzawi, Bshouty, Nader H. +1 · 2 citations
Computer Science · #Complexity and Algorithms in Graphs #FOS: Computer and information sciences #Graph Theory and Algorithms #Machine Learning (cs.LG) #Machine Learning and Algorithms #cs.LG
paper · pdf · doi:10.48550/arxiv.1001.0405
arxiv created 2010/01/03 · openalex publication_date 2010/01/03 · arxiv updated 2010/01/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In 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((mlog 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(nd/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((mlog (nd)/(m))/(log m)). additive queries. Using the information theoretic bound the above query complexities are tight.