  Belief propagation (BP) is a message-passing heuristic for statistical
inference in graphical models such as Bayesian networks and Markov random
fields. BP is used to compute marginal distributions or maximum likelihood
assignments and has applications in many areas, including machine learning,
image processing, and computer vision. However, the theoretical understanding
of the performance of BP is unsatisfactory.
  Recently, BP has been applied to combinatorial optimization problems. It has
been proved that BP can be used to compute maximum-weight matchings and
minimum-cost flows for instances with a unique optimum. The number of
iterations needed for this is pseudo-polynomial and hence BP is not efficient
in general.
  We study belief propagation in the framework of smoothed analysis and prove
that with high probability the number of iterations needed to compute
maximum-weight matchings and minimum-cost flows is bounded by a polynomial if
the weights/costs of the edges are randomly perturbed. To prove our upper
bounds, we use an isolation lemma by Beier and V\"{o}cking (SIAM J. Comput.
2006) for matching and generalize an isolation lemma for min-cost flow by
Gamarnik, Shah, and Wei (Operations Research, 2012). We also prove almost
matching lower tail bounds for the number of iterations that BP needs to
converge.
