On The Relationship Between Several Variants Of The Linear Hashing Conjecture

Westover Alek. Arxiv 2023

[Paper]    
ARXIV Independent

In Linear Hashing ($\mathsf{LH}$) with $\beta$ bins on a size $u$ universe $\mathcal{U}=\{0,1,\dots ,u-1\}$, items $\{x_1,x_2,\dots ,x_n\}\subset \mathcal{U}$ are placed in bins by the hash function $$x_i\mapsto (a{x}_i+b)\mathrm{mod}p\mathrm{mod}\beta$$forsomeprime$p\in [u,2u]$andrandomlychosenintegers$a,b \in [1,p]$.The“maxload”of$\mathsf{LH}$isthenumberofitemsassignedtothefullestbin.Expectedmaxloadforaworst-casesetofitemsisanaturalmeasureofhowwell$\mathsf{LH}$distributesitemsamongstthebins.Fix$\beta=n$.Despite$\mathsf{LH}$‘ssimplicity,bounding$\mathsf{LH}$‘sworst-casemaxloadisextremelychallenging.Itiswell-knownthatonrandominputs$\mathsf{LH}$achievesmaxload$Ω\left(\frac{log n}{loglog n}\right)$;thisiscurrentlythebestlowerboundfor$\mathsf{LH}$‘sexpectedmaxload.RecentlyKnudsenestablishedanupperboundof$\widetilde{O}(n^{1 / 3})$.Thequestion“Istheworst-caseexpectedmaxloadof$\mathsf{LH}$$n^{o(1)}$?” is one of the most basic open problems in discrete math. In this paper we propose a set of intermediate open questions to help researchers make progress on this problem. We establish the relationship between these intermediate open questions and make some partial progress on them.

Similar Work

• Expected Number Of Uniformly Distributed Balls In A Most Loaded Bin Using Placement With Simple Linear Functions
• Non-empty Bins With Simple Tabulation Hashing
• Efficient Hashing With Lookups In Two Memory Accesses
• On The Insertion Time Of Random Walk Cuckoo Hashing