Preprints and Publications
A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity [arxiv]
Xudong Wu, Guangxu Yang, Penghui YaoLinear-Size QAC0 Channels: Learning, Testing and Hardness [arxiv]
Yangjing Dong, Fengning Ou, Penghui YaoNonlocal Games and Self-tests in the Presence of Noise [arxiv]
Honghao Fu, Minglong Qin, Haochen Xu, Penghui YaoEfficient Non-Adaptive Quantum Algorithms for Tolerant Junta Testing [arxiv]
Zongbo Bao, Yuxuan Liu, Penghui Yao, Zekun Ye, Jialin Zhang
SOSA 2026, QIP 2026Optimal quantum sampling on distributed databases [arxiv]
Longyun Chen,Jingcheng Liu, Penghui Yao
SPAA 2025Experimental Efficient Influence Sampling of Quantum Processes [arxiv]
(by contribution) *Hao Zhan, *Zongbo Bao, Zekun Ye, Qianyi Wang, Minghao Mi, #Penghui Yao, #Lijian ZhangParallel Kac's Walk Generates PRU [arxiv]
Chuhan Lu, Minglong Qin, Fang Song, Penghui Yao, Mingnan ZhaoA Pseudorandom Generator for Functions of Low-Degree Polynomial Threshold Functions [arxiv]
Penghui Yao, Mingnan Zhao
ICALP 2025Distributed Quantum Simulation [arxiv]
(by contribution) Tianfeng Feng, Jue Xu, Wenjun Yu, Zekun Ye, #Penghui Yao, #Qi ZhaoOn the Computational Power of QAC0 with Barely Superlinear Ancillae [arxiv]
Anurag Anshu, Yangjing Dong, Fengning Ou, Penghui Yao
QIP 2025, STOC 2025Almost Optimal Algorithms for Token Collision in Anonymous Networks [arxiv]
Sirui Bai, Xinyu Fu, Xudong Wu, Penghui Yao, Chaodong Zheng
DISC 2024The Computational Advantage of MIP* Vanishes in the Presence of Noise [arxiv]
Yangjing Dong, Honghao Fu, Anand Natarajan, Minglong Qin, Haochen Xu, Penghui Yao
CCC 2024,QIP 2025,Journal of the ACM 2025Hypercontractivity for Quantum Erasure Channels via Multipartite Log-Sobolev Inequality [arxiv]
Zongbo Bao, Yangjing Dong, Fengning Ou, Penghui Yao
IEEE Transactions on Information Theory 2025Communication Complexity of Common Randomness Generation with Isotropic States [arxiv]
Yangjing Dong, Penghui Yao
IEEE Transactions on Information Theory 2024A Cryptographic Perspective on the Verifiability of Quantum Advantage [arxiv]
Nai-Hui Chia, Honghao Fu, Fang Song, Penghui Yao
AQIS 2024, ACM Transactions on Quantum Computing 2025The Generations of Classical Correlations via Quantum Schemes [arxiv]
Zhenyu Chen, Lijinzhi Lin, Xiaodie Lin, Zhaohui Wei, Penghui Yao
IEEE Transactions on Information Theory 2024Quantum and Classical Communication Complexity of Permutation-Invariant Functions [arxiv]
Ziyi Guan, Yunqi Huang, Penghui Yao, Zekun Ye
STACS 2024, IEEE Transactions on Information Theory 2025Quantum Pseudorandom Scramblers [arxiv]
Chuhan Lu, Minglong Qin, Fang Song, Penghui Yao, Mingnan Zhao
QIP 2024,TCC 2024On the Fine-Grained Query Complexity of Symmetric Functions [arxiv]
Supartha Podder, Penghui Yao, Zekun Ye
ISAAC 2023, Computational Complexity 2025On Testing and Learning Quantum Junta Channels [arxiv]
Zongbo Bao, Penghui Yao
COLT 2023, Transactions on Pattern Analysis and Machine Intelligence 2025Decidability of fully quantum nonlocal games with noisy maximally entangled states [arxiv]
Minglong Qin, Penghui Yao
QIP 2023, ICALP 2023, Algorithmica 2025Quantum Complexity of Weighted Diameter and Radius in CONGEST Networks [arxiv]
Xudong Wu, Penghui Yao
PODC 2022Polynomial-Time Approximation of Zero-Free Partition Functions [arxiv]
Penghui Yao, Yitong Yin, Xinyuan Zhang
ICALP 2022On the Gaussian surface area of spectrahedra [arxiv]
Srinivasan Arunachalam, Oded Regev, Penghui Yao
Geometric Aspects of Functional Analysis: Israel Seminar (GAFA) 2022Nonlocal games with noisy maximally entangled states are decidable [arxiv], supercedes [arxiv]
Minglong Qin, Penghui Yao
SIAM Journal on Computing 2021Complexity of Eccentricities and All-Pairs Shortest Paths in the Quantum CONGEST Model [arxiv]
Changsheng Wang, Xudong Wu, Penghui Yao
SPIN 2021Quantum and Classical Hybrid Generations for Classical Correlations [arxiv]
Xiaodie Lin, Zhaohui Wei, Penghui Yao
IEEE Transactions on Information Theory 2022Quantum verification of NP problems with single photons and linear optics [arxiv]
(by contribution) Aonan Zhang, Hao Zhan, Junjie Liao, Kaimin Zheng, Tao Jiang, Minghao Mi, #Penghui Yao, #Lijian Zhang
Light: Science & Applications 2020Positive spectrahedrons: Geometric properties, Invariance principles and Pseudorandom generators [arxiv]
Srinivasan Arunachalam, Penghui Yao
STOC 2022On the Compression of messages in the Multi-Party setting [arxiv]
Anurag Anshu, Penghui Yao
IEEE Transactions on Information Theory 2020A doubly exponential upper bound on noisy EPR states for binary games [arxiv](it is superceded by [arxiv])
Penghui Yao
QIP 2020Quantum Insertion-Deletion Channels [arxiv]
Janet Leahy, Dave Touchette, Penghui YaoRaz-McKenzie simulation with the inner product gadget [ECCC]
Xiaodi Wu, Penghui Yao, Henry YuenExpected communication cost of distributed quantum tasks [arxiv]
Anurag Anshu, Ankit Garg, Aram Harrow, Penghui Yao.
IEEE Transactions on Information Theory 2018Capacity approaching coding for low noise interactive quantum communication [arxiv]
Debbie Leung, Ashwin Nayak, Ala Shayeghi, Dave Touchette, Penghui Yao, Nengkun Yu
IEEE Transactions on Information Theory 2021. Extended abstract appeared in STOC 2018Exponential separation of quantum communication and classical information [arxiv]
Anurag Anshu, Dave Touchette, Penghui Yao, Nengkun Yu
STOC 2017, plenary talk QIP 2017Multipartite quantum correlation and communication complexities [arxiv]
Rahul Jain, Zhaohui Wei, Penghui Yao, Shengyu Zhang
Computational Complexity 2016New one shot quantum protocols with application to communication complexity [arxiv]
Anurag Anshu, Rahul Jain, Priyanka Mukhopadhyay, Ala Shayeghi, Penghui Yao
IEEE Transactions on Information Theory 2016Parity Decision Tree Complexity and 4-Party Communication Complexity of XOR-functions Are Polynomially Equivalent [arxiv]
Penghui Yao
Chicago Journal of Theoretical Computer Science 2016Lower bound on expected communication cost of quantum Huffman coding [arxiv]
Anurag Anshu, Ankit Garg, Aram Harrow, Penghui Yao
TQC 2016A parallel repetition theorem for entangled two-player one-round games under product distributions [arxiv]
Rahul Jain, Attila Pereszlényi, Penghui Yao.
CCC 2014A direct product theorem for two-party bounded-round public-coin commuinication complexity [arxiv]
Rahul Jain, Attila Pereszlényi, Penghui Yao
FOCS 2012, special issue in AlgorithmicaA parallel approximation algorithm for positive semidefinite programming [arxiv]
Rahul Jain, Penghui Yao
FOCS 2011Adversary Lower Bounds for Nonadaptive Quantum Algorithms [arxiv]
Pascal Koiran, Jürgen Landes, Natacha Portier, Penghui Yao
WoLLIC 2008, special issue in Journal of Computer and System Sciences