Guangxu Yang 杨广绪
“What I cannot create, I do not understand.”
I am a Ph.D. student in Computer Science at the University of Southern California, very fortunate to be advised by Prof. Jiapeng Zhang.
My research focused on developing new techniques in communication complexity, motivated by challenges in quantum computing, cryptography, and circuit lower bounds:
- Lifting Theorems for Numbers-on-Forehead Communication:We propose a novel lifting framework connecting two-party communication with the Numbers-on-Forehead (NOF) model. Using this framework, we establish the first exponential separation between quantum and randomized communication complexity in the one-way NOF setting, and achieve optimal separations between deterministic and randomized one-way NOF communication complexity.
- Gadgetless Lifting: We introduce a gadgetless lifting framework that extends query-to-communication lifting techniques to the gadgetless setting, resolving several open problems related to Collision Finding, Pointer Chasing, Set Intersection, and Key Agreement.
Publications & Manuscripts
Exponential Separation of Quantum and Classical One-Way Numbers-on-Forehead Communication
A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity
Deterministic Lifting Theorems for One-Way Numbers-on-Forehead Communication
A Min-Entropy Approach to Multi-Party Communication Lower Bounds
40th Computational Complexity Conference (CCC 2025)
Gadgetless Lifting Beats Round Elimination: Improved Lower Bounds for Pointer Chasing
16th Innovations in Theoretical Computer Science (ITCS 2025)
Communication Lower Bounds for Collision Problems via Density Increment Arguments
56th Annual ACM Symposium on Theory of Computing (STOC 2024)
Communication Lower Bounds of Key-Agreement Protocols via Density Increment Arguments
21st Theory of Cryptography Conference (TCC 2023)
Simulation Methods in Communication Lower Bounds, Revisited