Sharp Thresholds Imply Circuit Lower Bounds: From Random 2-SAT to Planted Clique

Abstract: In this talk, we will present a recent result that if a Boolean function exhibits a sharp threshold at an arbitrary density then it immediately implies a bounded depth circuit lower bounds for computing this function on average. By leveraging the rich literature of sharp thresholds, this method implies multiple new average-case circuit lower bounds. Time permitted, we will discuss new AC0 lower bounds for the random 2-SAT problem at the satisfiability threshold, the k-clique decision problem in random graphs, and also the planted clique model from the literature of statistical estimation. Joint work with David Gamarnik and Elchanan Mossel. 

Speaker bio: Ilias Zadik is Assistant Professor of Statistics and Data Science at Yale University. His research mainly focuses on the mathematical theory of statistics and its many connections with other fields such as computer science, probability theory, and statistical physics. His primary area of interest is the study of “computational-statistical trade-offs,” where the goal is to understand whether computational bottlenecks are unavoidable in modern statistical models or a limitation of currently used techniques. Prior to Yale, he held postdoctoral positions at MIT and NYU. He received his PhD from MIT in 2019.