Image

Low-degree hardness of random optimization problems, in particular the maximum independent set problem. The proof has two ingredients: (1) (Multi, Ensemble) Overlap Gap Property and (2) Stability of Low-Degree Polynomials.
Link to Papers: https://arxiv.org/
No Upcoming activities yet