Physics (Internal)

Making Really Hard Modeling Problems Much Easier

This event is part of the Biophysics/Condensed Matter Seminar Series.

Abstract:
Physically-motivated modeling underlies our efforts to understand
biomolecule structures from their genetic recipes, to assemble large
collections of fragmented and overlapping genetic data into coherent
wholes, or to search for stable strategies in complex, turbulent
economic markets. These large problems are difficult because of the
cumbersome representations that their state requires, and the
combinatoric explosion of possibilities that must be searched. In the
past 25 years or so, progress in these areas has often involved taking
the physical picture and intuitions of the more complicated problems
down to label an underlying (and still difficult) combinatorial problem,
in order to discover is some combination of intelligent moves, pruning,
and better cost function characterization can make the problems far
easier. Some fairly general examples now exist of how to tell is a
problem is really hard, and there are general strategies to follow in
finding effective heuristics. The Travelling Salesman Problem has long
been studied from this point of view and a less familiar problem,
finding coverings, independent sets, and cliques, may have a similar
broad relevance. I’ll talk about some old and some new work in both
areas, and show how these relate to the physical problems.