NumberDB$^\beta$ Advanced search Tags Tables Help Login
Roots of the cuckoo hashing threshold equation
edit · history · discussion · files · long url · combinatorics probability theory
Numbers
$k$
$\ell$ 
$\xi_{k,\ell}$
2
2:
2.687999345499491341463796937790041489618073899549236397935209599334514422260144214209251869745312739
comment: The associated cuckoo hashing threshold is $c^*_{2,2}$.
2
3:
5.071469708158110598648643546349746111224536523134635041837351018367446479545269819843879943093996070
comment: The associated cuckoo hashing threshold is $c^*_{2,3}$.
2
4:
7.321703358983259836814496629523591100449318121409982457321275056792696725897271000383910518926918359
comment: The associated cuckoo hashing threshold is $c^*_{2,4}$.
2
5:
9.496116339631318678686127155202154774263071948634199710067456727225709958713336937514852230633003440
comment: The associated cuckoo hashing threshold is $c^*_{2,5}$.
2
6:
11.62201083475983117017772549639697906479047433129974127980306614609092022913414759542897782318128499
comment: The associated cuckoo hashing threshold is $c^*_{2,6}$.
2
7:
13.71478188066531187419592663386781404667256909748779267691699334062513889841987887243770904218501949
2
8:
15.78402951575241749514337877292627806948039669526522457278218532643843899662344975085249937108013643
3
1:
2.149125799907062542079080149425149925528828496714285459034660801183768221524370129087681616217046728
comment: The associated cuckoo hashing threshold is $c^*_{3,1}$. This is also $\xi_{3}$.
3
2:
5.656576349425156386746617941568588192659141691293506742008009681442341139286464459237741396129083249
comment: The associated cuckoo hashing threshold is $c^*_{3,2}$.
3
3:
8.849851652473190362812087757716704933249004939448022043446615039577597636956590060258950889502471470
comment: The associated cuckoo hashing threshold is $c^*_{3,3}$.
3
4:
11.93324063021001784506567092268224882890651379335616698876346069366242440532751486950076095207023045
comment: The associated cuckoo hashing threshold is $c^*_{3,4}$.
3
5:
14.97035798828812027443562587311940396807103878054315654978741750621682886826142355899362774443783528
comment: The associated cuckoo hashing threshold is $c^*_{3,5}$.
3
6:
17.98693229671281992725192590653386429471971042695500411009746368493209696294996668806395227602097357
comment: The associated cuckoo hashing threshold is $c^*_{3,6}$.
3
7:
20.99428721963569996390356939647821605540269988019492846111677264277639899563812999474020204223244644
3
8:
23.99752228639355428601762208898877869365731075533340009984939339959751647474711325899830231566627929
4
1:
3.593511969447426082272169884555315798860946340951301392760865045230967927293167350976509334752600022
comment: The associated cuckoo hashing threshold is $c^*_{4,1}$. This is also $\xi_{4}$.
4
2:
7.907674019123758850790566789844419922995108412022415004802350765389662552216371593154538151656605121
comment: The associated cuckoo hashing threshold is $c^*_{4,2}$.
4
3:
11.97840754548836518417183962921129418652192059426167092339410984246940990181779382295840160771130815
comment: The associated cuckoo hashing threshold is $c^*_{4,3}$.
4
4:
15.99506456917725118329956899417052588708356806076354172978753823547047795118689779120004162634038769
comment: The associated cuckoo hashing threshold is $c^*_{4,4}$.
4
5:
19.99889979196351691674775775685275577102351928181638457324870251227217088836762137643885395177578993
comment: The associated cuckoo hashing threshold is $c^*_{4,5}$.
4
6:
23.99975947604794575691841460248553012829750258139642040533729634692718122214453372206287303646511694
comment: The associated cuckoo hashing threshold is $c^*_{4,6}$.
4
7:
27.99994816711800378712866883725114403620723445488544625643687745996149027919522284745023750300229475
4
8:
31.99998894879824441417761862037158295979322617563944053294099209179496582008077917131009191700694329
5
1:
4.801007549722517843402554184936876206309580045670987737307642940448096932959992199826971793616174495
comment: The associated cuckoo hashing threshold is $c^*_{5,1}$. This is also $\xi_{5}$.
5
2:
9.976864303760496064518075863793575319292786047595390211066663963569991540942269856056674145453186667
comment: The associated cuckoo hashing threshold is $c^*_{5,2}$.
5
3:
14.99741350114707424427436529215687505875158666319175852037547329980901221594064290374107937980231339
comment: The associated cuckoo hashing threshold is $c^*_{5,3}$.
5
4:
19.99972511819509434997149501618076756231262856417056906108861824236177909822971068355118859476119916
comment: The associated cuckoo hashing threshold is $c^*_{5,4}$.
5
5:
24.99997174425962980488681204119343855489405198561699586682058895464280942938737404120353105180800265
comment: The associated cuckoo hashing threshold is $c^*_{5,5}$.
5
6:
29.99999715761549573994778634148325126494830338224240111896361395105934488672352627555997411293020102
comment: The associated cuckoo hashing threshold is $c^*_{5,6}$.
5
7:
34.99999971828689495073763165197240517066200863512164923396388731330097929439240393661829966466206228
5
8:
39.99999997237895330621788962981778883738297516823892960097598945470307781177261883554921351313680319
6
1:
5.903000058948943810458175385422799724242893481515842146827627134583507853576375177519654679441566068
comment: The associated cuckoo hashing threshold is $c^*_{6,1}$. This is also $\xi_{6}$.
6
2:
11.99466733019710920890189533055350295714134739551676260854413064936109585534197475883076176045683468
comment: The associated cuckoo hashing threshold is $c^*_{6,2}$.
6
3:
17.99973347635061616803411249948014909629259883939838752321236504416573051808206817338186269012884600
comment: The associated cuckoo hashing threshold is $c^*_{6,3}$.
6
4:
23.99998747487764539641451256705490343509005188952388808136197333588086708276694929140893017510583906
comment: The associated cuckoo hashing threshold is $c^*_{6,4}$.
6
5:
29.99999943152413327868681837784491101013451684606105198098041990967162124172322669914399673273473956
comment: The associated cuckoo hashing threshold is $c^*_{6,5}$.
6
6:
35.99999997475451784136341288345456857119692422196366712451810528566280859222197757374080216380199990
comment: The associated cuckoo hashing threshold is $c^*_{6,6}$.
6
7:
41.99999999889542414122366233303485143320654681741093711561127695504527103766420273066250232144793028
6
8:
47.99999999995219035911121073083261956776388908486262174893059213350857113390914160633563926285687229
7
1:
6.953455713353474571757750459668776777157703675694193843415968941936946472738479953900380174362202268
comment: The associated cuckoo hashing threshold is $c^*_{7,1}$. This is also $\xi_{7}$.
7
2:
13.99885801107353040821026786739382027366723850806829945798703162739514390358101431148202137692247181
comment: The associated cuckoo hashing threshold is $c^*_{7,2}$.
7
3:
20.99997542174545116865984920724717820919492653448481645717520596822045513748851642102679476382231719
comment: The associated cuckoo hashing threshold is $c^*_{7,3}$.
7
4:
27.99999950416907812559837246489148384069148256876607111079228415555129553225681370701807267652350603
comment: The associated cuckoo hashing threshold is $c^*_{7,4}$.
7
5:
34.99999999034126708478328429759287181356009191496219282981587565655646617784379490803056882062904127
comment: The associated cuckoo hashing threshold is $c^*_{7,5}$.
7
6:
41.99999999981590402367849092443096959604956068083312186280042756840973653364740468966946712440564761
comment: The associated cuckoo hashing threshold is $c^*_{7,6}$.
7
7:
48.99999999999654292747548744500679934181770500628007276070831287944725977561733647959273498745564802
7
8:
55.99999999999993577845740933717347678095367153698328337540863073043813488092281488750741802432689143
8
1:
7.978107736977070325801043211904953879262698393828180241246253405412112875926606187603354958634672340
comment: This is also $\xi_{8}$.
8
2:
15.99976948102927827986542124541488713267127746399729766072612805128795102265768110760940453279424376
8
3:
23.99999791249776477526583476080506216234102397159993337514112341684209297104091256244852792327457149
8
4:
31.99999998229421298460254326745152221550730148833673533729524296426543935216880675395508263187643527
8
5:
39.99999999985498950806757475620303349980850606530853798231452429691164904454209053823396541671456058
8
6:
47.99999999999883796011733170868052057137582534802368310535910608098338588451248045651064858878746216
8
7:
55.99999999999999082549391562002909328701108769779675895602517556708034266361241800416573464377913288
8
8:
63.99999999999999992834402649754375760190095303136801320458170026394134384645740733675987984543584298
9
1:
8.989912519269479737859486962678439859820876867181214191191759058921700750894868987723157685967200046
comment: This is also $\xi_{9}$.
9
2:
17.99995558761294977966818068289267088363733341183405815612510976231904637506443052969637856628689981
9
3:
26.99999983352352961042941034339633686304220206518353674195280425530683901186238491867268566768515694
9
4:
35.99999999941561385098893372788096996561690281820301749212947615290516804614045183422834008690123778
9
5:
44.99999999999801919305082234770327569019046986214351730820829668360886856474366257676088334662390077
9
6:
53.99999999999999343065909329240090609003008758610857626415549884626998582815644147538220664394674172
9
7:
62.99999999999999997853447576929085008477958958894807023008980265237111984961160627932241566256965976
9
8:
71.99999999999999999993061441609145926492092198540629260762095728903122120396676581175298500932542075
10
1:
9.995441133814842741400932592133052045659869599058257396947103091116896080275781481170753765750751443
comment: This is also $\xi_{10}$.
10
2:
19.99999175532397639510723938539197172685876190125580078940097278567402872373190369462770109320805875
10
3:
29.99999998736720884786849000606127949609681146401724642592851062919967298195042923078301953657939331
10
4:
39.99999999998187368851045929393106882058385746209414203789099520628733836767523116000236057505306730
10
5:
49.99999999999997488606968796925152644784476238575890384234977335355924395199220785928036687273938648
10
6:
59.99999999999999996595468615463592787867667500988890573654324673171421401025800846179121604786771409
10
7:
69.99999999999999999995452841941861924002553783985688095997335889540455229361435728186723724816936075
10
8:
79.99999999999999999999993991987781392399810404873673798479132940346038560854294804041994268606612031
11
1:
10.99797533724523459964809795243574469075450093882819090308597431902540854000078754311674399450335085
comment: This is also $\xi_{11}$.
11
2:
21.99999851488517276973356296887971416297310448187286037590198521442657586161954157013882052989047286
11
3:
32.99999999907915484654545491315215449163745431990297375840265137828907644347735690959548374034591679
11
4:
43.99999999999946531877181122147256072419894574950910293217574266605946316139268086367466348320254086
11
5:
54.99999999999999970022294676201591390239148458347613314279899585265004830296739456794500897466038155
11
6:
65.99999999999999999983554796698832443426458379839525580909098650734782934863450405163700046159950972
11
7:
76.99999999999999999999991111670246507512745952320140207088988905626058824490013908561046140475302416
11
8:
87.99999999999999999999999995247642335132558037025826968825608144272689315958189086407055151646688758
12
1:
11.99911450952184187994188030867116719218749935503081985334373686869595954724308587188802621404555431
comment: This is also $\xi_{12}$.
12
2:
23.99999973906263763888635703659509263599693504819018910906283928752947053662071847875940174056266984
12
3:
35.99999999993506820569541850604743043381727068503034310488356895861522915810675023393886249474191992
12
4:
47.99999999999998486927236110518216962947226737596170690457984108010802546017790713704709072849131913
12
5:
59.99999999999999999659546861546359288175342248216531481598929226516094870792739885326898926339202027
12
6:
71.99999999999999999999925046437135835625690761305989053541447887800803389833608802049978599676410160
12
7:
83.99999999999999999999999983741994273900471654555240956479446650018331675054632253001815588891446266
12
8:
95.99999999999999999999999999996511406950363288604986811024745437877209428743378103551374565332127081
Definition
For integers $k\geq2$ and $\ell\geq1$ with $(k,\ell)\neq(2,1)$, the number $\xi_{k,\ell}$ is the unique positive solution of $k\ell=\xi Q(\xi,\ell)/Q(\xi,\ell+1)$; see [1] for the threshold equation.
Parameters
$k$
—   number of choices ($k\geq2$)
$\ell$
—   bucket capacity ($\ell\geq1$, with $(k,\ell)\neq(2,1)$)
Formulas
(1)
$Q(x,s)=\mathbb{P}(\mathrm{Po}(x)\geq s) =1-e^{-x}\sum_{j=0}^{s-1}x^j/j!$, where $\mathrm{Po}(x)$ denotes a Poisson random variable with mean $x$.
(2)
$c^*_{k,\ell}=\xi_{k,\ell}/(kQ(\xi_{k,\ell},\ell)^{k-1})$ for $(k,\ell)\neq(2,1)$; see [1] and [2] for this threshold formula.
Comments
(3)
$\xi_{k,\ell}$ determines the $\ell$-orientability threshold $c^*_{k,\ell}$ of the random $k$-uniform hypergraph [5] by formula (2) in this table. This threshold is the load threshold of cuckoo hashing [4] with $k$ choices and buckets of capacity $\ell$, as described in [1] for this model. Dietzfelbinger, Goerdt, Mitzenmacher, Montanari, Pagh and Rink [2] index bucket capacity one higher: their $\ell+1$ is the bucket capacity $\ell$ used here.
(4)
The excluded case $k=2$, $\ell=1$ has no positive root. For $\ell=1$, the quotient $xQ(x,1)/Q(x,2)$ has limit $2$ as $x\to0^+$ and is greater than $2$ for every $x>0$, so the equation $2=xQ(x,1)/Q(x,2)$ has no positive solution. The threshold $c^*_{2,1}=1/2$ is recorded in the cuckoo hashing threshold table.
(5)
For $\ell=1$ and $k\geq3$, $\xi_{k,1}$ is the root $\xi_k$ of the $k$-XORSAT threshold equation, which determines the threshold in the satisfiability threshold table for random $k$-XORSAT.
Programs
(P1)
Python
from mpmath import mp
mp.dps = 50
k, ell = 3, 1
if (k, ell) == (2, 1):
    raise ValueError("k=2, ell=1 has no positive root")
Q = lambda x, s: mp.gammainc(s, 0, x, regularized=True)
g = lambda x: x * Q(x, ell) / Q(x, ell + 1) - k * ell
lo, hi = mp.mpf("1e-30"), mp.mpf(4 * (k + ell) + 10)
while g(hi) <= 0:
    hi *= 2
for _ in range(4 * mp.dps):
    mid = (lo + hi) / 2
    if g(mid) < 0:
        lo = mid
    else:
        hi = mid
print((lo + hi) / 2)
References
[1]
N. Fountoulakis, M. Khosla and K. Panagiotou, The multiple-orientability thresholds for random hypergraphs, Combinatorics, Probability and Computing 25 (2016), 870-908. (arXiv) (doi)
[2]
M. Dietzfelbinger, A. Goerdt, M. Mitzenmacher, A. Montanari, R. Pagh and M. Rink, Tight thresholds for cuckoo hashing via XORSAT, Proceedings of ICALP 2010, Lecture Notes in Computer Science 6198, 213-225. (arXiv) (doi)
[3]
J. A. Cain, P. Sanders and N. Wormald, The random graph threshold for k-orientability and a fast algorithm for optimal multiple-choice allocation, Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), 469-476.
Links
Similar tables
Cuckoo hashing thresholds of random $k$-uniform hypergraphs —   thresholds obtained from these roots by the formula for $c^*_{k,\ell}$
Roots of the $k$-XORSAT threshold equation —   the same roots in the rows with bucket capacity $\ell=1$ and $k\geq3$
Data properties
Entries are of type: real number
How well the digits are known: proven
Sources of data: [1], [2], [3]
Table is complete: no (it holds $\xi_{k,\ell}$ for every $2\leq k\leq12$ and $1\leq\ell\leq8$ except $(k,\ell)=(2,1)$, extending the $\ell=1$ column through the range of the XORSAT root table and carrying the bucket-capacity range through $\ell=8$)
How they were obtained:

Each stored root is computed in ball arithmetic with 64 guard bits beyond the 100 digits written. The root $\xi_{k,\ell}$ is enclosed by bisection on the sign of $\xi Q(\xi,\ell)/Q(\xi,\ell+1)-k\ell$, down to a bracket of half-width $10^{-106}$ whose ends are checked to give opposite signs; that bracket is the stored ball.

more

The generator also compares every stored root with an mpmath computation at 120 digits that writes $Q$ as the regularised incomplete gamma function, checks the stored rows with $\ell=1$ and $3\leq k\leq12$ against the XORSAT root table, and compares each derived threshold with the cuckoo hashing threshold table for the rows that table also holds.



API Python package Skill for AI Privacy Legal notice Source
Data licensed CC BY-SA 4.0. No tracking, no analytics, essential cookies only.