CTIT University of Twente
Research Business & Innovation About CTIT Research Calls Looking for a job? Intranet

SMABEP: Smoothed Analysis of Belief Propagation

Project Number: 613.001.023

Project Manager: Dr. Bodo Manthey

Faculty of Electrical Engineering, Mathematics and Computer Science

Tel.: +31 53 489 3385

Email: b.manthey@utwente.nl

Project website:


Belief propagation is a heuristic approach for solving large-scale statistical inference problems. It is an easy-to-implement heuristic based on message-passing that usually converges quickly. As such, it has become very popular, and it has proved to be successful in a wide range of applications.

Its success in practice, however, is at stark contrast to the lack of theoretical understanding of its performance. Belief propagation shares this aspect with many algorithms. The reason for the discrepancy between remarkably good performance in practice and unsatisfactory theoretical understanding is often that performance is analyzed in terms of worst-case analysis; worst-case analysis is often far too pessimistic. Indeed, worst-case instances are often artificially constructed and rarely show up in applications. An adequate theoretical analysis, however, should measure the performance in terms of “typical” rather than “pathological” instances.

To provide a more realistic analysis of algorithms, the concept of smoothed analysis has been developed: An adversary specifies an instance, and then the expected performance is measured when this instance is slightly randomly perturbed. Smoothed analysis takes into account that practical data is often noisy, e.g., due to measurement errors. Smoothed analysis has already been applied successfully to explain the performance of a variety of algorithms.

The aim of this project is a smoothed analysis of belief propagation. We will focus on the application of belief propagation to combinatorial optimization problems. The goal is to get a deeper understand- ing of its performance and to bridge the gap between theoretical and practical performance of belief propagation.

Project duration: 1-9-2011 / 1-9-2015

Project budget: 211.500 €

Number of person/years: 1 fte

Involved groups: Discrete Mathematics and Mathematical Programming (DMMP)