{"id":"arxiv/2610.34750","url":"https://arxiv.org/abs/2610.34750","tags":["cs.DS","cs.CC","cs.IT","math.PR"],"score":0,"title":"Linear Hashing Is Poissonesque","domain":"cs.DS","source":"arxiv","authors":["Vinayak M. Kumar"],"reviews":0,"subject":"cs.DS","summary":"The Poisson approximation theorem states that when $m$ balls are tossed uniformly and randomly into $n$ bins, the distribution of the bin loads can sometimes be approximated by $n$ independent Poisson random variables of mean $m/n$. We show that when the balls are tossed via a random $\\mathbb{F}_2$-linear map, the load distribution is still governed by this Poisson distribution, albeit in a (necessarily) weaker manner. This allows us to show that a random linear map behaves like a fully random map in the following ways: 1. $\\textbf{Expected loads.}$ We show that the expected value of the…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-26","reactions":{}}