Liu, Tian

Associate Professor

Research Interests: Algorithm and complexity

Office Phone: 86-10-6276 5818

Email: lt@pku.edu.cn

Liu, Tian is an associate professor in the School of Computer Science. He obtained his B.Sc. from University of Science and Technology of China (USTC) in 1989, and Ph.D. from Peking University in 1999 respectively. His research interests include algorithm analysis and computational complexity.

Dr. Liu has published more than 40 research papers, and most of them are published in international conferences and journals, such as IJCAI, SCT, COCOON, COCOA, TAMC, AAIM, FAW, TCS, JOCO, JSTAT, QIC, and M&M. He has served in the Technical Program Committee of various international conferences including TAMC, FAW and IC3. He is serving as a member of CCF Theoretical Computer Science Specialized Committee.

Dr. Liu has more than seven research projects including NSFC and 863 projects. His research achievements are summarized as follows:

1)  Structural parameters of random (hyper)graphs: One major research topic in random constraint satisfaction problems (CSPs) is to show a rigorous link between the hardness of random instances and the phase transition phenomena. He proposed to use large structural parameters, such as (hyper)tree-width, hinge-width and decycling numbers, of the random constraint (hyper)graphs to provide theoretical evidences on the hardness of a random CSP model called Model RB. These results are published on top conference IJCAI and decent journals TCS, JOCO, M&M, and JSTAT. The result on tree-width is cited by leading researchers from Stanford and Weizmann.

2)  Tree-convex bipartite graphs: Some NP-complete graph problems are still intractable on bipartite graphs, but tractable on convex bipartite graphs or chordal bipartite graphs. He defined tree-convex bipartite graphs as a generalization of convex bipartite graphs and chordal bipartite graphs, and find the complexity of these graph problems are sensitive to the shapes of associated trees. For example, when the associated tree is a star, the problems will remain NP-complete, but when the associated tree is a triad (three paths with a common end), the problems will be tractable. These results are cited in Information System on Graph Classes and their Inclusions (an online encyclopedia of graph classes, http://www.graphclasses.org/) .

3)  Post-processing of quantum key distributions (QKD): Reconciliation is a key step in quantum key distribution. He conducted a system research on the reconciliation algorithms in QKD, including Cascade, Winnow, LDPC, and Polar Code. These results are cited as basic references in European HIPANQ project workshop and as major references in USA Air Force technical reports and a paper in QIC.