Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Definability of Combinatorial Functions
event speaker icon
Tommer Kotek (Ph.D. Thesis Seminar)
event date icon
Wednesday, 11.01.2012, 14:30
event location icon
Taub 601
event speaker icon
Advisor: Prof. J.A. Makowsky
The complexity of several prominent graph polynomials, such as the chromatic polynomial and the matching polynomial, has been studied in the literature. In 2008 Makowsky raised a conjecture which generalizes complexity results for specific graph polynomials to an infinite class of graph polynomials which include almost all of those in the literature. The conjecture states roughly that the evaluations of such graph polynomials are equivalent in terms of running-time complexity, except for a small and nicely structured exception set. As a case study for the conjecture, we consider a graph polynomial which originated in statistical mechanics in order to study phase transitions. A trivariate Ising polynomial was studied with respect to its approximability by L. A. Goldberg, M. Jerrum and M. Paterson in 2003. A related bivariate Ising polynomial was studied in by D. Andr\'{e}n and K. Markstr\"{o}m in 2009. We show that both Ising polynomials satisfy versions of Makowsky's conjecture, even when the domain is restricted. Under a counting version of the Exponential Time Hypothesis we give a dichotomy theorem stating that evaluations of the bivariate Ising polynomial either require exponential time runnning-time, or can be computed in polynomial time.