Department of Physics
Research, teaching and outreach in Physics at UW–Madison

Events

Events at Physics
<< Summer 2009 Fall 2009 Spring 2010 >>
Subscribe your calendar or receive email announcements of events
Math Colloquia
Complexity Theory --- The World of P and NP
Date: Friday, September 25th
Time: 4:00 pm
Place: B239 Van Vleck
Speaker: Jin-Yi Cai, UW Madison CS Dept.
Abstract: The study of computational complexity presents challenging mathematical problems. In Complexity Theory computational problems are classified into complexity classes, the best known include P, NP and Valiant's class #P for counting problems. A central problem in Valiant's theory is the permanent vs. determinant problem. We will report some latest progress on this problem. Graph homomorphism was introduced by Lovasz over 40 years ago, and it is also called the partition functions in Statistical Physics, and can encode a rich class of counting problems: Given an $m imes m$ symmetric matrix $A$ over the complex numbers, compute the function $Z_A(cdot)$, where for an arbitrary input graph $G$, [ Z_A(G) = sum_{xi:V(G)
ightarrow [m]} prod_{(u,v)in E(G)} A_{xi(u),xi(v)}.] Our foucs is the computational complexity of $Z_A(cdot)$. With Xi Chen and Pinyan Lu, we have achieved a complete classification theorem for the complexity of $Z_A(cdot)$. The classification proof is too complicated to present, but we will present the proof of a lemma. It states that in order to be computable in polynomial time, the matrix $A$ must possess a group structure. Another component of the proof uses Gauss sums. (In a subsequent Number Theory Seminar I will present some related work.) No prior knowledge of complexity theory is assumed. <br>
Add this event to your calendar