Ilias Zadik : New Perspectives on Inference and Random Structures

Posted by Gyorgy Turan , part of the Departmental Colloquium.

At

Dec. 5, 2022, 3 p.m.

In

636 SEO

Abstract

The mathematical analysis of high dimensional inference models has been a topic of intense research activity over the last years. This field of study has created a plethora of exciting, fruitful and, sometimes, unexpected interactions between the fields of mathematics, computer science, statistics and statistical physics. In the first part of this talk I will present to you a recent result on the surprising failure of the Metropolis process for the planted clique model, a well-studied random graph inference setting. Our proof is based on leveraging ``bottleneck’’ methods inspired by statistical physics techniques. Notably, our work resolved a well-known open question posed by Jerrum in 1992 and our proposed technique has been leveraged successfully in several other inference settings. In the second part of the talk, I will share with you some new results on how inference techniques can offer alternative proofs of state-of-the-art results in combinatorics, including for example the celebrated fractional Kahn-Kalai conjecture.