Search Results

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 either the local or the low-degree polynomial (LDP) framework, and a rich literature has subsequently identified nearly sharp algorithmic thresholds within these classes by exploiting their stability. In the dense setting, however, the algorithmic paradigms are fundamentally different: they are online and thus need not be stable. Perhaps more crucially, even for the classical Erdős-Rényi random graph G(n,p), LDPs are conjectured to fail in the "easy" regime accessible to online algorithms, thereby challenging their viability for dense models. Our focus is on two models: (i) finding large independent sets in dense r-uniform Erdős-Rényi hypergraphs, where each size-r hyperedge is present independently with probability p, and (ii) the more challenging problem of finding large γ-balanced independent sets in dense r-uniform r-partite hypergraphs, where the vertex set is the disjoint union V_1 ⊔ ⋯ ⊔ V_r with |V_i| = n for all i, each hyperedge in V_1× ⋯ × V_r is present independently with probability p, and the i-th coordinate of γ ∈ ℚ^r specifies the proportion of vertices from V_i in the independent set. For both models, we pinpoint the size of the largest independent set and design online algorithms that achieve a multiplicative approximation factor of r^{1/(r-1)} in the uniform and (max_i γ_i)^{-1/(r-1)} in the r-partite model. Furthermore, we establish matching algorithmic lower bounds, showing that these computational gaps are sharp: no online algorithms can breach these gaps. Our results provide a detailed landscape for dense hypergraphs, thereby completing the picture for dense models in a manner parallel to the sparse counterparts developed recently. Our main technical contribution is twofold: a novel staged and bucketed greedy algorithm and a stopping-time argument tailored to the hypergraph and multipartite structure for algorithmic hardness, both of which may be of independent interest. The algorithms and proof techniques in the dense regime differ substantially from those in the sparse, yet the resulting computational gaps are remarkably analogous, pointing to a form of universality. More conceptually, our results corroborate a hypothesis from statistical mechanics linking glassy equilibrium to computational hardness: optimization problems become far more intricate in the presence of global constraints.