On multistage learning a hidden hypergraph

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

Результат исследований: Глава в книге, отчете, сборнике статейМатериалы для конференциирецензирование

1 Цитирования (Scopus)

Аннотация

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.

Язык оригиналаАнглийский
Название основной публикацииProceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory
ИздательInstitute of Electrical and Electronics Engineers Inc.
Страницы1178-1182
Число страниц5
ISBN (электронное издание)9781509018062
DOI
СостояниеОпубликовано - 10 авг. 2016
Опубликовано для внешнего пользованияДа
Событие2016 IEEE International Symposium on Information Theory, ISIT 2016 - Barcelona, Испания
Продолжительность: 10 июл. 201615 июл. 2016

Серия публикаций

НазваниеIEEE International Symposium on Information Theory - Proceedings
Том2016-August
ISSN (печатное издание)2157-8095

Конференция

Конференция2016 IEEE International Symposium on Information Theory, ISIT 2016
Страна/TерриторияИспания
ГородBarcelona
Период10/07/1615/07/16

Fingerprint

Подробные сведения о темах исследования «On multistage learning a hidden hypergraph». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать