Mingyu Xiao: How Fast Can We Exactly Solve NP-Complete Problems?

Speaker:

Mingyu Xiao (University of Electronic Science and Technology of China)

Time:

• 16:20-17:20 (Time in Beijing)
• September 30, 2022 (Friday)

Venue:

518, Research Building 4

Abstract:

Under the hypothesis P $!=$ NP, NP-complete problems cannot be solved in polynomial time. Under the ETH hypothesis, the SAT problem (the first NP-complete problem) cannot be solved in sub-exponential time. Under the SETH hypothesis, the SAT problem has no algorithm with running time better than the trivial bound $O(2^n)$, where n is the number of variables in the formula. However, some NP-complete problems allow algorithms with running time bound better than the trivial bound $O(2^n)$, and some can even be solved in sub-exponential time under ETH. In this talk, I will introduce the current status of exact algorithms and some techniques to break the border of $O(2^n)$ and also to design sub-exponential algorithms.

Speaker Bio:

2008年在香港中文大学获得计算机博士学位之后进入电子科技大学工作，现在为电子科技大学计算机学院教授，副院长。主要从事算法分析与设计、机制设计与博弈论、人工智能中的基础算法理论等方向的研究，在Information and Computation、JCSS、Algorithmica、ACM/IEEE Trans.、ICALP、IJCAI、AAAI、WWW、INCOFOM等算法、人工智能领域顶级期刊和会议上发表论文超过100篇，撰写英文专著1部，主持（完成）国家自然科学基金项目5项。是参数算法和精确算法国内外知名的学者。