Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Pinyan Lu


Pinyan Lu (陆品燕) 

Lead Researcher
Microsoft Research Asia

Chair Professor
Shanghai Jiao Tong University


No 999, Zixing Road, Minhang District

Shanghai, 200241, China

 Phone: +86-10-5917-3005



Pinyan Lu is a Lead Researcher at Theory Group of Microsoft Research Asia. He is also a Chair Professor at Computer Science Department and Zhiyuan College of Shanghai Jiao Tong University. He studied in Tsinghua University (BS (2005) and PhD (2009) both in Computer Science).  He is interested in theoretical computer science, including complexity theory, algorithms design and algorithmic game theory. Currently, his research is mainly focused on complexity and approximability of counting problems, and algorithmic mechanism design.

My Curriculum Vitae

Program Committee:

FAW 2010, FAW-AAIM 2011, COCOON 2011, WINE 2011, CATS 2012, ICALP 2012, FAW-AAIM 2012 (PC co-Chair), TAMC 2013STOC 2013, ISAAC 2014, WINE 2014 (co-Chair for Poster track), ICALP 2015, FOCS 2015, ESA 2016

Research Opportunities:

I'm looking for self-motivated students with interest in theoretical computer science working with me either as intern student at Microsoft Research Asia or as PhD student at Shanghai Jiao Tong University. For PhD students, I will supervise him/her with the help from the whole Chair Professor Team. If you are interested, please send me your CV.

There are also researcher (faculty) positions openning for theoretical computer science in both Institutes (MSRA and SJTU), please contact me if you are interested.   

Current PhD Student:

Current and Past Intern Students:

Guangda HuZhang, Yumeng Zhang, Lingxiao Huang, Kuan Yang, Tao Xiao, Zhengyang Liu, Jingcheng Liu, Menghui Wang, Liang Li, Bo Tang, Xue Chen, Nick Gravin, Zeyuan Zhu, Sangxia Huang, Lei Wang, Yuan Zhou 


 My DBLP Site 

Approximate Counting

  • Canonical Paths for MCMC: from Art to Science. with Lingxiao Huang and Chihao Zhang, SODA 2016.
  • FPTAS for #BIS with Degree Bounds on One Side. with Jingcheng Liu, STOC 2015.
  • FPTAS for Counting Monotone CNF. with Jingcheng Liu, SODA 2015.  
  • FPTAS for Counting Weighted Edge Covers. with Jingcheng Liu and Chihao Zhang, ESA 2014.
  • The Complexity of Ferromagnetic Two-spin Systems with External Fields. with Jingcheng Liu and Chihao Zhang, RANDOM 2014.
  • FPTAS for Weighted Fibonacci Gates and Its Applications. with Menghui Wang and Chihao Zhang, ICALP 2014.
  • A Simple FPTAS for Counting Edge Covers. with Chengyu Lin and Jingcheng Liu, SODA 2014.  
  • Improved FPTAS for Multi-Spin Systems. with Yitong Yin, RANDOM 2013.
  • The Complexity of Approximating Conservative Counting CSPs. with Xi Chen, Martin Dyer, Leslie Ann Goldberg, Mark Jerrum, Colin McQuillan and David Richerby, STACS 2013.
  • Correlation Decay up to Uniqueness in Spin Systems. with Liang Li and Yitong Yin, SODA 2013.
  • Inapproximability After Uniqueness Phase Transition in Two-Spin Systems. with Jin-Yi Cai, Xi Chen and Heng Guo. COCOA 2012.
  • Approximate Counting via Correlation Decay in Spin Systems. with Liang Li and Yitong Yin, SODA 2012.

Complexity of Counting Problems

  • Dichotomy for Holant* Problems with a Function on Domain Size 3. with Jin-Yi Cai and Mingji Xia, SODA 2013.
  • A Dichotomy for Real Weighted Holant Problems. with Sangxia Huang, CCC 2012.
  • 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.
  • 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.
  • 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 Cai and Mingji Xia, TAMC 2009.

Algorithmic Game Theory

  • Improved Efficiency Guarantees in Auctions with Budgets. with Tao Xiao, EC 2015.
  • Competitive analysis via benchmark decomposition. with Ning Chen and Nick Gravin, EC 2015.
  • Optimal Competitive Auctions. with Ning Chen and Nick Gravin, STOC 2014.
  • Truthful Generalized Assignments via Stable Matching.  with Ning Chen and Nick Gravin, Mathematics of Operations Research, 2013.
  • Characterization of Truthful Mechanisms for One-dimensional Single Facility Location Game with Payments. with Lan Yu, WINE 2013.
  • Competitive Auctions for Markets with Positive Externalities. with Nick Gravin, ICALP 2013.
  • Budget Feasible Mechanism Design: From Prior-Free to Bayesian. with Xiaohui Bei, Ning Chen and Nick Gravin, STOC 2012.   
  • Computing the Nucleolus of Matching, Cover and Clique Games. with Ning Chen and Hongyang Zhang, AAAI 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.
  • On the Approximability of Budget Feasible Mechanisms. with Ning Chen and Nick Gravin, SODA 2011.  
  • Envy-free Pricing with General Supply Constraints. with Sungjin Im and Yajun Wang, WINE 2010.  
  • Asymptotically Optimal Strategy-Proof Mechanisms for Two-Facility Games. with Xiaorui 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.
  • Worst-Case Nash Equilibria in Restricted Routing. With Changyuan Yu, WINE 2008.
  • Randomized Truthful Mechanisms for Scheduling Unrelated Machines. With Changyuan Yu, WINE 2008.
  • An Improved Randomized Truthful Mechanism for Scheduling Unrelated Machines, with Changyuan Yu, STACS 2008.
  • Truthful Auctions with Optimal Profit. with Shang-Hua Teng and Changyuan Yu, WINE 2006.

Holographic Algorithms

  • Holographic Algorithms by Fibonacci Gates and Holographic Reductions for Hardness, with Jin-Yi Cai and Mingji Xia, FOCS 2008.
  • Holographic Algorithms with Unsymmetric Signatures, with Jin-Yi Cai, SODA 2008.
  • Signature Theory in Holographic Algorithms. with Jin-Yi. Cai, ISAAC 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)
  • 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 Vinay Choudhary, CCC 2007.
  • On Symmetric Signatures in Holographic Algorithms. with Jin-Yi Cai, STACS 2007.


  • On Optimal Differentially Private Mechanisms for Count-Range Queries. with
    Chen Zeng, Jin-Yi Cai, and Jeffrey Naughton, ICDT 2013.
  • Simulating Undirected st-Connectivity Algorithms on Uniform JAGs and NNJAGs. With jialin zhang, Chung Keung Poon, Jin-Yi Cai, ISAAC 2005.