  We show that in random $K$-uniform hypergraphs of constant average degree,
for even $K \geq 4$, local algorithms defined as factors of i.i.d. can not find
nearly maximal cuts, when the average degree is sufficiently large. These
algorithms have been used frequently to obtain lower bounds for the max-cut
problem on random graphs, but it was not known whether they could be successful
in finding nearly maximal cuts. This result follows from the fact that the
overlap of any two nearly maximal cuts in such hypergraphs does not take values
in a certain non-trivial interval - a phenomenon referred to as the overlap gap
property - which is proved by comparing diluted models with large average
degree with appropriate fully connected spin glass models and showing the
overlap gap property in the latter setting.
