Date & Time: 

   2026 /09 / 18  (Fri) 14:20 - 16:20

 

Location: 

   Delta Building R216, NTHU

 

Speaker: 

  王新博 教授

  國立臺灣大學 電機工程學系

 

Topic: 

  Not-so-Perfect Hashing and Massive Random Access

 

Abstract: 

  In this talk, we discuss how perfect hashing and its not-so-perfect variants can help save communication cost in massive random access (MRA).

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 do not share a slot with other users. This notion generalizes Song and Telatar's ISIT 2026 paper on non-perfect hashing and Kang and Yu's 2021 TIT paper on non-minimal hashing. We use the principle of maximum entropy (POME) to find an upper bound on the communication cost, which generalizes both papers and, in particular, outperforms the former for all 1/𝑒<𝛼<1.

For downlink MRA, we modify the idea of perfect hashing by allowing collisions among users assigned the same message, and call it message-separating hashing. We again use POME to estimate the cost, which matches the information-theoretic lower bound and the first-order asymptotics from the 2025 TIT paper by Song, Attiah, and Yu (for the lossless case) and the ISIT 2025 paper by Song and Yu (for the lossy case).

 

Autobiography: 

  Hsin-Po Wang is an Assistant Professor at National Taiwan University (EE & GICE). He received his BSc in Math from NTU and his PhD in Math from UIUC, then worked at UC San Diego and UC Berkeley before joining NTU.

Professor Wang is interested in applying math tools such as algebra, combinatorics, calculus, and probability theory to information theory and coding theory. Particular topics he has worked on include polar codes (wireless communication), group testing (with many downstream applications including heavy hitters, compressed sensing, and multiple access channels), regenerating codes (cloud storage), distributed matrix multiplication (cloud computation), DNA digital data storage (long-term high-density storage), differential privacy (privacy for sparse data), exact distribution shaping (randomized algorithms), and pessimistic cardinality estimation (database optimization).

Hsin-Po has a habit of putting too many TikZ figures in his papers and taking video games too seriously. He even has a webpage https://nm.lk/t collecting techniques that are too fancy for papers and another page https://nm.lk/f dedicated to beautiful factory designs in the video game Factorio.