标题： 自适应学习隐藏超图 显示英文标题

标题： Adaptive Learning a Hidden Hypergraph

摘要： 学习一个隐藏的超图是经典组测试问题的一个自然推广，其目的是通过进行边检测测试来检测未知的超图$H_{un}=H(V,E)$。 在本文中，我们仅关注一类特定的局部超图$\mathcal{F}(t,s,\ell)$，对于这类超图，顶点总数$|V| = t$、边数$|E|\le s$、$s\ll t$以及任何边的基数$|e|\le\ell$、$\ell\ll t$。 我们的目标是通过使用最少的测试次数来确定$H_{un}\in \mathcal{F}(t,s,\ell)$的所有边。我们提供了一个适应性算法，该算法匹配信息论界限，即算法在最坏情况下的总测试次数最多为$s\ell\log_2 t(1+o(1))$。 显示英文摘要

摘要： Learning a hidden hypergraph is a natural generalization of the classical group testing problem that consists in detecting unknown hypergraph $H_{un}=H(V,E)$ by carrying out edge-detecting tests. In the given paper we focus our attention only on a specific family $\mathcal{F}(t,s,\ell)$ of localized hypergraphs for which the total number of vertices $|V| = t$, the number of edges $|E|\le s$, $s\ll t$, and the cardinality of any edge $|e|\le\ell$, $\ell\ll t$. Our goal is to identify all edges of $H_{un}\in \mathcal{F}(t,s,\ell)$ by using the minimal number of tests. We provide 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\ell\log_2 t(1+o(1))$.