Computer Science – Learning
Scientific paper
2010-01-03
Computer Science
Learning
Scientific paper
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(\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.
Bshouty Nader H.
Mazzawi Hanna
No associations
LandOfFree
Optimal Query Complexity for Reconstructing Hypergraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Optimal Query Complexity for Reconstructing Hypergraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal Query Complexity for Reconstructing Hypergraphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-223034