Tel-Aviv University - Computer Science Colloquium

Sunday, Jan 29, 2006, 11:15-12:15

Room 309
Schreiber Building


Yair Weiss

Hebrew University


Solving NP-hard problems in practice – lessons from

computer vision and computational biology



It is often useful to formulate problems in vision

and in computational biology as energy minimization problems.

For many of these problems, finding the global optimum is NP

hard and researchers have focused on approximation methods.

From an application standpoint, using approximations is problematic

because when things fail we don't know whom to blame - the energy function

or the approximate minimization.


In this talk I will describe our recent successes in finding the

GLOBAL optimum for energy functions in stereo vision, side

chain prediction and protein design. Our approach is based

on a classical technique - linear programming (LP) relaxations, but

with a novel twist - we use a variant of belief propagation

to solve the LP relaxation. By using belief propagation,

we can find the global optimum  for  large, real-world

problems in a few minutes.


Joint work with Talya Meltzer and Chen Yanover