4 papers
Quantum versus Classical Separation in Simultaneous Number-on-Forehead Communication
Guangxu Yang, Jiapeng Zhang
Quantum versus classical separation plays a central role in understanding the advantages of quantum computation. In this paper, we present the first exponential separation between…
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…
PASTO: Strategic Parameter Optimization in Recommendation Systems -- Probabilistic is Better than Deterministic
Weicong Ding, Hanlin Tang, Jingshuo Feng +17
Real-world recommendation systems often consist of two phases. In the first phase, multiple predictive models produce the probability of different immediate user actions. In the se…