My previous research primarily focused on developing new techniques in communication complexity, motivated by challenges in quantum advantage, cryptography, and circuit lower bounds.
In this paper, we give the first exponential explicit separation between quantum and randomized one-way NOF communication, which resolves the open problem proposed by [GP08]. Our proof introduces a new analytical framework combining lifting techniques and information complexity.
In this paper, we propose a novel lifting framework connecting two-party communication with the Numbers-on-Forehead communication model. At present, we establish a deterministic lifting theorem that translates one-way two-party lower bounds into the one-way NOF setting. By our NOF lifting theorem, we get an \(\Omega(\frac{n}{2^k})\) vs \(O(1)\) explicit separation between deterministic 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], size-depth trade-offs of circuits [Valiant77], and lower bounds for well-known problems in additive combinatorics [LPS17].
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).