Maximum Cut problem on sparse random hypergraphs: Structural results using the interpolation method and the algorithmic implications - David Gamarnik

We consider a particular version of the Maximum Cut problem (to be defined in the talk)  on a  sparse random K-uniform hypergraph, when K is even. The goal is to compute the maximum cut value w.h.p., and ideally to find an algorithm which finds a near maximum cut value in polynomial time. Using the interpolation technique we obtain the value of the maximum cut asymptotically as the edge density increases. Specifically, the interpolation method allows us to connect the maximum cut value with the ground state of the associated Sherrington-Kirkpatrick (SK) spin glass model. Furthermore, in the case when K is at least 4, we show that the configurations nearing the ground state in the SK model exhibits the Overlap Gap Property (OGP): every two such configurations are either nearly identical or nearly orthogonal to each other. Using the interpolation method the same is shown to hold for the original Maximum Cut problem. The presence of the OGP implies that no local algorithm defined as a factor of i.i.d., which will be defined in the talk, can succeed in constructing a nearly optimal cut. The existence of a polynomial time algorithm for constructing a nearly optimum cut on a random K-uniform hypergraph remains an open problem.