# Optimal Query Complexity for Reconstructing Hypergraphs

Abstract : 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.
Document type :
Conference papers

Cited literature [23 references]

https://hal.inria.fr/inria-00455786
Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Thursday, February 11, 2010 - 11:18:54 AM
Last modification on : Monday, February 22, 2010 - 10:50:25 AM
Long-term archiving on: : Friday, June 18, 2010 - 8:12:34 PM

### File

bshouty.pdf
Files produced by the author(s)

### Identifiers

• HAL Id : inria-00455786, version 1

### Citation

Nader H. Bshouty, Hanna Mazzawi. Optimal Query Complexity for Reconstructing Hypergraphs. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Inria Nancy Grand Est & Loria, Mar 2010, Nancy, France. pp.143-154. ⟨inria-00455786⟩

Record views
{"ft_lang_label":"__label__en","ft_lang_prob":0.6473476,"math_prob":0.8971101,"size":261,"snap":"2022-27-2022-33","text_gpt3_token_len":78,"char_repetition_ratio":0.031128405,"word_repetition_ratio":0.0,"special_character_ratio":0.2835249,"punctuation_ratio":0.23404256,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9861149,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-06-29T11:00:43Z\",\"WARC-Record-ID\":\"<urn:uuid:732cc77b-02c8-4dc9-87a6-f1bc00fa842b>\",\"Content-Length\":\"41231\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:e1140708-a6ca-4593-98f3-9215f8bf4bb5>\",\"WARC-Concurrent-To\":\"<urn:uuid:9df50266-4ce6-4cd5-bdff-c86ff6ff5bfe>\",\"WARC-IP-Address\":\"193.48.96.10\",\"WARC-Target-URI\":\"https://hal.inria.fr/inria-00455786\",\"WARC-Payload-Digest\":\"sha1:FLK7IEQYYCVBXO6PLHXOZP3VX2DJ2YSI\",\"WARC-Block-Digest\":\"sha1:NT5BI3XMBGGDKIHX42TNITBLRAQZQ3LF\",\"WARC-Identified-Payload-Type\":\"application/xhtml+xml\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-27/CC-MAIN-2022-27_segments_1656103626162.35_warc_CC-MAIN-20220629084939-20220629114939-00152.warc.gz\"}"}