  We study the algorithmic task of finding large independent sets in
Erdos-Renyi $r$-uniform hypergraphs on $n$ vertices having average degree $d$.
Krivelevich and Sudakov showed that the maximum independent set has density
$\left(\frac{r\log d}{(r-1)d}\right)^{1/(r-1)}$. We show that the class of
low-degree polynomial algorithms can find independent sets of density
$\left(\frac{\log d}{(r-1)d}\right)^{1/(r-1)}$ but no larger. This extends and
generalizes earlier results of Gamarnik and Sudan, Rahman and Virag, and Wein
on graphs, and answers a question of Bal and Bennett. We conjecture that this
statistical-computational gap holds for this problem.
  Additionally, we explore the universality of this gap by examining
$r$-partite hypergraphs. A hypergraph $H=(V,E)$ is $r$-partite if there is a
partition $V=V_1\cup\cdots\cup V_r$ such that each edge contains exactly one
vertex from each set $V_i$. We consider the problem of finding large balanced
independent sets (independent sets containing the same number of vertices in
each partition) in random $r$-partite hypergraphs with $n$ vertices in each
partition and average degree $d$. We prove that the maximum balanced
independent set has density $\left(\frac{r\log d}{(r-1)d}\right)^{1/(r-1)}$
asymptotically. Furthermore, we prove an analogous low-degree computational
threshold of $\left(\frac{\log d}{(r-1)d}\right)^{1/(r-1)}$. Our results
recover and generalize recent work of Perkins and the second author on
bipartite graphs.
  While the graph case has been extensively studied, this work is the first to
consider statistical-computational gaps of optimization problems on random
hypergraphs. Our results suggest that these gaps persist for larger
uniformities as well as across many models. A somewhat surprising aspect of the
gap for balanced independent sets is that the algorithm achieving the lower
bound is a simple degree-1 polynomial.
