Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique Number

Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar

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 t…