Adjunct Research Fellow
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.
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
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.
- Approximate Counting via Correlation Decay in Spin Systems.with Liang Li and Yitong Yin, SODA 2012
- On the Approximation Ratio of k-lookahead Auction.with Xue Chen, Guangda Hu and Lei Wang, WINE 2011.
- Optimal Pricing in Social Networks with Incomplete Information.with Wei Chen, Xiaorui Sun, Bo Tang, Yajun Wang and Zeyuan Allen Zhu, WINE 2011
- The Complexity of Symmetric Boolean Parity Holant Problems.with Heng Guo and Leslie Valiant, ICALP 2011
- Non-negative Weighted #CSPs: An Effective Complexity Dichotomy.with Jin-Yi Cai and Xi Chen, CCC 2011
- The Complexity of Weighted Boolean #CSP Modulo k. with Heng Guo, Sangxia Huang and Mingji Xia, STACS 2011
- Dichotomy for Holant* Problems of Boolean Domain.with Jin-Yi Cai and Mingji Xia, SODA 2011
- On the Approximability of Budget Feasible Mechanisms.withNing Chen and Nick Gravin, SODA 2011
- Envy-free Pricing with General Supply Constraints.withSungjinIm and Yajun Wang, WINE 2010
- From Holant To #CSP And Back: Dichotomy For Holantc Problems. with Jin-Yi Cai and Sangxia Huang, ISAAC 2010. (Best Paper Award.)
- Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP.with Jin-Yi Cai and Mingji Xia, FOCS 2010
- On Tractable Exponential Sums.with Jin-Yi Cai, Xi Chen and Richard Lipton, FAW 2010. (Best Paper Award.)
- Graph Homomorphisms with Complex Values: A Dichotomy Theorem.with Jin-Yi Cai and Xi Chen, ICALP 2010
- Asymptotically Optimal Strategy-Proof Mechanisms for Two-Facility Games. withXiaorui Sun, Yajun Wang and Zeyuan Allen Zhu, EC 2010
- On 2-Player Randomized Mechanisms for Scheduling. WINE 2009
- Tighter Bounds for Facility Games.with Yajun Wang and Yuan Zhou, WINE 2009
- Holant Problems and Counting CSP.with Jin-Yi Cai and Mingji Xia, STOC 2009
- A Computational Proof of Complexity of Some Restricted Counting Problems. with Jin-Yi ai and Mingji Xia, TAMC 2009
- Worst-Case Nash Equilibria in Restricted Routing. With Changyuan Yu, WINE 2008
- Randomized Truthful Mechanisms for Scheduling Unrelated Machines. With Changyuan Yu, WINE 2008
- Signature Theory in Holographic Algorithms.with Jin-Yi. Cai, ISAAC 2008
- Holographic Algorithms by Fibonacci Gates and Holographic Reductions for Hardness, with Jin-Yi Cai and Mingji Xia, FOCS 2008
- An Improved Randomized Truthful Mechanism for Scheduling Unrelated Machines, with Changyuan Yu, STACS 2008
- Holographic Algorithms with Unsymmetric Signatures, with Jin-Yi Cai, SODA 2008
- On Block-wise Symmetric Signatures for Matchgates.with Jin-Yi Cai, FCT 2007
- Holographic Algorithms: The Power of Dimensionality Resolved.with Jin-Yi Cai, ICALP 2007. (Best Paper Award of track A.)
- Holographic Algorithms: From Art to Science. with Jin-Yi Cai, STOC 2007
- Bases Collapse in Holographic Algorithms.with Jin-Yi Cai, CCC 2007
- On the Theory of Matchgate Computations.with Jin-Yi Cai and VinayChoudhary, CCC 2007
- On Symmetric Signatures in Holographic Algorithms.with Jin-Yi Cai, STACS 2007
- Truthful Auctions with Optimal Profit. with Shang-HuaTeng and Changyuan Yu, WINE 2006
- Simulating Undirectedst-Connectivity Algorithms on Uniform JAGs and NNJAGs. With jialinzhang, Chung Keung Poon, Jin-Yi Cai, ISAAC 2005