BEGIN:VCALENDAR
VERSION:2.0
CALSCALE:GREGORIAN
PRODID:UW-Madison-Physics-Events
BEGIN:VEVENT
SEQUENCE:0
UID:UW-Physics-Event-1642
DTSTART:20090925T210000Z
DURATION:PT1H0M0S
DTSTAMP:20260417T151658Z
LAST-MODIFIED:20090921T152921Z
LOCATION:B239 Van Vleck
SUMMARY:Complexity Theory --- The World of P and NP\, Math Colloquia\,
  Jin-Yi Cai\, UW Madison CS Dept.
DESCRIPTION:The study of computational complexity presents challenging
  mathematical problems. In Complexity Theory computational problems ar
 e classified into complexity classes\, the best known include P\, NP a
 nd Valiant's class #P for counting problems. A central problem in Vali
 ant's theory is the permanent vs. determinant problem. We will report 
 some latest progress on this problem. Graph homomorphism was introduce
 d by Lovasz over 40 years ago\, and it is also called the partition fu
 nctions in Statistical Physics\, and can encode a rich class of counti
 ng problems: Given an $m 	imes m$ symmetric matrix $A$ over the comple
 x numbers\, compute the function $Z_A(cdot)$\, where for an arbitrary 
 input graph $G$\, [ Z_A(G) = sum_{xi:V(G)<br>
\nightarrow [m]} prod_{(
 u\,v)in E(G)} A_{xi(u)\,xi(v)}.] Our foucs is the computational comple
 xity of $Z_A(cdot)$. With Xi Chen and Pinyan Lu\, we have achieved a c
 omplete classification theorem for the complexity of $Z_A(cdot)$. The 
 classification proof is too complicated to present\, but we will prese
 nt the proof of a lemma. It states that in order to be computable in p
 olynomial time\, the matrix $A$ must possess a group structure. Anothe
 r component of the proof uses Gauss sums. (In a subsequent Number Theo
 ry Seminar I will present some related work.) No prior knowledge of co
 mplexity theory is assumed. <br><br>
\n
URL:https://www.physics.wisc.edu/events/?id=1642
END:VEVENT
END:VCALENDAR