# Learning Low Degree Hypergraphs

arXiv: https://arxiv.org/abs/2202.09989 · HTML: https://mlsanity.com/paper/2202.09989/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 21 references that are in the map.
- First posted on arXiv 21 Feb 2022.

## Builds on (most cited first, 2 of 2)

- [On Exact Learning Monotone DNF from Membership Queries](https://mlsanity.com/paper/1405.0792/) (2014)
- [Exact Learning from an Honest Teacher That Answers Membership Queries](https://mlsanity.com/paper/1706.03935/) (2017)

## Built on by (most cited first, 3 of 3)

- [Non-adaptive Learning of Random Hypergraphs with Queries](https://mlsanity.com/paper/2501.12771/) (2025)
- [Adaptive Sparse M"obius Transforms for Learning Polynomials](https://mlsanity.com/paper/2602.06246/) (2026)
- [Randomized Algorithms for Learning Partitions with Near Optimal Query Complexity in Constant Rounds](https://mlsanity.com/paper/2608.02176/) (2026)

## Abstract (arXiv)

We study the problem of learning a hypergraph via edge detecting queries. In this problem, a learner queries subsets of vertices of a hidden hypergraph and observes whether these subsets contain an edge or not. In general, learning a hypergraph with m edges of maximum size d requires Omega((2m/d)d/2) queries. In this paper, we aim to identify families of hypergraphs that can be learned without suffering from a query complexity that grows exponentially in the size of the edges. We show that hypermatchings and low-degree near-uniform hypergraphs with n vertices are learnable with poly(n) queries. For learning hypermatchings (hypergraphs of maximum degree  1), we give an O(log3 n)-round algorithm with O(n log5 n) queries. We complement this upper bound by showing that there are no algorithms with poly(n) queries that learn hypermatchings in o(log log n) adaptive rounds. For hypergraphs with maximum degree Delta and edge size ratio ρ, we give a non-adaptive algorithm with O((2n)ρ Delta+1log2 n) queries. To the best of our knowledge, these are the first algorithms with poly(n, m) query complexity for learning non-trivial families of hypergraphs that have a super-constant number of edges of super-constant size.