Penghui Yao's homepage
Contact
- Email: phyao1985#gmail.com
- Office: Room #502 Department of Computer Science and Technology, Xianlin Campus of Nanjing University
Short Bio
I am an associate professor in the Theory Group of the Department of Computer Science and Technology at Nanjing University. I am a member of CS Theory group.
I obtained Bsc. from East China Normal University majored in mathematics and Ph.D. degree from Centre for Quantum Technologies, National University of Singapore fortunately supervised by Rahul Jain and Miklos Santha. Prior to joining Nanjing University, I was a postdoctoral researcher at Centrum Wiskunde Informatica(CWI), then Institute for Quantum Computing (IQC) at University of Waterloo, then Hartree postdoctoral research fellow at Joint center for Quantum Information and Computer Science (QuICS), University of Maryland. My full cv is here.
Research interest
I am interested in all applications of information theory and Fourier analysis in quantum computing and complexity theory. More specifically,Quantum computational complexity
Communication complexity and information complexity
Fourier analysis in theoretical computer science and quantum computation
Derandomization
Current students
Minglong Qin (Ph.D., 2019.4- )
Mingnan Zhao (Ph.D., 2020.9- )
Xudong Wu (Ph.D. coadvised with Yitong Yin, 2020.9-)
Yangjing Dong (Ph.D. 2021.9-)
Zekun Ye (Ph.D., 2021.9-)
Zongbo Bao (Msc. 2021.9- )
Haigang Zhou (Ph.D., 2023.9 -)
Alumni
Changsheng Wang (MSc., 2020.9-2023.7) Now Microsoft (Suzhou)
Interns
We have a few intern positions on TCS/quantum computing . Please drop me an email if you are interested.2020.9-2021.1: Tingjia Cao (Bsc. Fudan University, now Ph.D. University of Wisconsin-Madison)
2020.12-2021.7: Ziyi Guan (Bsc. CMU, now Ph.D. EPFL)
2020.12-2022.1 : Yunqi Huang (Bsc. Sun Yat-sen University, now Ph.D. University of Technology, Sydney)
2023.9- : Yizhou Yan (Bsc. Southern University of Science and Technology)
Services
Program Committee: QIP 2019, TQC 2021, TQC 2022, QIP 2023 QIP 2024
Students Travel Awards Commitee: Program Committees: QIP 2022
Preprints
- Quantum Pseudorandom Scramblers [arxiv]
Chuhan Lu, Minglong Qin, Fang Song, Penghui Yao, Mingnan Zhao The Generations of Classical Correlations via Quantum Schemes [arxiv]
Zhenyu Chen, Lijinzhi Lin, Xiaodie Lin, Zhaohui Wei, Penghui YaoQuantum Insertion-Deletion Channels Covers [arxiv]
Janet Leahy, Dave Touchette, Penghui YaoRaz-McKenzie simulation with the inner product gadget [ECCC]
Xiaodi Wu, Penghui Yao, Henry Yuen
Publications
On 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
To appear GAFA Seminar NotesNonlocal 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 2020Expected 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
Resources
A collection of references that I think may be useful for the students and researchers who are interested in the theory aspect of quantum information and quantum computation.The Theory of Quantum Information by John Watrous.
Lecture Notes on Quantum Algorithms by Andrew Childs.
Quantum Computing: Lecture Notes by Ronald de Wolf.
Quantum Computation and Quantum Information by Michael Nielsen and Isaac Chuang.