[Archimedes Talks Series] Counting Stars is Constant-Degree Optimal For Detecting Any Planted Subgraph

Title: Counting Stars is Constant-Degree Optimal For Detecting Any Planted Subgraph

Presenter: Professor Ilias Zadik, Assistant Professor at Yale University


Abstract: Over the last decade, multiple papers have studied the power of low-degree polynomials in detecting subgraphs in random graphs. Formally, all these papers study special cases of the following general hypothesis testing problem: let H=H_n be an arbitrary undirected graph on n vertices. Can a D-degree polynomial detect between a ``null'' Erdős-Rényi random graph G(n,p) and a ``planted'' random graph which is the union of G(n,p) together with a random copy of H=H_n? The special cases include the case when H is a clique (the planted clique model), when  H is a matching (the planted matching problem), and more.

 

We prove a new unifying positive result that for all H=H_n, as long as D=O(1), the optimal such D-degree polynomial is always given simply by the count stars in the input graph. This allows us to prove multiple old and new results in the literature of low-degree polynomials for this task.

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.