09/15/2009 - 12:15pm

09/15/2009 - 1:10pm

Speaker:

Mark Huber (Claremont McKenna College)

Abstract:

The set of #P complete problems is the counting equivalent of NP complete problems. For instance, "Is there a Hamiltonian path of length less than 60?" is in NP, while "How many Hamiltonian paths of length less than 60 are there?" is a problem in #P. Often #P problems are of the form: let Z be the sum of w(x), where x ranges over a particular set of combinatorial objects. Then calculating Z exactly is often a #P complete problem. A famous example of this type of problem is the Ising model, where each node in a graph is assigned to be either spin up, or spin down, and w(x) is an energy of the configuration. In this talk, I will discuss three different forms of the Ising model. Two of these forms were already known to be linked by what is called a simulation reduction. Here I will present a result showing that the third form of the model can also be "simulation reduced" to the other two forms. This provides a new proof of a known result regarding the relationship between the values of Z for the different forms, and also results in several new algorithms for the Ising model.

Where:

Millikan 208 (Pomona College)