Research: 

(*denotes equal contribution, (α-β) denotes alphabetical author order) 

• Position: Transformers Have the Potential to Achieve AGI

Qian Li, Ziniu Li, Tian Ding, and Ruoyu Sun

Manuscript

• Constant Bit-size Transformers are Turing Complete

Qian Li, and Yuyi Wang

Manuscript

• Cryptomania vs Minicrypt in a Quantum World

Longcheng Li, Qian Li, Xingjian Li, and Qipeng Liu (α-β)

Manuscript

• Multi-pass Memory Lower Bounds for Learning Problems

Qian Li, Shuo Wang, Jiapeng Zhang

To appear in the 38th Conference on Learning Theory (COLT 2025)

• Towards Explaining the Power of Constant-depth Graph Neural Networks for Structured Linear Programming

Qian Li, Minghui Ouyang, Tian Ding, Yuyi Wang, Qingjiang Shi, and Ruoyu Sun

In the 13th International Conference on Learning Representations  (ICLR 2025)

• When GNNs Meet Symmetry in ILPs: An Orbit-based Feature Augmentation Approach

Qian Chen, Lei Li, Qian Li, Jianghua Wu, Akang Wang, Ruoyu Sun, Xiaodong Luo, Tsung-Hui Chang, Qingjiang Shi

In the 13th International Conference on Learning Representations  (ICLR 2025)

~Qingjiang_Shi1

• Toward the Impossibility of Perfect Complete Quantum PKE from OWFs 

Longcheng Li, Qian Li, Xingjian Li, and Qipeng Liu (α-β)

In the 16th Innovations in Theoretical Computer Science (ITCS 2025) 

• Real-time Seedless Post-processing for Quantum Random Number Generators  

Qian Li, and Hongyi Zhou

IET Quantum Communication, 2024. 

• On the Power of Small-size Graph Neural Networks for Linear Programming 

Qian Li*, Tian Ding*, Linxin Yang*, Minghui Ouyang, Qingjiang Shi, and Ruoyu Sun

In the 38th Annual Conference on Neural Information Processing Systems (NeurIPS 2024).

• A Simple Distributed Algorithm for Sparse Fractional Covering and Packing Problems

Qian Li, Minghui Ouyang, and Yuyi Wang (α-β)

In the 35th International Symposium on Algorithms and Computation (ISAAC 2024). 

• New Distinguishers for Negation-Limited Weak Pseudorandom Functions

Zhihuai Chen, Siyao Guo, Qian Li, Chengyu Lin, and Xiaoming Sun (α-β)

Theory of Computing, 2024.

• A Hybrid Algorithm for Quadratically Constrained Quadratic Optimization Problems

Hongyi Zhou, Sirui Peng, Qian Li, and Xiaoming Sun

Physica Scripta, 2024.

• Improved Real-Time Post-Processing for Quantum Random Number Generators

Qian Li, Xiaoming Sun, Xingjian Zhang, and Hongyi Zhou

Advanced Quantum Technologies, 2024.

• How (not) to Build Quantum PKE in Minicrypt

Longcheng Li, Qian Li, Xingjian Li, and Qipeng Liu (α-β)

In the 44th Annual International Cryptology Conference (CRYPTO 2024).

• A New Information Complexity Measure for Multi-pass Streaming with Applications

Mark Braverman, Sumegha Garg, Qian Li, Shuo Wang, David P. Woodruff, and Jiapeng Zhang (α-β)

In the 56th ACM Symposium on Theory of Computing (STOC 2024). 

• A Practical Multi- Objective Auction Design and Optimization Framework for Sponsored Search

Qian Li, Liang Wang, Lirong Xia, Wenxun Zheng, and Yuxuan Zhou

Operations Research Letters, 2023. 

The auction mechanism has been implemented and commercialized on Alibaba’s e-commerce platform. Experimental results conducted on large-scale real-world traffic demonstrated that the auction mechanism drove a 1% increase in revenue (about 1 billion CNY/year), a 6% increase in click-through rate, a 2% improvement in conversion rate, and a 7% increase in gross merchandise volume (>100 billion CNY/year).

• Fast Exact Synthesis of Two-qubit Unitaries Using Near Minimum Number of T Gates

Longcheng Li, Cheng Guo, Qian Li, and Xiaoming Sun

Physical Review A, 2023. 

• Optimal Synthesis of Multi-Controlled Qudit Gates

Wei Zi*, Qian Li*, and Xiaoming Sun 

In the 60th ACM/IEEE Design Automation Conference (DAC 2023). 

• Moser-Tardos Algorithm: Beyond Shearer's Bound

Kun He, Qian Li, and Xiaoming Sun (α-β)

In the ACM-SIAM Symposium on Discrete Algorithms (SODA 2023). 

• Unifying Presampling via Concentration Bounds

Siyao Guo, Qian Li, Qipeng Liu, and Jiapeng Zhang (α-β)

In the 19th Theory of Cryptography Conference (TCC 2021).

• Streaming Algorithms for Graph k-Matching with Optimal or Near-Optimal Update Time

Jianer Chen, Qin Huang, Iyad Kanj, Qian Li, and Ge Xia (α-β)

In the 32nd International Symposium on Algorithms and Computation (ISAAC 2021).

• On the Sensitivity Complexity of k-Uniform Hypergraph Properties

Qian Li, and Xiaoming Sun (α-β)

ACM Transaction on Computation Theory, 2021. Preliminary version in 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). 

• Approximate Single-Peakedness in Large Elections

Zhihuai Chen, Qian Li, Xiaoming Sun, Lirong Xia, and Jialin Zhang (α-β)

In the IEEE International Conference on Knowledge Graph (ICKG 2020).

• Graph Algorithms: Parallelization and Scalability

Wenfei Fan, Kun He, Qian Li, and Yue Wang

Science China Information Sciences, 2020.

• On the Module Degree Complexity of Boolean Functions

Qian Li, and Xiaoming Sun (α-β)

Theoretical Computer Science, 2020. Preliminary version in the 23rd International Conference on Computing and Combinatorics (COCOON 2017).

• On the Optimality of Tape Merge of Two Lists with Similar Size

Qian Li, Xiaoming Sun, and Jialin Zhang  (α-β)

Algorithmica, 2020. Preliminary version in the 27th International Symposium on Algorithms and Computation (ISAAC 2016).

• Quantum Lovasz Local Lemma: Shearer’s Bound is Tight

Kun He, Qian Li, Xiaoming Sun, and Jiapeng Zhang (α-β)

In the 51st ACM Symposium on Theory of Computing (STOC 2019). 

• A Tighter Relation between Sensitivity and Certificate Complexity

Kun He, Qian Li, and Xiaoming Sun (α-β)

Theoretical Computer Science, 2019. Preliminary version in the 23rd International Conference on Computing and Combinatorics (COCOON 2017).

• Efficient Delivery Policy to Minimize User Traffic Consumption in Guaranteed Advertising

Jia Zhang, Zheng Wang, Qian Li, Qiang Li, Xiaoming Sun, and Jialin Zhang

In the 31st AAAI Conference on Artificial Intelligence (AAAI 2017).