Search Mailing List Archives


Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] Theory Lunch 3/10: Siqi Liu (Berkeley)

Junyao Zhao junyaoz at stanford.edu
Mon Mar 7 09:28:19 PST 2022


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/20220307/ffb51c9b/attachment-0002.html>


More information about the theory-seminar mailing list