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

Understand

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 random input.
• Much less is known about the algorithmic universality of specific methods for solving such variational problems.
• Namely, whether algorithms tuned to specific variational tasks produce the same asymptotic behavior across different input distributions with matching moments.