Belief propagation has been shown to be a very powerful method through research in probabilistic graphical models.However, I don't know anything about BP that's comparable to MCMC methods where we can have fully polynomial randomized approximation schemes (FPRAS) for #P-complete problems.Could someone point me to some references?
Theoretical guarantees for running times of belief propagation methods?
cc.complexity theory;reference request;graph algorithms;machine learning;st.statistics
Here's a paper where the authors used BP to obtain a fully polynomial-time randomized approximation scheme for the the capacitated minimum-cost network ow problem.