【講題】Not-So-Perfect Hashing for Massive Random Access

【演講時間】5月8日(星期五)下午1點30分  

【演講地點】清華大學校本部第二綜合大樓B側8樓A813室

【摘要】

This talk discusses how perfect hashing and its not-so-perfect variants can help save communication cost in massive random access (MRA). For downlink MRA, we borrow the idea of perfect hashing, but allow collisions among users assigned the same message. Compared with the 2025 TIT work of Song, Attiah, and Yu, our scheme increases the probability of success, reduces the expected number of trials, and reduces communication cost. We then invoke the principle of maximum entropy (POME) to conjecture that our upper bound is tight. For uplink MRA, we propose (α,β)-perfect hashing, where α is the fraction of slots occupied by exactly one user, and β is the fraction of users that are alone in their assigned slot. This generalizes Song and Telatar's α-perfect hashing presented at ITW 2026. We again use POME to find a competitively tight upper bound on the communication cost, which outperforms and generalizes the bound by Song and Telatar.