1 citations · 1 across the 9 of their papers we have counts for
10 papers
Quantum Communication Lower Bounds for Search Problems via Matrix Discrepancy
Minbo Gao, Chenghua Liu, Guangxu Yang +1
We study one-way quantum communication lower bounds for search problems. Unlike decision problems, search problems can have many valid outputs, which pose a fundamental barrier to…
Exponential Quantum Space Advantage for Approximating Max-SAT in the Streaming Setting
Haoyu Wang, Guangxu Yang
In this paper, we give a one-pass quantum streaming algorithm for Max-SAT that uses space and achieves a -approximation on instances with …
Prediction Under Imperfect Compression: A Theory of Approximate MDL
Qian Li, Xinyu Mao, Shang-Hua Teng +1
Minimum Description Length (MDL) formalizes the principle of Occam's razor by optimizing the total description length: . Fo…
Exponential Separation of Quantum and Classical One-Way Numbers-on-Forehead Communication
Guangxu Yang, Jiapeng Zhang
Numbers-on-Forehead (NOF) communication model is a central model in communication complexity. As a restricted variant, one-way NOF model is of particular interest. Establishing str…
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…
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…
Tackling Long-Tailed Category Distribution Under Domain Shifts
Xiao Gu, Yao Guo, Zeju Li +5
Machine learning models fail to perform well on real-world applications when 1) the category distribution P(Y) of the training dataset suffers from long-tailed distribution and 2)…
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…