Showing cs.CCShow all
3 papers · 1 filter
cs.CC2025
A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity
Xudong Wu, Guangxu Yang, Penghui Yao
We investigates a model of hybrid classical-quantum communication complexity, in which two parties first exchange classical messages and subsequently communicate using quantum mess…
cs.CC2024
Quantum and Classical Communication Complexity of Permutation-Invariant Functions
Ziyi Guan, Yunqi Huang, Penghui Yao +1
This paper gives a nearly tight characterization of the quantum communication complexity of the permutation-invariant Boolean functions. With such a characterization, we show that…
cs.CC2023
On the Fine-Grained Query Complexity of Symmetric Functions
Supartha Podder, Penghui Yao, Zekun Ye
This paper explores a fine-grained version of the Watrous conjecture, including the randomized and quantum algorithms with success probabilities arbitrarily close to . Our con…