The Probabilitas Seminar series focuses on high-dimensional problems that combine statistics, probability, artificial intelligence, information theory, computer science, and other related fields. The upcoming seminar takes place on Tuesday, October 21, at 1:30pm in Science Center 705. This week's speaker will be Ilias Zadik, assistant professor at Yale Statistics and Data Science.
Fundamental Limits of Recovering Planted Subgraphs
In the planted subgraph model, a statistician observes the union of an unknown copy of a fixed “planted” subgraph H and an independent instance of Erdős–Rényi noise G(n,p), with the goal of recovering the location of H from the observed graph. This framework generalizes several classical high-dimensional estimation models, including the planted clique model (Jerrum, 1992), obtained when H is a k-clique, and the planted matching model (Cherktov et al., 2010), when H is a perfect matching.
In this talk, we present new results characterizing the limiting minimum mean squared error (MMSE) for all subgraphs H satisfying a mild density condition. Our unified analysis reveals a rich structure: the limiting MMSE takes a staircase form, with discontinuities determined (up to 1+o(1) error) by natural variants of the subgraph expectation threshold of H, introduced by Kahn and Kalai (2004). Interestingly, our work establishes for the first time a fundamental connection between this combinatorial threshold—long central to probabilistic combinatorics—and the fundamental limits of statistical estimation.
Zoom link:
Topic: Ilias Zadik seminar
Time: Oct 21, 2025 01:30 PM Eastern Time (US and Canada)
Join Zoom meeting
https://harvard.zoom.us/j/91819545451?pwd=c7UqbsnH1g5ucywpNWDXgIb2fpIuQ8.1
Password: 021235
Join by telephone (use any number to dial in)
+1 929 436 2866
+1 301 715 8592
+1 305 224 1968
+1 309 205 3325
+1 312 626 6799
+1 646 931 3860
+1 386 347 5053
+1 507 473 4847
+1 564 217 2000
+1 669 444 9171
+1 669 900 6833
+1 689 278 1000
+1 719 359 4580
+1 253 205 0468
+1 253 215 8782
+1 346 248 7799
+1 360 209 5623
833 928 4609 US Toll-free
833 928 4610 US Toll-free
877 853 5257 US Toll-free
888 475 4499 US Toll-free
833 548 0276 US Toll-free
833 548 0282 US Toll-free
833 928 4608 US Toll-free
International numbers available: https://harvard.zoom.us/u/aoaVf999i
One tap mobile: +19294362866,,91819545451# US (New York)
Join by SIP conference room system
Meeting ID: 918 1954 5451
LOCATION:Science Center 705 STATUS:CONFIRMED DTSTART:20251021T173000Z DTEND:20251021T183000Z END:VEVENT END:VCALENDAR