A Fast Hierarchical Splitting Approach for Non-Adaptive Learning of Random Hypergraphs

2026/05/11 by Huy Pham, Hoang Ta
Computer Science · Mathematics · #cs.IT #math.IT

paper · pdf

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 θ∈ (0;1). Prior work [Austhof-Reyzin-Tani, ISIT 2025] presents a testing-decoding scheme that uses O(mlog n) tests but requires a decoding time of Ω(n³), where m = q\binomn3 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(m log n) tests and achieves decoding time O(m^5/3log n) for the case θ> \dfrac23 and O(m^5/3log²mlog n) for the case θ≤ \dfrac23. In particular, the decoding runtime is subcubic in n whenever θ<(3)/(5), providing a new test-decoding tradeoff compared with existing schemes.

Related

• Non-adaptive Learning of Random Hypergraphs with Queries
• A Fast Binary Splitting Approach for Non-Adaptive Learning of Erdős--Rényi Graphs
• Learning Erdős-Rényi Random Graphs via Edge Detecting Queries
• Non-Adaptive Learning a Hidden Hipergraph
• Learning Low Degree Hypergraphs