Seminars

View all Seminars  |  Download ICal for this event

On Bayesian Estimation and constraint satisfaction

Series: Bangalore Theory Seminars

Speaker: Prasad Raghavendra, U.C. Berkeley

Date/Time: Sep 06 11:00:00

Location: CSA Seminar Hall (Room No. 254, First Floor)

Abstract:
Bayesian estimation is the problem of inferring the values of hidden variables from observed data. Formally, the problem is specified by a joint distribution P(x, G) over a set of hidden variables x and observations G. The algorithmic problem is to (even approximately) infer the values of x given the observed values G, using the Bayes rule.

Beginning with the work of Krzakala and Zdeborova [KZ09], a precise and comprehensive theory of the computational complexity of sparse random instances of Bayesian CSPs is emerging. Inspired by ideas from statistical physics, this theory predicts that sparse random Bayesian CSPs undergo a computational phase transition, in which they abruptly go from being computationally easy to being intractable. Moreover, the theory predicts the precise location of this transition for any given Bayesian CSP. This talk will survey algorithms and lower bounds for Bayesian CSPs, and outline some directions for future research.


Microsoft teams link:

Link


We are grateful to the Kirani family for generously supporting the theory seminar series


Hosts: Rameesh Paul, Rachana Gusain, Rahul Madhavan, KVN Sreenivas