2024-06-30-bresler24a.md

title	section	abstract	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	container-title	volume	genre	issued	pdf	extras
Thresholds for Reconstruction of Random Hypergraphs From Graph Projections	Original Papers	The graph projection of a hypergraph is a simple graph with the same vertex set and with an edge between each pair of vertices that appear in a hyperedge. We consider the problem of reconstructing a random $d$-uniform hypergraph from its projection. Feasibility of this task depends on $d$ and the density of hyperedges in the random hypergraph. For $d=3$ we precisely determine the threshold, while for $d\ge 4$ we give bounds. All of our feasibility results are obtained by exhibiting an efficient algorithm for reconstructing the original hypergraph, while infeasibility is information-theoretic. Our results also apply to mildly inhomogeneous random hypergrahps, including hypergraph stochastic block models (HSBM). A consequence of our results is an optimal HSBM recovery algorithm, improving on Gaudio and Joshi (2023a).	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	bresler24a	0	Thresholds for Reconstruction of Random Hypergraphs From Graph Projections	632	647	632-647	632	false	Bresler, Guy and Guo, Chenghao and Polyanskiy, Yury	given family Guy Bresler given family Chenghao Guo given family Yury Polyanskiy	2024-06-30		Proceedings of Thirty Seventh Conference on Learning Theory	247	inproceedings	date-parts 2024 6 30	https://proceedings.mlr.press/v247/bresler24a/bresler24a.pdf	label link Supplementary ZIP https://proceedings.mlr.press/v247/bresler24a/bresler24a-supp.zip