Pinyan Lu

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

Chinese Articles

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:

ISAAC 2019 (PC co-Chair), FAW 2018 (PC co-Chair), EC 2018, WINE 2017 (PC co-Chair), AAMAS 2017, ICALP 2017, FAW 2016, IJCAI 2016, WINE 2016, ESA 2016,ICALP 2015FOCS 2015,ISAAC 2014WINE 2014 (co-Chair for Poster track), TAMC 2013STOC 2013,CATS 2012ICALP 2012FAW-AAIM 2012 (PC co-Chair), FAW-AAIM 2011COCOON 2011WINE 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 HuangLei WangYuan Zhou 


  My DBLP Site 

Approximate Counting

  • Approximability of the eight-vertex model. with Jin-Yi Cai Tianyu Liu,and Jing Yu, CCC 2020.

  • Approximability of the Six-vertex Model. with Jin-Yi Cai and Tianyu Liu, SODA 2019.

  • Zeros of Holant problems: locations and algorithms. with Heng Guo, Chao Liao and Chihao Zhang, SODA 2019.

  • Counting hypergraph colourings in the local lemma regime. with Heng Guo ,Chao Liao,and Chihao Zhang, STOC 2018.

  • 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 Real Holant^c Problems. with Jin-Yi Cai and Mingji Xia, SODA 2018.

  • 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

  • Strategyproof Mechanism for Two Heterogeneous Facilities with Constant Approximation Ratio. with Minming Li, Yuhao Yao, and Jialin Zhang, IJCAI 2020.

  • Tight Approximation Ratio of Anonymous Pricing. with Yaonan Jin, Qi Qi, Zhihao Gavin Tang and Tao Xiao, STOC 2019.

  • Revenue Maximization with Imprecise Distribution. with Yingkai Li, and Haoran Ye, AAMAS 2019.

  • Correlation-Robust Analysis of Single Item Auction. with Xiaohui Bei, Nick Gravin and Zhihao Gavin Tang, SODA 2019.

  • Tight Revenue Gaps among Simple Mechanisms. with Yaonan Jin, Zhihao Gavin Tang and Tao Xiao, SODA 2019.

  • Facility Location Game with Fractional Preferences. with Ken C.K. Fong, Minming Li, Taiki Todo and Makoto Yokoo, AAAI 2018.

  • The Value of Information Concealment. with Hu Fu, Chris Liaw and Zhihao Gavin Tang, SODA 2018.

  • Separation in Correlation-Robust Monopolist Problem with Budget. with Nick Gravin, SODA 2018.

  • Liquid Welfare Maximization in Auctions with Multiple Items. with Tao Xiao, SAGT 2017.

  • 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.


  • Learning Plackett-Luce Mixtures from Partial Preferences. with Ao Liu, Zhibing Zhao, Chao Liao, Lirong Xia, AAAI 2019.

  • 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.