Xu, Jin

Professor

Research Interests: Bio-computer, graph theory, information security

Office Phone: 86-10-6275 0359

Email: jxu@pku.edu.cn

Xu, Jin is a professor (of the first grade) in the School of Computer Science at Peking University. He has obtained two PhDs both in science and engineering. His research interests include bio-informatics and bio-computer, graph theory and combinatorial optimization, neural networks and information security, etc.

Dr. XU is a member of Educational Advisory Committee of Cyberspace Security, Ministry of Education; deputy director of Circuits and Systems Society branch, Chinese Institute of Electronics; director of Graph Theory and System Optimization Major Committee, Chinese Institute of Electronics; chief scientist of key special subjects of Central Military Commission Science and Technology Committee of China. He has published more than 300 academic papers, about 200 of which have been indexed by SCI. He has presided over tens of national natural science foundation projects, including major projects, major equipment on special, national 863 projects and 973 projects, etc. As the first persons involved, he received one Second Class National Prize of Natural Science and three First Ministerial Prizes of Natural Science. He has acted 5 times as Chairman of the International Conference on Bio-inspired Computing.

Dr. XU’s research achievements are summarized as follows:

1)  Biological computing models and implementation: In 2010, Dr. XU proposed a parallel DNA computing model. With this model, all 48 3-colorings of a graph of order 61 are successfully worked out, which is by far the largest international bio-computing experiment. Professor B?a?ewicz, winner of the European Journal of Operational Research, said: The proposed DNA algorithm solves the coloring problem. Professor Wing, member of the US National Academy of Sciences, and Professor Richard in University of California, the world's leading DNA computing experts, commented: "Your recent breakthrough in DNA computing" "This is very exciting".

2)  Probe Machine. In 2016, Dr. XU proposed a novel computing model, called Probe Machine. Different from Turing Machine, Probe Machine is a fully-parallel computing model in the sense that it can simultaneously process multiple pairs of data, rather than sequentially process every pair of linearly-adjacent data. And in particular he shows that Turing Machine is a special case of Probe Machine. With this computing model, people can enumerate all solutions by only one probe operation. His article " Probe Machine " was selected as one of the three featured papers by the IEEE Computational Intelligence Society for 2016, and the first CIS-publication outstanding paper in fourth quarter of 2016 by the IEEE Computational Intelligence Magazine.

3)  Graph Theory. Dr. XU studied systematically the theory on the structure and coloring of maximal planar graphs. He established two recursion formulas of chromatic polynomial by contracting wheels of a maximal planar graph. By using these formulas, the research object of Four-Color Conjecture boils down a special class of graphs, viz., 4-chromatic-funnel pseudo uniquely-4-colorable maximal planar graphs. By establishing the extending-contracting operations and the coloring operations of maximal planar graphs, he divided all maximal planar graphs into three types: Kempe-type, 2-chromatic unchanged-cycle-type, circular-cycle-type. Furthermore, he translated skillfully the Four-Color Problem into 2-chromatic unchanged-cycle maximal planar graph problem and obtained a mathematical proof of this problem.