[Colloquium] THEORY SEMINAR: Pedro Felzenszwalb on November 2, 2010

[Katie Casey]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO

Date: Tuesday, November 2, 2010 
Time: 3:00 p.m.
Place: Ryerson 251, 1100 E. 58th Street

----------------------------------------------

Speaker:		Pedro Felzenszwalb

From:		University of Chicago

Web page:	http://www.cs.uchicago/people/pff

Title: Fast Inference with Min-Sum Matrix Product 
(or how I finished a homework assignment 15 years later)

Abstract:  
Graphical models provide a general framework for modeling dependencies
among random variables.  The MAP inference problem in a graphical
model has a wide range of applications.  I will show how important
cases can be solved efficiently using a fast algorithm for computing
min-sum products of n by n matrices.  I will also describe an
algorithm for computing the min-sum product in O(n^2 log n) expected
time, assuming the entries in the matrices are independent samples
from a uniform distribution.  Finally, I will describe some variants
that work well for inputs that arise in several real problems.  This
leads to significant speedups over previous inference methods in
applications within computer vision and natural language processing.

Refreshments will be served prior to the talk at 2:30 in Ryerson 255.