Fall 2021

The Overlap Gap Property For Inference: Power And Limitations

Monday, Sep. 13, 2021 4:05 pm4:30 pm

Add to Calendar


Ilias Zadik (Massachusetts Institute of Technology)


Calvin Lab Auditorium

Over the recent years, the Overlap Gap Property (OGP) has been used as a topological barrier whose appearance (empirically) coincides with the onset of algorithmic hardness for various random settings. The two main categories of problems the OGP has been applied for is optimization in random environments and inference. In this talk, we will briefly survey the notion of OGP in the context of inference, discuss some of its succesful applications and future directions.

PDF icon slides726.39 KB