Pinyan Lu(陆品燕)

Pinyan Lu

Adjunct Research Fellow


Brief Introduction

Pinyan Lu is a researcher at Theory Group of Microsoft Research Asia and an Adjunct Research Fellow at Shanghai Jiao Tong University. He studied in Tsinghua University (BS (2005) and PhD (2009) both in Computer Science). He joined Microsoft Research Asia as an associate researcher in 2009. He is mainly interested in complexity theory, algorithms design and algorithmic game theory. He has received various awards, including the Best Paper Award in ICALP 2007, FAW 2010, ISAAC 2010 and so on.

Research Interests

Computational complexity, dichotomy theorems and counting problems, Algorithm design, holographic algorithms and approximate counting, Property of Spin systems, Gibbs measure, Computational economics, Algorithmic game theory, mechanism design and auction theory

Research highlights

To characterize which problems are ultimately efficient computable and which are not is the most fundamental question in computer science, the implications of which go well beyond computing to all engineering disciplines and to the entire society. Dr. Pinyan Lu’s main research focus is on this direction. For example, a number of Dr. Lu’s papers are dichotomy theorems for certain computational framework. That is to say, they give a characterization: If certain conditions are satisfied, the problem is polynomial time computable; otherwise, it is hard. These works greatly deepen our understanding of this area.

Pinyan is also very much interested in the research in the interface of computer science and economics. He has done some significant work in such topics including truthful mechanism design, property of Nash equilibrium, and so on.

Selected Publications