Search Mailing List Archives
[theory-seminar] Theory Lunch 3/10: Siqi Liu (Berkeley)
Junyao Zhao
junyaoz at stanford.edu
Thu Mar 10 09:56:47 PST 2022
A gentle reminder: This is happening in 10 minutes.
________________________________
From: theory-seminar <theory-seminar-bounces at lists.stanford.edu> on behalf of Junyao Zhao <junyaoz at stanford.edu>
Sent: Monday, March 7, 2022 9:28 AM
To: theory-seminar at lists.stanford.edu <theory-seminar at lists.stanford.edu>; thseminar at cs.stanford.edu <thseminar at cs.stanford.edu>
Subject: [theory-seminar] Theory Lunch 3/10: Siqi Liu (Berkeley)
Hello everyone,
This week's theory lunch will take place Thursday at noon in the Engineering Quad<https://www.google.com/maps/place/Science+%26+Engineering+Quad+Courtyard/@37.4284882,-122.1765394,17z/data=!3m1!4b1!4m5!3m4!1s0x808fbb8ce58bcc27:0x677c06a883bb7bb7!8m2!3d37.428484!4d-122.1743507>. We'll start with some socializing, followed by a talk at 12:30pm. Siqi will tell us about: On statistical inference when fixed points of belief propagation are unstable
Abstract: Many statistical inference problems correspond to recovering the values of a set of hidden variables from sparse observations on them. Inspired by ideas from statistical physics, the presence of a stable fixed point for belief propagation has been widely conjectured to characterize the computational tractability of these problems. For community detection in stochastic block models, many of these predictions have been rigorously confirmed. We consider a general model of statistical inference problems that includes both community detection in stochastic block models, and all planted constraint satisfaction problems as special cases. We carry out the cavity method calculations from statistical physics to compute the regime of parameters where recovery should be algorithmically tractable. At precisely the predicted tractable regime, we give a general polynomial-time algorithm for the problem of recovery.
In this talk, we will discuss:
-How to apply cavity method to this general model of statistical inference problems
-Intuitions behind the recovery algorithm
This talk is based on joint work with Sidhanth Mohanty and Prasad Raghavendra.
Cheers,
Junyao
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20220310/c6539eff/attachment-0002.html>
More information about the theory-seminar
mailing list