Pinyan Lu (陆品燕） 

Pinyan Lu is an Associate Researcher at Theory Group of Microsoft Research Asia.  He studied in Tsinghua University (BS (2005) and PhD (2009) both in Computer Science). His advisor was Prof. Andrew C. Yao, and he was also co-supervised by Prof. Jin-Yi Cai at University of Wisconsin-Madison.  He is mainly interested in complexity theory, algorithms design and algorithmic game theory.

I'm organizing weekly theory seminars at MSRA. You are welcome to attend and/or give talks.

Current and Past Intern Students:

• Zeyuan Zhu (Tsinghua University)

• Sangxia Huang (Shanghai Jiaotong University)

• Lei Wang (Georgia Institute of Technology )

• Yuan Zhou  (Carnegie Mellon University)

If you are interested in working with me as an intern student, please send me your CV.

Publications:

 My DBLP Site

1. On 2-Player Randomized Mechanisms for Scheduling. to appear in WINE 2009.
2. Tighter Bounds for Facility Games. with Yajun Wang and Yuan Zhou, to appear in WINE 2009.
3. Holant Problems and Counting CSP. with Jin-Yi Cai and Mingji Xia, STOC 2009.
4. A Computational Proof of Complexity of Some Restricted Counting Problems. with Jin-Yi Cai and Mingji Xia, TAMC 2009.
5. Worst-Case Nash Equilibria in Restricted Routing. With Changyuan Yu, WINE 2008.
6. Randomized Truthful Mechanisms for Scheduling Unrelated Machines. With Changyuan Yu, WINE 2008.
7. Signature Theory in Holographic Algorithms. with Jin-Yi. Cai, ISAAC 2008.
8. Holographic Algorithms by Fibonacci Gates and Holographic Reductions for Hardness, with Jin-Yi Cai and Mingji Xia, FOCS 2008.
9. An Improved Randomized Truthful Mechanism for Scheduling Unrelated Machines, with Changyuan Yu, STACS 2008.
10. Holographic Algorithms with Unsymmetric Signatures, with Jin-Yi Cai, SODA 2008.
11. On Block-wise Symmetric Signatures for Matchgates. with Jin-Yi Cai, FCT 2007.
12. Holographic Algorithms: The Power of Dimensionality Resolved. with Jin-Yi Cai, ICALP 2007. (Best Paper Award of track A.)
13. Holographic Algorithms: From Art to Science. with Jin-Yi Cai, STOC 2007.
14. Bases Collapse in Holographic Algorithms. with Jin-Yi Cai, CCC 2007.
15. On the Theory of Matchgate Computations. with Jin-Yi Cai and Vinay Choudhary, CCC 2007.
16. On Symmetric Signatures in Holographic Algorithms. with Jin-Yi Cai, STACS 2007.
17. Truthful Auctions with Optimal Profit. with Shang-Hua Teng and Changyuan Yu, WINE 2006.
18. Simulating Undirected st-Connectivity Algorithms on Uniform JAGs and NNJAGs. With jialin zhang, Chung Keung Poon, Jin-Yi Cai, ISAAC 2005.