Speaker: Mingyu Xiao University of Electronic Science and Technology of China (UESTC)
Time: 2021-03-22 16:00-2021-03-22 17:00
Venue: FIT1-222

Abstract:

Under the hypothesis P != NP, NP-complete problems cannot be solved in polynomial time. Under ETH, the SAT problem (the first NP-complete problem) cannot be solved in sub-exponential time. Under SETH, the SAT problem has not algorithms with running time better than the trivial bound O(2^n), where n is the number of variables in the formula. However, there are some NP-complete problems that allow algorithms with running time bound much better than the trivial bound O(2^n), and some NP-complete problems that can be solved in sub-exponential time even when ETH holds. In this talk, we will introduce some techniques to design algorithms breaking the border of O(2^n) and also to design sub-exponential algorithms.

Short Bio:

Currently, I am a professor in the school of computer science and engineering, University of Electronic Science and Technology of China (UESTC), Chengdu, China.  I received my Ph.D in computer science from The Chinese University of Hong Kong under the supervision of Professor Andrew Chi-Chih Yao and Professor Leizhen Cai in 2008. I received my M.S and B.S in mathematics from Central South University in 2005 and 2002, respectively.