1 citations · 1 across the 8 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2025
Deterministic Lifting Theorems for One-Way Number-on-Forehead Communication
Guangxu Yang, Jiapeng Zhang
Lifting theorems are one of the most powerful tools for proving communication lower bounds, with numerous downstream applications in proof complexity, monotone circuit lower bounds…
cs.CC2024
Gadgetless Lifting Beats Round Elimination: Improved Lower Bounds for Pointer Chasing
Xinyu Mao, Guangxu Yang, Jiapeng Zhang
We prove an Ω(n/k+k) communication lower bound on (k-1)-round distributional complexity of the k-step pointer chasing problem under uniform input distribution, improving the Ω(n/k…
cs.CC2023★ 1 cited
Lifting Theorems Meet Information Complexity: Known and New Lower Bounds of Set-disjointness
Guangxu Yang, Jiapeng Zhang
Set-disjointness problems are one of the most fundamental problems in communication complexity and have been extensively studied in past decades. Given its importance, many lower b…