On multistage learning a hidden hypergraph

A. G. D'Yachkov, I. V. Vorobyev, N. A. Polyanskii, V. Yu Shchukin

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Citation (Scopus)

Abstract

Learning a hidden hypergraph is a natural generalization of the classical group testing problem that consists in detecting unknown hypergraph Hun = H(V, E) by carrying out edge-detecting tests. In the given paper we focus our attention only on a specific family (t, s, ℓ) of localized hypergraphs for which the total number of vertices |V| = t, the number of edges |E| ≤ s, s ≪ t, and the cardinality of any edge |e| ≤ ℓ, ℓ ≪ t. Our goal is to identify all edges of Hun ⋯ (t, s, ℓ) by using the minimal number of tests. We develop an adaptive algorithm that matches the information theory bound, i.e., the total number of tests of the algorithm in the worst case is at most sℓ log2 t(1+o(1)). We also discuss a probabilistic generalization of the problem.

Original languageEnglish
Title of host publicationProceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1178-1182
Number of pages5
ISBN (Electronic)9781509018062
DOIs
Publication statusPublished - 10 Aug 2016
Externally publishedYes
Event2016 IEEE International Symposium on Information Theory, ISIT 2016 - Barcelona, Spain
Duration: 10 Jul 201615 Jul 2016

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
Volume2016-August
ISSN (Print)2157-8095

Conference

Conference2016 IEEE International Symposium on Information Theory, ISIT 2016
Country/TerritorySpain
CityBarcelona
Period10/07/1615/07/16

Keywords

  • asymptotic rate
  • capacity
  • cover-free code
  • Group testing problem
  • learning hidden hypergraph

Fingerprint

Dive into the research topics of 'On multistage learning a hidden hypergraph'. Together they form a unique fingerprint.

Cite this