Penghui Yao

According to our database, Penghui Yao authored at least 39 papers between 2010 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2024

Quantum and Classical Communication Complexity of Permutation-Invariant Functions.

Ziyi Guan, Yunqi Huang, Penghui Yao, Zekun Ye

Proceedings of the 41st International Symposium on Theoretical Aspects of Computer Science, 2024

2023

The Computational Advantage of MIP* Vanishes in the Presence of Noise.

Yangjing Dong, Honghao Fu, Anand Natarajan, Minglong Qin, Haochen Xu, Penghui Yao

CoRR, 2023

Communication Complexity of Common Randomness Generation with Isotropic States.

Yangjing Dong, Penghui Yao

CoRR, 2023

A Cryptographic Perspective on the Verifiability of Quantum Advantage.

Nai-Hui Chia, Honghao Fu, Fang Song, Penghui Yao

CoRR, 2023

Quantum Pseudorandom Scramblers.

Chuhan Lu, Minglong Qin, Fang Song, Penghui Yao, Mingnan Zhao

CoRR, 2023

Nearly Optimal Algorithms for Testing and Learning Quantum Junta Channels.

Zongbo Bao, Penghui Yao

CoRR, 2023

The Generations of Classical Correlations via Quantum Schemes.

Zhenyu Chen, Lijinzhi Lin, Xiaodie Lin, Zhaohui Wei, Penghui Yao

CoRR, 2023

On the Fine-Grained Query Complexity of Symmetric Functions.

Supartha Podder, Penghui Yao, Zekun Ye

Proceedings of the 34th International Symposium on Algorithms and Computation, 2023

Decidability of Fully Quantum Nonlocal Games with Noisy Maximally Entangled States.

Minglong Qin, Penghui Yao

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

On Testing and Learning Quantum Junta Channels.

Zongbo Bao, Penghui Yao

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

2022

Quantum and Classical Hybrid Generations for Classical Correlations.

Xiaodie Lin, Zhaohui Wei, Penghui Yao

IEEE Trans. Inf. Theory, 2022

Complexity of Eccentricities and All-Pairs Shortest Paths in the Quantum CONGEST Model.

ChengSheng Wang, Xudong Wu, Penghui Yao

CoRR, 2022

Positive spectrahedra: invariance principles and pseudorandom generators.

Srinivasan Arunachalam, Penghui Yao

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Quantum Complexity of Weighted Diameter and Radius in CONGEST Networks.

Xudong Wu, Penghui Yao

Proceedings of the PODC '22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25, 2022

Polynomial-Time Approximation of Zero-Free Partition Functions.

Penghui Yao, Yitong Yin, Xinyuan Zhang

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

2021

Capacity Approaching Coding for Low Noise Interactive Quantum Communication Part I: Large Alphabets.

Debbie W. Leung, Ashwin Nayak, Ala Shayeghi, Dave Touchette, Penghui Yao, Nengkun Yu

IEEE Trans. Inf. Theory, 2021

Nonlocal Games with Noisy Maximally Entangled States are Decidable.

Minglong Qin, Penghui Yao

SIAM J. Comput., 2021

Positive spectrahedrons: Geometric properties, Invariance principles and Pseudorandom generators.

Srinivasan Arunachalam, Penghui Yao

Electron. Colloquium Comput. Complex., 2021

On the Gaussian surface area of spectrahedra.

Srinivasan Arunachalam, Oded Regev, Penghui Yao

Electron. Colloquium Comput. Complex., 2021

2020

On the Compression of Messages in the Multi-Party Setting.

Anurag Anshu, Penghui Yao

IEEE Trans. Inf. Theory, 2020

2019

A doubly exponential upper bound on noisy EPR states for binary games.

Penghui Yao

CoRR, 2019

Quantum Insertion-Deletion Channels.

Janet Leahy, Dave Touchette, Penghui Yao

CoRR, 2019

2018

Expected Communication Cost of Distributed Quantum Tasks.

Anurag Anshu, Ankit Garg, Aram W. Harrow, Penghui Yao

IEEE Trans. Inf. Theory, 2018

Capacity approaching coding for low noise interactive quantum communication.

Debbie W. Leung, Ashwin Nayak, Ala Shayeghi, Dave Touchette, Penghui Yao, Nengkun Yu

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

2017

Raz-McKenzie simulation with the inner product gadget.

Xiaodi Wu, Penghui Yao, Henry S. Yuen

Electron. Colloquium Comput. Complex., 2017

Multipartite Quantum Correlation and Communication Complexities.

Rahul Jain, Zhaohui Wei, Penghui Yao, Shengyu Zhang

Comput. Complex., 2017

Exponential separation of quantum communication and classical information.

Anurag Anshu, Dave Touchette, Penghui Yao, Nengkun Yu

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

2016

New One Shot Quantum Protocols With Application to Communication Complexity.

Anurag Anshu, Rahul Jain, Priyanka Mukhopadhyay, Ala Shayeghi, Penghui Yao

IEEE Trans. Inf. Theory, 2016

Parity Decision Tree Complexity and 4-Party Communication Complexity of XOR-functions Are Polynomially Equivalent.

Penghui Yao

Chic. J. Theor. Comput. Sci., 2016

A Direct Product Theorem for Two-Party Bounded-Round Public-Coin Communication Complexity.

Rahul Jain, Attila Pereszlényi, Penghui Yao

Algorithmica, 2016

Lower Bound on Expected Communication Cost of Quantum Huffman Coding.

Anurag Anshu, Ankit Garg, Aram W. Harrow, Penghui Yao

Proceedings of the 11th Conference on the Theory of Quantum Computation, 2016

2014

Approximate and Multipartite Quantum Correlation (Communication) Complexity.

Rahul Jain, Zhaohui Wei, Penghui Yao, Shengyu Zhang

CoRR, 2014

A new operational interpretation of relative entropy and trace distance between quantum states.

Anurag Anshu, Rahul Jain, Priyanka Mukhopadhyay, Ala Shayeghi, Penghui Yao

CoRR, 2014

A Parallel Repetition Theorem for Entangled Two-Player One-Round Games under Product Distributions.

Rahul Jain, Attila Pereszlényi, Penghui Yao

Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

2012

A strong direct product theorem in terms of the smooth rectangle bound

Rahul Jain, Penghui Yao

CoRR, 2012

A parallel approximation algorithm for mixed packing and covering semidefinite programs

Rahul Jain, Penghui Yao

CoRR, 2012

A direct product theorem for bounded-round public-coin randomized communication complexity

Rahul Jain, Attila Pereszlényi, Penghui Yao

CoRR, 2012

2011

A Parallel Approximation Algorithm for Positive Semidefinite Programming.

Rahul Jain, Penghui Yao

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010

Adversary lower bounds for nonadaptive quantum algorithms.

Pascal Koiran, Jürgen Landes, Natacha Portier, Penghui Yao

J. Comput. Syst. Sci., 2010