Pinyan Lu (陆品燕)
School of Information Management and Engineering
Shanghai University of Finance and Economics
No.100 Wudong Road
Yangpu District, Shanghai, China
Dr. Pinyan Lu is a professor and the founding director of Institute for Theoretical Computer Science at Shanghai University of Finance and Economics (ITCS@SUFE). Before joining SUFE, he was a researcher at Microsoft Research. 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

ITCS@SUFE is hiring:

The Institute for Theoretical Computer Science (ITCS) is a newly established academic unit at Shanghai University of Finance and Economics (SUFE), aimed at creating a world-class environment for research of theoretical computer science in broad sense. Positions at Assistant/Associate/Full Professor levels are available. We also have two regular post-doc positions each year. If you are interested in these positions, please send me your CV.

Program Committee:

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

Current and Past PhD Student:

  • Chihao Zhang (Shanghai Jiao Tong University,now at The Chinese University of Hong Kong)
  • Tao Xiao(Shanghai Jiao Tong University, co-advised with Xiaotie Deng)
  • Chao Liao (Shanghai Jiao Tong University)

Past Intern Students at MSRA:

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

  • FPTAS for Counting Proper Four Colorings on Cubic Graphs. with Kuan Yang ,Chihao Zhang,and Minshen Zhu, SODA 2017.
  • FPTAS for Hardcore and Ising Models on Hypergraphs. with Kuan Yang and Chihao Zhang, STACS 2016.
  • Uniqueness, Spatial Mixing, and Approximation for Ferromagnetic 2-Spin Systems. with Heng Guo, RANDOM 2016.
  • 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.


  • Combinatorial Multi-Armed Bandit with General Reward Functions. with Wei Chen, Wei Hu,Fu Li ,Jian Li,Yu Liu, NIPS 2016.
  • 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.