A Fast Hierarchical Splitting Approach for Non-Adaptive Learning of Random Hypergraphs
2026-05-11 • Information Theory
Information Theory
AI summaryⓘ
The authors study how to identify all special 3-item groups (hyperedges) from a large set by making yes/no questions that detect if a group exists. They focus on random groups formed under a well-known model where each group appears with some probability depending on the size of the set. Building on earlier work, they create a new method that asks roughly the same number of questions but can figure out the answer much faster, especially when groups are not too sparse. This improvement lowers the time needed to decode which groups exist while keeping the number of questions nearly minimal.
3-uniform hypergraphedge-detecting queriesErdős–Rényi modelbinary splittingquery complexitydecoding complexityrandom hypergraphsgroup testingsparse recoverycombinatorial algorithms
Authors
Huy Pham, Hoang Ta
Abstract
This work focuses on the problem of learning an unknown $3$-uniform hypergraph using edge-detecting queries. Our goal is to design a querying strategy that recovers the hyperedge set using as few queries as possible. We restrict our attention to random hypergraphs under the Erdős--Rényi (ER) model, in which each potential hyperedge appears independently with probability $q = Θ(n^{-3(1-θ)})$ for $θ\in (0;1)$. Prior work [Austhof-Reyzin-Tani, ISIT 2025] presents a testing-decoding scheme that uses $O(\bar{m}\log n)$ tests but requires a decoding time of $Ω(n^3)$, where $\bar{m} = q\binom{n}{3}$ denotes the expected number of hyperedges. In this work, we extend the binary splitting framework and adapt it to the $3$-uniform hypergraph setting. We obtain a testing-decoding scheme that recovers the hyperedge set with high probability using $O(\bar{m} \log n)$ tests and achieves decoding time $O(\bar{m}^{5/3}\log n)$ for the case $θ> \dfrac{2}{3}$ and $O(\bar{m}^{5/3}\log^2{\bar{m}}\log n)$ for the case $θ\leq \dfrac{2}{3}$. Thus, compared with prior work, our result significantly improves the decoding complexity while maintaining optimal query complexity.