Monday February 11, 2002

Speaker: Martin Cohn

Title: The Complexity of a Vision Model

Abstract: Dan Graboi and John Lisman (Brandeis Biology) describe a computational model of how the human vision system recognizes words. Their experiments found that a greedy algorithm worked best.

I'll discuss their model and show that the greedy algorithm is not optimal, but that the problem as posed is NP-complete, so that an optimal strategy is (almost certainly) not feasible. On the other hand, the problem is approximable by the very algorithm they suggest, and any better approximation can be proved to be NP-hard.