Posts Tagged Claremont

Giving an Algebra/Number Theory/Combinatorics Seminar this Tuesday

This Tuesday I’m starting off the talks for the Spring in the Algebra/Number Theory/Combinatorics Seminar here in Claremont.  It will be at 12:15 on 24 Jan 2012 in Millikan 134.  Complete details can be found here.  The title is “A gadget for reducing the Ising model to matchings”, and it is joint work that I did with my first graduate student, Jenny Law.

Abstract:  In my talk last semester in the seminar, I presented a classic result: the problem of counting the number of solutions to a logic formula can be turned into a problem of summing weighted perfect matchings in a graph. The key idea was the use of a combinatorial “gadget”. In this talk I’ll present a gadget developed with my first graduate student, Jenny Law, that allows for what is called a simulation reduction. The reduction works as follows: if you are able to sample randomly from a weighted distribution on perfect matchings in a graph, then you can also simulate from the Ising model, a classical model from statistical physics that has been heavily studied since its inception in the 1920’s. (http://arxiv.org/abs/0907.0477)

Advertisements

, , , ,

Leave a comment

Claremont Algebra/Number Theory/Combinatorics Seminar

Today I am giving the Algebra/Number Theory/Combinatorics Seminar at the Claremont Colleges.  This talk, “What is a #P complete problem” is a prequel in a sense to an earlier talk I gave in the Seminar last year.  In the earlier talk, I discussed new methods for approximating the permanent of a matrix.  In this talk, I will argue that finding the permanent is a hard problem.  One way to characterize hardness of a numerical problem is the notion of  number P problems, or #P for short.  I will define #P problems and give Ben-Dor and Halevi’s 1993 proof that finding the permanent of a matrix is a #P hard problem, so if we could solve it quickly, any problem in #P could also be solved quickly.

, , , ,

Leave a comment