4 citations · 12 across the 22 of their papers we have counts for
7 papers · 1 filter
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…
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…
A New Information Complexity Measure for Multi-pass Streaming with Applications
Mark Braverman, Sumegha Garg, Qian Li +3
We introduce a new notion of information complexity for multi-pass streaming problems and use it to resolve several important questions in data streams. In the coin problem, one se…
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…
Streaming Lower Bounds and Asymmetric Set-Disjointness
Shachar Lovett, Jiapeng Zhang
Frequency estimation in data streams is one of the classical problems in streaming algorithms. Following much research, there are now almost matching upper and lower bounds for the…
Decision list compression by mild random restrictions
Shachar Lovett, Kewen Wu, Jiapeng Zhang
A decision list is an ordered list of rules. Each rule is specified by a term, which is a conjunction of literals, and a value. Given an input, the output of a decision list is the…