![Computational Complexity of Statistical Inference_hi-res logo](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-03/Computational%20Complexity%20of%20Statistical%20Inference_hi-res.jpg?h=ccd3d9f7&itok=qCiIzWU5)
Description
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/
All scheduled dates:
Upcoming
No Upcoming activities yet