Search Results

Documents authored by Mazzawi, Hanna


Document
Optimal Query Complexity for Reconstructing Hypergraphs

Authors: Nader H. Bshouty and Hanna Mazzawi

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)


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\left(\frac{m\log n}{\log m}\right) $$ 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\left(\frac{m\log \frac{n^d}{m}}{\log m}\right). $$ additive queries. Using the information theoretic bound the above query complexities are tight.

Cite as

Nader H. Bshouty and Hanna Mazzawi. Optimal Query Complexity for Reconstructing Hypergraphs. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 143-154, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{bshouty_et_al:LIPIcs.STACS.2010.2496,
  author =	{Bshouty, Nader H. and Mazzawi, Hanna},
  title =	{{Optimal Query Complexity for Reconstructing Hypergraphs}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{143--154},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2496},
  URN =		{urn:nbn:de:0030-drops-24968},
  doi =		{10.4230/LIPIcs.STACS.2010.2496},
  annote =	{Keywords: Query complexity, hypergraphs}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail