Publications
My previous research primarily focuses on developing new techniques for proving lower bounds in communication complexity, motivated by challenges in cryptography, quantum advantage, and circuit lower bounds.
Guangxu Yang, Jiapeng Zhang
In this paper, we propose a novel lifting framework connecting two-party communication with the Numbers-on-Forehead (NOF) communication model. At present, we establish a deterministic lifting theorem that translates one-way two-party lower bounds into the one-way NOF setting.
Our NOF lifting framework resolves two fundamental open problems:
- An optimal explicit separation between randomized and deterministic one-way NOF communication.
- The first exponential separation between quantum and randomized one-way NOF communication.
Proving strong lower bounds in one-way NOF communication remains highly challenging. Strong deterministic one-way NOF lower bounds will imply \(\mathrm{ACC}^0\) circuit lower bounds [HG91, BT94] and lower bounds for well-known problems in additive combinatorics [LPS17].
Guangxu Yang, Jiapeng Zhang
56th Annual ACM Symposium on Theory of Computing
In this paper, we propose a gadgetless lifting framework that extends query-to-communication lifting techniques to the gadgetless setting.
We further develop this framework or idea to resolve some open problems in communication complexity such as Collision Finding (STOC 2024), Pointer Chasing (ITCS 2025), Key Agreement (TCC 2023), Set Intersection (CCC 2025) and Classical-Quantum Trade-off (arXiv 2025) which have broad applications in areas including cryptography, proof complexity, and streaming lower bounds.
The gadgetless lifting framework has also been adopted by other works, such as [GGJL25] (STOC 2025), [BW25] (ICALP 2025) and [RSSY25] (RANDOM 2025).