2025/01/22 by Bethany Austhof, Austhof, Bethany, Lev Reyzin +3 · 1 citation
Computer Science · #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Face and Expression Recognition #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Machine Learning and ELM
paper · pdf · doi:10.48550/arxiv.2501.12771
openalex publication_date 2025/01/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the problem of learning a hidden hypergraph G=(V,E) by making a single batch of queries (non-adaptively). We consider the hyperedge detection model, in which every query must be of the form: ``Does this set S⊆ V contain at least one full hyperedge?'' In this model, it is known that there is no algorithm that allows to non-adaptively learn arbitrary hypergraphs by making fewer than Ω(min\m2log n, n2\) even when the hypergraph is constrained to be 2-uniform (i.e. the hypergraph is simply a graph). Recently, Li et al. overcame this lower bound in the setting in which G is a graph by assuming that the graph learned is sampled from an Erdős-Rényi model. We generalize the result of Li et al. to the setting of random k-uniform hypergraphs. To achieve this result, we leverage a novel equivalence between the problem of learning a single hyperedge and the standard group testing problem. This latter result may also be of independent interest.