学术报告|
当前位置:首页 > 科研 > 学术报告
发表时间:2018-08-06 阅读次数:153次
报告题目: Siegel's theorem, edge coloring, and a holant dichotomy
报 告 人:Jin-Yi Cai
报告人所在单位:University of Wisconsin-Madison
报告日期:2018-08-06 星期一
报告时间:14:00-15:00
报告地点:光华东主楼2201
  
报告摘要:

 What does Siegel's theorem on finiteness of integer solutions have to do with complexity theory? In this talk we discuss a complexity dichotomy theorem for counting problems. Such a dichotomy is a classification of a class of problems into exactly two kinds: those that are polynomial time computable, and those that are #P-hard, and thus intractable.  An example problem in this dichotomy is the problem of counting the number of valid edge colorings of a graph. We will show that an effective version of Siegel's theorem and some Galois theory are key ingredients in the proof of this dichotomy. Along the way we will also meet the Tutte polynomial, medial graphs, Eulerian orientations, Puiseux series, and a certain lattice condition on the (logarithm of) the roots of polynomials with integer coefficients.
Joint work with Heng Guo and Tyson Williams.

海报

 

  
本年度学院报告总序号:198

Copyright © |2012 复旦大学数学科学学院版权所有 沪ICP备042465  

电话:+86(21)65642341 传真:+86(21)65646073