Preprints and Publications
On the Computational Power of QAC0 with Barely Superlinear Ancillae [arxiv]
Anurag Anshu, Yangjing Dong, Fengning Ou, Penghui YaoAlmost 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 2024Hypercontractivity for Quantum Erasure Channels via Multipartite Log-Sobolev Inequality [arxiv]
Zongbo Bao, Yangjing Dong, Fengning Ou, Penghui YaoCommunication Complexity of Common Randomness Generation with Isotropic States [arxiv]
Yangjing Dong, Penghui Yao
IEEE Transactions on Information Theory 2024-
A Cryptographic Perspective on the Verifiability of Quantum Advantage [arxiv]
Nai-Hui Chia, Honghao Fu, Fang Song, Penghui Yao
AQIS 2024 The 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 2024Quantum 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 2023On Testing and Learning Quantum Junta Channels [arxiv]
Zongbo Bao, Penghui Yao
COLT 2023Decidability of fully quantum nonlocal games with noisy maximally entangled states [arxiv]
Minglong Qin, Penghui Yao
QIP 2023, ICALP 2023Quantum 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 of 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 Covers [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