Algorithmic Phase Transition for Large Independent Sets in Dense Hypergraphs

Abhishek Dhawan, Nhi U. Dinh, Eren C. Kızıldağ +2

We study the algorithmic tractability of finding large independent sets in dense random hypergraphs. In the sparse regime, much of the natural algorithms can be formulated within e…