Speaker: Dr.Zhaohui Wei Centre for Quantum Technologies of Singapore
Time: 2014-11-26 15:00-2014-11-26 17:00
Venue: FIT 1-222

Abstract:

In recent years, a breakthrough in optimization theory is that it has been proved that linear programming cannot solve TSP, an NP-C problem, efficiently. People conjecture that semidefinite programming cannot do this either, and this is a major open problem at present. To prove this conjecture, one has to find a strong lower bound for the PSD-rank of the corresponding slack matrix. However, it has been realized that PSD-rank is very hard to bound. In this talk, we will introduce some related results on this conjecture, including the proof for a special case.

Short Bio:

Zhaohui Wei is currently a research fellow in the Centre for Quantum Technologies of Singapore, and the School of Physical and Mathematical Sciences, Nanyang Technological University. He received his PhD degree in Computer Science from Tsinghua University in 2009, and his research focuses on quantum information & quantum computation, computational complexity, and communication complexity.