Pinyan Lu (陆品燕) 

Pinyan Lu is a 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 monthly theory seminars at shanghai area. You are welcome to attend and/or give talks.

My Curriculum Vitae

Program Committee:

FAW 2010, FAW-AAIM 2011, COCOON 2011, WINE 2011, CATS 2012, ICALP 2012, FAW-AAIM 2012 (PC co-Chair)

Current and Past Intern Students:

• Liang Li (Peking University)

• Xue Chen (Tsinghua University)

• Nick Gravin  (Nanyang Technological University, Singapore)

• Zeyuan Zhu (MIT)

• Sangxia Huang (KTH)

• 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. Budget Feasible Mechanism Design: From Prior-Free to Bayesian. with Xiaohui Bei, Ning Chen and Nick Gravin, STOC 2012.  
2. A Dichotomy for Real Weighted Holant Problems. with Sangxia Huang, CCC 2012.
3. Computing the Nucleolus of Matching, Cover and Clique Games. with Ning Chen and Hongyang Zhang, AAAI 2012.
4. Approximate Counting via Correlation Decay in Spin Systems. with Liang Li and Yitong Yin, SODA 2012.
5. On the Approximation Ratio of k-lookahead Auction. with Xue Chen, Guangda Hu and Lei Wang, WINE 2011.
6. Optimal Pricing in Social Networks with Incomplete Information. with Wei Chen, Xiaorui Sun, Bo Tang, Yajun Wang and Zeyuan Allen Zhu, WINE 2011.
7. The Complexity of Symmetric Boolean Parity Holant Problems. with Heng Guo and Leslie Valiant, ICALP 2011.
8. Non-negative Weighted #CSPs: An Effective Complexity Dichotomy. with Jin-Yi Cai and Xi Chen, CCC 2011.
9. The Complexity of Weighted Boolean #CSP Modulo k. with Heng Guo, Sangxia Huang and Mingji Xia, STACS 2011.
10. Dichotomy for Holant^* Problems of Boolean Domain. with Jin-Yi Cai and Mingji Xia, SODA 2011.
11. On the Approximability of Budget Feasible Mechanisms. with Ning Chen and Nick Gravin, SODA 2011.  
12. Envy-free Pricing with General Supply Constraints. with Sungjin Im and Yajun Wang, WINE 2010.  
13. From Holant To #CSP And Back: Dichotomy For Holant^c Problems. with Jin-Yi Cai and Sangxia Huang, ISAAC 2010. (Best Paper Award.)
14. Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP. with Jin-Yi Cai and Mingji Xia, FOCS 2010.
15. On Tractable Exponential Sums. with Jin-Yi Cai, Xi Chen and Richard Lipton, FAW 2010. (Best Paper Award.)
16. Graph Homomorphisms with Complex Values: A Dichotomy Theorem. with Jin-Yi Cai and Xi Chen, ICALP 2010.
17. Asymptotically Optimal Strategy-Proof Mechanisms for Two-Facility Games. with Xiaorui Sun, Yajun Wang and Zeyuan Allen Zhu, EC 2010.
18. On 2-Player Randomized Mechanisms for Scheduling. WINE 2009.
19. Tighter Bounds for Facility Games. with Yajun Wang and Yuan Zhou, WINE 2009.
20. Holant Problems and Counting CSP. with Jin-Yi Cai and Mingji Xia, STOC 2009.
21. A Computational Proof of Complexity of Some Restricted Counting Problems. with Jin-Yi Cai and Mingji Xia, TAMC 2009.
22. Worst-Case Nash Equilibria in Restricted Routing. With Changyuan Yu, WINE 2008.
23. Randomized Truthful Mechanisms for Scheduling Unrelated Machines. With Changyuan Yu, WINE 2008.
24. Signature Theory in Holographic Algorithms. with Jin-Yi. Cai, ISAAC 2008.
25. Holographic Algorithms by Fibonacci Gates and Holographic Reductions for Hardness, with Jin-Yi Cai and Mingji Xia, FOCS 2008.
26. An Improved Randomized Truthful Mechanism for Scheduling Unrelated Machines, with Changyuan Yu, STACS 2008.
27. Holographic Algorithms with Unsymmetric Signatures, with Jin-Yi Cai, SODA 2008.
28. On Block-wise Symmetric Signatures for Matchgates. with Jin-Yi Cai, FCT 2007.
29. Holographic Algorithms: The Power of Dimensionality Resolved. with Jin-Yi Cai, ICALP 2007. (Best Paper Award of track A.)
30. Holographic Algorithms: From Art to Science. with Jin-Yi Cai, STOC 2007.
31. Bases Collapse in Holographic Algorithms. with Jin-Yi Cai, CCC 2007.
32. On the Theory of Matchgate Computations. with Jin-Yi Cai and Vinay Choudhary, CCC 2007.
33. On Symmetric Signatures in Holographic Algorithms. with Jin-Yi Cai, STACS 2007.
34. Truthful Auctions with Optimal Profit. with Shang-Hua Teng and Changyuan Yu, WINE 2006.
35. Simulating Undirected st-Connectivity Algorithms on Uniform JAGs and NNJAGs. With jialin zhang, Chung Keung Poon, Jin-Yi Cai, ISAAC 2005.