  Let $\mathcal{H}(k,n,p)$ be the distribution on $k$-uniform hypergraphs where
every subset of $[n]$ of size $k$ is included as an hyperedge with probability
$p$ independently. In this work, we design and analyze a simple spectral
algorithm that certifies a bound on the size of the largest clique,
$\omega(H)$, in hypergraphs $H \sim \mathcal{H}(k,n,p)$. For example, for any
constant $p$, with high probability over the choice of the hypergraph, our
spectral algorithm certifies a bound of $\tilde{O}(\sqrt{n})$ on the clique
number in polynomial time. This matches, up to $\textrm{polylog}(n)$ factors,
the best known certificate for the clique number in random graphs, which is the
special case of $k = 2$.
  Prior to our work, the best known refutation algorithms [CGL04, AOW15] rely
on a reduction to the problem of refuting random $k$-XOR via Feige's XOR trick
[Fei02], and yield a polynomially worse bound of $\tilde{O}(n^{3/4})$ on the
clique number when $p = O(1)$. Our algorithm bypasses the XOR trick and relies
instead on a natural generalization of the Lovasz theta semidefinite
programming relaxation for cliques in hypergraphs.
