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.
Type de document :
Communication dans un congrès
Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.143-154, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

Littérature citée [23 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00455786
Contributeur : Publications Loria <>
Soumis le : jeudi 11 février 2010 - 11:18:54
Dernière modification le : lundi 22 février 2010 - 10:50:25
Document(s) archivé(s) le : vendredi 18 juin 2010 - 20:12:34

Fichier

bshouty.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00455786, version 1

Collections

Citation

Nader H. Bshouty, Hanna Mazzawi. Optimal Query Complexity for Reconstructing Hypergraphs. Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.143-154, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00455786〉

Partager

Métriques

Consultations de la notice

157

Téléchargements de fichiers

43