Qian Li

Qian Li



Dr. Qian Li is now a research scientist in Shenzhen Institute of Computing Sciences. Prior to SICS, he was a senior software engineer in Alibaba group focusing on mechanism design for online advertising. He did his PhD at the Institute of Computing Technology, Chinese Academy of Sciences, where he had Xiaoming Sun as his adviser. Prior to that, he received his bachelor’s degree in integrated circuit design from Chongqing University. He has a broad interest in theoretical computer science, in particular parallel computing, computational complexity, quantum computing, algorithmic Lovasz Local Lemma, and Boolean function analysis.

Research Interests

  • Parallel Computing
  • Computational Complexity
  • Quantum Computation
  • Algorithmic Lovasz Local Lemma
  • Boolean Function Analysis


  • Wenfei Fan, Kun He, Qian Li, and Yue Wang: Graph Algorithms: Parallelization and Scalability. SCIENCE CHINA Information Sciences (SCIS) (invited), 2020.
  • Zhihuai Chen, Qian Li, Xiaoming Sun, Lirong Xia, and Jialin Zhang: Approximate Single-Peakedness in Large Elections. IEEE International Conference on Knowledge Graph (ICKG 2020),  2020, Nanjing, China: 433-440.
  • Qian Li, Xiaoming Sun, Jialin Zhang:On the Optimality of Tape Merge of Two Lists with Similar Size. Algorithmica 82(7): 2107-2132 (2020).
  • Kun HeQian Li, Xiaoming Sun:Quantum Lovász Local Lemma: Shearer’s Bound Is Tight . ACM Symposium on the Theory of Computing(STOC 2019), Jun 23-26, 2019, Phoenix, Arizona, USA :461-472

Current Project

  • On the Impossibility of Parallel Computing

A variety of parallel computation frameworks are built to carry out computations on large-scale graphs, and many efficient algorithms are proposed for these frameworks. However, much fewer papers study the limitations of these frameworks, and lots of related problems remain open. In this project, instead of looking for a faithful model for the system du jour, we investigate limitations of two general and abstract parallel computation models, namely Bulk Synchronous Parallel Computing Model (BSP model) and Congested Bulk Synchronous Parallel Computing Model (Congested BSP model), which capture the most fundamental constraints shared by most common-used models.