Algorithmic Universality, Low-Degree Polynomials, and Max-Cut in Sparse Random Graphs

Houssam El Cheairi, David Gamarnik

Universality, namely distributional invariance, is a well-known property for many random structures. For example, it is known to hold for a broad range of variational problems with…