TY - GEN

T1 - On multistage learning a hidden hypergraph

AU - D'Yachkov, A. G.

AU - Vorobyev, I. V.

AU - Polyanskii, N. A.

AU - Shchukin, V. Yu

PY - 2016/8/10

Y1 - 2016/8/10

N2 - 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.

AB - 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.

KW - asymptotic rate

KW - capacity

KW - cover-free code

KW - Group testing problem

KW - learning hidden hypergraph

UR - http://www.scopus.com/inward/record.url?scp=84985930994&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2016.7541485

DO - 10.1109/ISIT.2016.7541485

M3 - Conference contribution

AN - SCOPUS:84985930994

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 1178

EP - 1182

BT - Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2016 IEEE International Symposium on Information Theory, ISIT 2016

Y2 - 10 July 2016 through 15 July 2016

ER -