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 

Add to Calendar

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/pdf/2004.12063.pdf , https://arxiv.org/pdf/2010.06563.pdf ​