Ilias Zadik is a postdoctoral researcher working at MIT, Mathematics Department, with Prof. Elchanan and Prof. Nike Sun. Prior to that, he spent two years as a postdoctoral fellow at NYU and before that he completed his PhD at MIT with David Gamarnik. His research broadly lies on the interface of high dimensional statistics, the theory of machine learning and discrete probability. He is particularly interesting on understanding computational to statistical trade-offs in inference and (sharp) statistical phase transitions.
Talk: On the second Kahn-Kalai conjecture and statistical inference connections
Abstract: For a given graph H we are interested in the critical threshold p so that a sample from the Erdos-Renyi random graph contains a copy of H with high probability. Kahn and Kalai in 2006 conjectured that it should be given (up to a logarithm) by the minimum p so that in expectation all subgraphs H’ of H appear in the random graph. In this work, we will present a proof of a modified version of this conjecture. Our proof is based on a powerful “spread lemma”, which played a key role in recent breakthroughs (a) on the Erdos-Rado sunflower conjecture (which enjoys many TCS applications) and.(b) the fractional Kahn-Kalai conjecture. Time permitting, we will discuss also a new proof of the spread lemma using Bayesian inference tools. Joint work with Elchanan Mossel, Jonathan Niles-Weed and Nike Sun.