Events
Fall 2021
CCSI Overlap Gap Property Reading Group: Low-Degree Hardness of Max Independent Set
Sep 7, 2021 2:00 pm – 3:00 pm
Parent Program:
Speaker:
Alex Wein (UC Berkeley)
Location:
Room 116
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/
