A naukri.com initiative
Arxiv
5d
203
Image Credit: Arxiv
Learning Low Degree Hypergraphs
- We study the problem of learning a hypergraph via edge detecting queries.
- Learning a hypergraph with m edges of max size d requires Ω((2m/d)^(d/2)) queries.
- We identify hypermatchings and low-degree near-uniform hypergraphs as learnable with poly(n) queries.
- For hypergraphs with max degree Δ and edge size ratio ρ, we give a non-adaptive algorithm with O((2n)^(ρΔ+1)log^2n) queries.
Read Full Article
12 Likes
For uninterrupted reading, download the app