The Power of Simple Tabulation Hashing

• p. 3 Intro

  As defined by Wegman and Carter [WC81] in 1977

• p. 45 References

  Journal of Computer and System Sciences, 22(3):265–279, 1981. See also FOCS’79.

• p. 44 Reference [CW79]

  18(2):143–154, 1979. See also STOC’77.

Only the authors can say what is right here.

Judge's note: I checked p.3 and the reference entries on pp.44-45. The abstract (p.1) also ties 1977 to 'Carter and Wegman (STOC'77)', which is [CW79]. Either the citation key or the year is inconsistent with the list. Only the authors can say which work they meant for the k-independence definition.

Second check: another model agreed

• p. 5 Intro, Minwise independence

  In the full version, we show that simple tabulation is ε-minwise in- dependent

• p. 6 Intro, Fourth moment bounds

  In the full version of the paper, we analyze the 4th moment

• p. 7 Contents of extended abstract

  We only have room to present the most essential results

• p. 5 'Minwise independence..' paragraph

  In the full version, we show that simple tabulation is ε-minwise in-

Judge's note: Page 1 contents list Sections 3, 5, 6 and Appendices A and B. Pages 5-7 carry the 'full version' and 'extended abstract' wording, and p.6 Section 2 also defers branch (3) to the full version. This looks like text left over from the conference abstract, and it misdescribes this document.

Second check: another model agreed

• p. 7 'Contents of extended abstract..' paragraph

  We only have room to present the most essential results; namely the Chernoff style concentration from Theorem 1 and the results for Cuckoo hashing from Theorem 2.

• p. 1 Contents

  Linear probing and the concentration in arbitrary intervals

Judge's note: The table of contents on p.1 lists Minwise Independence (p.9), Linear probing and the concentration in arbitrary intervals (p.23), Fourth Moment Bounds (p.28), Experimental evaluation (p.35) and Chernoff bounds with fixed means (p.41). The scope statement on p.7 contradicts this; it was evidently carried over from the conference version. Section 2 on p.7 also says that branch (3) "is shown in the full version of the paper", which is similarly leftover text.

Second check: another model agreed

• p. 7 Notation

  so an m-bit hash code is obtained by keeping only the most significant log2 m bits

Judge's note: Checked the crop of p.7. The sentence keeps log2 m bits to get a value in [m], so "m-bit" contradicts the rest of the sentence. The fix is evidently a "log2 m-bit hash code" or a "hash code in [m]". This is a wording slip; no result depends on it.

Second check: another model agreed

• p. 11 Section 3.1

  Start by fixing h(q1), . . . , h(qc) subject to h(q) = x.

Judge's note: From the p.10 image (PDF p.11): f(p) is defined as conditioned on h(q) = p, and x is then used for a key in Gα, so 'h(q) = x' clashes with both. z appears nowhere else. These are notation slips; the argument is recoverable.

Second check: another model agreed

• p. 11 Proof of Lemma 8

  each with success probability p. The probability of no failures occurring is (1 −p)t

Judge's note: Checked both pages. The formula is right, but the named event is the complementary one. The intent is clear from the formula.

Second check: another model agreed

• p. 12 Proof of Lemma 8

  (1 −p)t ≤1 −αt + (αt)2/2

• p. 11 Lemma 8 statement

  Let p ∈[0, 1] and k ≥0, where p · k ≤

• p. 12 end of proof of Lemma 8

  (pk)2 ≤1 −pk.

Only the authors can say what is right here.

Judge's note: Reworked: at k=0 (or p=0) both sides equal 1, so the strict '>' is false as printed. In the proof, Gerber's inequality is '≤', and the final step 1 − pk − (1 − (1+pk)²/2)(pk)² ≤ 1 − pk is an equality when pk = √2−1, so strictness is never established. Use in (6) and later needs only ≥, so the downstream bound stands. That is why this is rated S3 rather than S1. The α-for-p symbol slip also quoted in this cluster is judged under C036.

Second check: another model agreed

• p. 16 Section 4, encoding argument

  has entropy |Σ|c lg m bits

Judge's note: Page 16 image shows the superscript c on |Σ|. |Σ|^c lg m is the entropy of a fully random function on Σ^c. The encoding argument uses only the saving γ, so Pr[E] = O(2^{−γ}) is unaffected. The misstatement is in the description of the quantity.

Second check: another model agreed

• p. 18 Section 4, after the basic stream

  lg m = lg((1 + ε)n) ≥ε + lg n bits

• p. 18 Section 4, same paragraph

  O(lg k) ≤εk + f(c, ε) = k + O(1)

Only the authors can say what is right here.

Judge's note: lg(1+ε) ≥ ε holds on [0,1] by concavity, with equality at 0 and 1. It fails for ε>1: for ε=3, lg 4 = 2 < 3. Theorem 2 (PDF p.5) states m=(1+ε)n with no upper limit on ε, and I found no assumption ε≤1 in Section 4. The per-edge saving is still at least min(ε,1) bits, so the argument survives with that substitution. The step is false as printed, but the stated result stands. The 'k + O(1)' part of this cluster is the same defect as C050.

Second check: another model agreed

• p. 19 Lemma 14

  If xi∆xi+1 ⊆x<i, then we can encode both Id(xi) and Id(xi+1)

• p. 22 Case 4

  K = x<t−1 ∪a1 ∪a2, so xt−1∆xt ⊆K

Only the authors can say what is right here.

Judge's note: Checked PDF pp.19 and 22. In Case 4 (i=t−1, t≤k), x̂_t is nonempty, lies in x_{t−1}Δx_t, and is disjoint from x_{<t−1}. The printed hypothesis therefore fails, and only the K version is verified. Case 5 also applies the lemma with K = x_{<k} ∪ a1 ∪ a2. The proof (z = x_i \ x_{<i}) goes through with x_{<i} replaced by K, and the O(c lg|K|) term shows K was intended. The lemma as printed is too narrow for its uses, but the result stands once the hypothesis reads ⊆ K.

Second check: another model agreed

• p. 19 Proof of Lemma 15

  Note β̸ = α and such a β exists by assumption.

Only the authors can say what is right here.

Judge's note: Let U1=(x_iΔx_{i+1})\x_{<i} and U2=(eΔf)\x_{<i}. The hypothesis gives U2≠∅ and U2≠U1. If U1 ⊊ U2 (e.g. U1={β}, U2={α,β}), then U1\U2=∅ and no such β exists. U1={β} can arise when x̂_i ⊆ x_{i+1} and x̂_{i+1}={β}. This configuration is consistent with eΔf ⊂ x_{≤i+1}. The lemma itself still holds, because two distinct nonzero GF(2) vectors are independent: deduce β from the x_i/x_{i+1} equation, then α from the e/f equation. The printed justification is wrong, but the stated result stands.

Second check: another model agreed

• p. 20 Proof of Lemma 16

  it must be that ˜e ∪˜f ⊂ xi+1 by

Only the authors can say what is right here.

Judge's note: I verified the reviewer's counterexample against the lemma's hypotheses. With c=2, i=1, x1={(1,a),(2,b)}, x2={(1,a'),(2,b)}, e={(1,a),(2,g)}, f={(1,a'),(2,g)}: e\x≤1={(2,g)} ≠ f\x≤1={(1,a'),(2,g)}, and e\x≤2 = f\x≤2 = {(2,g)}. But ẽ∪f̃={(1,a),(1,a')}, and (1,a)∉x2. The rest of the proof (x̂_{i+2} has no characters of ẽ∪f̃, and Lemma 15 applies) needs only ⊂ x_{≤i+1}. The step is false as printed, but Lemma 16 stands.

Second check: another model agreed

• p. 21 Case 3

  This assumption is exactly what we need to apply Lemma 15

• p. 22 Lemma 20 / Cases 4, 6-8 (same notation)

  aj \ x<tj−1 = ˆxtj−1∆ˆxtj

Only the authors can say what is right here.

Judge's note: Checked PDF pp.21–22. Reworking: (x_{t−1}Δx_t)\x_{<t−1} = (x̂_{t−1} \ x_t) ∪ (x_t \ x_{≤t−1}) = (x̂_{t−1}\x_t) ∪ x̂_t. This is smaller than x̂_{t−1} ∪ x̂_t when x_t reuses a new character of x_{t−1}. In the reviewer's c=3 example, a_j\x_{<t−1}={(2,b),(3,d)}. This differs from x̂_{t−1}∪x̂_t={(1,a),(2,b),(3,d)}, but equals (x_{t−1}Δx_t)\x_{<t−1}. So the Case 3 condition holds while Lemma 15's does not, and Cases 4–8 (which assume the printed equality) do not cover it either. Reading the notation as (x_{t−1}Δx_t)\x_{<t−1} closes the gap. The authors should confirm.

Second check: another model agreed

• p. 23 Proof of Lemma 20

  using lg C(y) ≤lg 1 2 lg n bits

• p. 23 Proof of Lemma 20

  using lg C(y) ≤lg 1

Only the authors can say what is right here.

Judge's note: Checked the crop and page 23 image: the extra 'lg' is printed. Reworking: in this case C(y) ≤ √n, so lg C(y) ≤ ½ lg n. The printed lg(½ lg n) is false as printed, since C(y) can be as large as √n. The surrounding accounting uses ½ lg n, so the lemma itself stands.

Second check: another model agreed

• p. 26 After Claim 23

  δi,jµj = ∆i,j = Θ(δ2

Only the authors can say what is right here.

Judge's note: PDF p26 image. Δ_{j,i} is defined on the same page as (δα/24)·2^{(4/5)i+(1/5)j}, and µ_j = α2^j. Dividing gives (δ/24)·2^{(4/5)(i−j)}, which matches the next expression only if the α is kept. As printed, without α, the quotient would carry an extra 1/α factor. The following line is correct, so the result stands.

Second check: another model agreed

• p. 27 End of proof of (7)

  ¯h = O(log log1/a(2i/m))

• p. 27

  hat m/2i ≥n1−1/(3c), so h = O(log log m) is OK. To avoid

Only the authors can say what is right here.

Judge's note: PDF p27 image. Reworking: a^{2^h̄} ≤ (2^i/m)^γ is equivalent to 2^h̄ ≥ γ·log_{1/a}(m/2^i), which gives h̄ = O(log log_{1/a}(m/2^i)). The fraction is inverted as printed. The 'repeated log' text-rule hit is not a defect, because log log is intended. The result stands.

Second check: another model agreed, code check

• p. 28 End of proof of (7)

  we have O(2i+¯h/m)γ−1 ≤(2i/m)γ/2. We conclude that

• p. 28 End of proof of (7)

  Pr[Dℓ,δ,p] = (2i/m)2γ +

Only the authors can say what is right here.

Judge's note: PDF p28 image. Since 2^i/m < 1, (2^i/m)^{2γ} is smaller than the (2^i/m)^{γ/2} that was derived, so the printed term does not follow. γ is an arbitrary constant, so (7) still holds after renaming γ. The step is faulty but the stated result stands.

Second check: another model agreed

• p. 32

  Yi and Yj are independent (these involve looking

Only the authors can say what is right here.

Judge's note: Checked on the page image (PDF p.32). The printed statement is true: Yi and Yj are independent by 3-independence of {i,j,q}. However, it is never used. Yi^2 ≤ 1 is simply bounded, and the probability bound O(1/m^2) for Yj = Yk = 1−1/m needs Yj and Yk independent, which follows from 3-independence of {j,k,q}. The authors should say whether Yj and Yk was intended. The claim itself stands.

Second check: another model agreed

• p. 34 Section 6.4, proof of (18) for δ ≥ 1

  Since δ ≥1, we get j = i −3.

Only the authors can say what is right here.

Judge's note: Own check against Claim 22 (PDF p.25). If δ>2 then δ/(1+δ/2) > 1, so j=i−2 satisfies the strict inequality. j=i−1 never does, because δ/(1+δ/2) < 2. So the maximal j is i−2. j=i−3 is maximal only for 1 ≤ δ ≤ 2. The proof of Claim 22 needs only that j satisfies the inequality, which j=i−3 does for every δ ≥ 1. The 2^5+1 bins and bound (18) therefore stand; only the stated derivation is inexact.

Second check: another model agreed

• p. 35 Section 6.4, before eq. (20)

  We see that for j ≥j1, the bound decreases exponentially with j

• p. 35 Line before (20)

  We see that for j ≥j1, the bound decreases exponentially with j, so

Only the authors can say what is right here.

Judge's note: Reworked from the page image (PDF p.35): P_j is proportional to 2^{−(i−j)/5}, which is 1 at j=i and 1/2 at j=i−5. The terms form a geometric series dominated by j=i, so (20), Σ_{j=j1}^{i} P_j = O(1/(δ^4(α2^i)^2)), holds. Only the stated direction is reversed. The step's wording is faulty, but the result stands.

Second check: another model agreed

• p. 42 Appendix A, cuckoo discussion

  Based on Table 1, this would be two orders of magnitude slower than simple tabulation.

• p. 39 Table 1

  99.70

• p. 42 Cuckoo hashing, DW03 comparison

  this would be two orders of magnitude slower than simple tabulation

• p. 39 Table 1

  5-indep-Mersenne-prime 99.70

Only the authors can say what is right here.

Judge's note: Table 1 on page 39: 99.70 vs 4.98 ns and 45.06 vs 4.61 ns, for 32-bit keys with p = 2^61−1 as in the proposed scheme. Doubling these for two degree-5 polynomials gives about 40× and 20×. That is well short of 100×. The wording overstates what Table 1 supports, unless the authors had extra overheads in mind.

Second check: another model agreed

• p. 42 A.5, after hypercube results

  the deviation from 3.28 over 100 independent runs grew from below 0.5% with random input to almost 1% with any of the structured input

• p. 41 Figure 3

  Figure 3: Keys from hyper cube.

• p. 41 Figure 3

  Keys from hyper cube.

• p. 41 Figure 3

  average probes per insert/delete

Only the authors can say what is right here.

Judge's note: Page 41: in Figure 2(a), the dense interval, simple-table's vertical CDF line sits just above 3. In Figure 3, the hypercube, it sits at about 1.6. So 3.28 cannot be the reference mean for every structured input. The deviation may be meant relative to each input's own mean, but the text names 3.28. A secondary point raised by one reviewer is not a defect: 'less than 0.02' of 3.28 (≈0.6%) does not contradict 'below 0.5%', because both are upper bounds.

Second check: another model agreed

• p. 42 Appendix A, comparison with [DW03]

  For a nontrivial failure probability with sets of 220 keys, this would require 6-independence.

Only the authors can say what is right here.

Judge's note: Rests on outside knowledge: whether the [DW03] analysis requires an even d, or a target failure rate much smaller than 1/32. Page 42 gives only n/r^{d/2} and r = 2^10. Under that formula d = 4 gives exactly 1 and d = 5 gives 1/32, so 'nontrivial' does not by itself force d = 6. The authors should say what threshold or constraint they mean.

Second check: another model agreed

• p. 4 Linear probing heading

  Linear probing..

• p. 5 Cuckoo hashing heading

  Cuckoo hashing..

• p. 7 Notation heading

  Notation..

Judge's note: Seen in the page images for pp.4, 5 and 7. 'Chernoff bounds.' and 'Desirable properties.' have a single period.

Second check: none (judge only)

• p. 5 Intro, first line

  e.g,,

Judge's note: Visible on the first line of the page 5 image.

Second check: none (judge only)

• p. 7 Notation paragraph

  we can treat a key x as a set of q position-characters

Judge's note: Page 7 image shows italic q. In the same Notation paragraph, keys are in Σ^c and position-characters in [c] × Σ, and q is defined as the query in the preceding paragraph.

Second check: none (judge only)

• p. 7 Notation

  we mean 1 −ra for any desired constant a

Judge's note: Page 7 image shows 1 − r^a with a positive exponent. For a > 0 and r > 1 this is negative, so it is not a probability. Elsewhere the paper writes high probability as 1 − n^{−γ} (Theorem 1).

Second check: none (judge only)

• p. 7 Sec. 2 intro

  we shows that the load of any fixed bin

Judge's note: The page image confirms the subject–verb disagreement.

Second check: none (judge only)

• p. 8 Chernoff Bounds for a Fixed Bin

  define a total ording ≺

Judge's note: The misspelling is confirmed on the p.8 image.

Second check: none (judge only)

• p. 8 Proof of Lemma 5

  We have to prove is that, as long as

Judge's note: The ungrammatical phrasing is confirmed on the p.8 image.

Second check: none (judge only)

• p. 9 Lemma 6

  (2c(3 + γ)c, 22c(3+γ)

Judge's note: The image shows two opening parentheses before 2c and only one closing parenthesis, after γ, followed by the exponent c. Applying Lemma 4 with ε = 1/(2c) and failure exponent 2+γ gives ((1+2+γ)·2c)^c, which supports (2c(3+γ))^c.

Second check: none (judge only)

• p. 10 Section 3, eq. (5)

  Pr[h(q) < min h(X)]

Judge's note: Checked the p.9 crops (PDF p.10). A grep of the text finds h(X) only at these two spots, while Section 3's subsequent formulas and the introduction use h(S). The notation is inconsistent; the meaning is clear.

Second check: none (judge only)

• p. 10 Sec. 3

  the minimum bin in non-empty

Judge's note: The typo is confirmed on the image.

Second check: none (judge only)

• p. 11 Sec. 3.1

  Let h(≺α) done the choice for all

Judge's note: The typo is confirmed on the page image.

Second check: none (judge only)

• p. 11 before Sec 3.1

  of 1 −p of landing about p

Judge's note: Page 11 (printed p.10), line just before §3.1, shows "landing about p". The meaning is landing above p, so 'about' is a wrong word.

Second check: none (judge only)

• p. 12 Proof of Lemma 8

  (1 −p)t ≤1 −αt + (αt)2/2

Judge's note: Page 12 image: α appears in the inequality, and the next line uses p. α is undefined here and denotes position-characters elsewhere.

Second check: none (judge only)

• p. 12 after Lemma 8 proof

  no failure occurs amount t Bernoulli

Judge's note: Page 12, first line: 'amount' is a wrong word for 'among'.

Second check: none (judge only)

• p. 13 Before Lemma 9

  Let n(≻α) = P β≻α |Gα|

• p. 13 Before Lemma 9

  Let n(≻α) = P

• p. 13 before Lemma 9

  n(≻α) = P β≻α |Gα|

• p. 13 Section 3.2, before Lemma 9

  Let n(≻α) = P β≻α |Gα| and define n(⪰α) simmilarly.

Judge's note: Page 13 image shows the subscript α on G inside the sum over β, so this is not an extraction artefact. Lemmas 9 and 10 use n(≻α) as the number of keys in later groups, so the intent is clear.

Second check: none (judge only)

• p. 13 before Lemma 9

  define n(⪰α) simmilarly

Judge's note: Page 13 image confirms 'simmilarly'.

Second check: none (judge only)

• p. 17 An easy way out

  there subkeys a and b on the positions such that

• p. 17 An easy way out

  there subkeys a and b on the positions

Judge's note: The page image (p.17, printed p.16) shows the sentence exactly as quoted, with no verb. This is a copy-edit slip.

Second check: none (judge only)

• p. 18 Section 4, paragraph on O(lg k) terms

  O(lg k) ≤εk + f(c, ε) = k + O(1)

Judge's note: The image shows '= k + O(1)'. Since f(c,ε)=O(1), the right-hand side equals εk + O(1), and the argument needs the εk form so that εk absorbs O(lg k). The equality as printed is false for ε<1.

Second check: none (judge only)

• p. 19 Lemma 16 title

  Lemma 16 (odd-size saving)

• p. 22 Case 5

  Lemma 16 (odd-side saving)

Judge's note: Images of PDF p.19 (title) and p.22 (references) confirm the inconsistency. The lemma concerns parity, i.e. the side of the bipartite graph, so 'odd-side' is intended.

Second check: none (judge only)

• p. 19 Proof of Lemma 15

  the last unknown in the equality hi(x) = hi(xi+1)

Judge's note: The PDF p.19 image shows 'h_i(x) = h_i(x_{i+1})'. Here x is undefined, and the collision in use is h_i(x_i)=h_i(x_{i+1}).

Second check: none (judge only)

• p. 21 Proof of Lemma 17, final bound

  Overall, the encoding uses space: lg n C(ξ)

• p. 21 End of proof of Lemma 17

  Overall, the encoding uses space: lg

Judge's note: The PDF p.21 image shows ξ and ê_{i+1}. The proof defines y and g and costs them as lg n/C(y), lg n/C(g) and lg min{C(y),C(g)}. The symbols are leftover notation, and the bound holds with y and g.

Second check: none (judge only)

• p. 22 Proof of Lemma 19

  Since aj ∩ˆxk̸ = in the current case

Judge's note: The PDF p.22 image shows '≠ in' with no ∅, so this is not an extraction loss.

Second check: none (judge only)

• p. 22 Case 5

  Lemma 17 (piggybacking) can give use Id(a) and Id(b)

• p. 22 Case 5

  can give use Id(a) and Id(b)

Judge's note: The PDF p.22 image confirms both slips: 'use' for 'us', and a, b, whereas the keys being piggybacked in Case 5 are a1 and a2.

Second check: none (judge only)

• p. 24 Section 5, definition of R

  positions h(q), ..., h(q) + ℓ−1 are filled

• p. 24 Section 5, second paragraph

  positions h(q), ..., h(q) + ℓ−1 are filled with keys from S while h(q) + R is empty

Judge's note: Page 23 image (PDF p24): the run being defined has length R, as the next sentence's 'h(q) and h(q)+R−1' shows. ℓ is a different quantity, the interval-length threshold in Theorem 21. This is a symbol slip.

Second check: none (judge only)

• p. 24 Section 5, second paragraph

  leads to an an optimal

• p. 24 Section 5, third paragraph

  will consider at most at most

• p. 24 Sec. 5

  simpler, tigher, and more generic

• p. 24

  4, our analysis also leads to an an optimal O(1/ε2) for

Judge's note: All three are visible on the PDF p24 page image.

Second check: code check

• p. 24 Sec. 5

  5-indepedent hashing

• p. 24 Sec. 5

  general relative devations δ

Judge's note: Both misspellings are visible on the PDF p24 page image.

Second check: none (judge only)

• p. 25 after Thm 21

  the reletive deviation δ

• p. 25 after Thm 21

  diadic intervals

• p. 26 δ ≤ 1

  To circument

Judge's note: All three are visible on the page images.

Second check: none (judge only)

• p. 28 Sec. 5.1

  maximal dyadic decompostion

Judge's note: The misspelling is visible on the PDF p28 page image.

Second check: none (judge only)

• p. 28 After Corollary 24

  in Section 6.4 (21), we show that we that this implies that linear probing fills h(q) with probability O(α)

• p. 36 Section 6.4

  as promised in (13), we have

Judge's note: On the page image the text reads "we show that that this implies", not "we that" as quoted, so there is one duplicated "that". On p.35 (PDF p.36) the bound Pr[L>0]=O(α) is derived directly from (21) with δ=1/(2α), and the text there says "as promised in (13)". Pointing to (21) as the source is therefore reasonable and is not a defect. Only the duplicated word is confirmed.

Second check: none (judge only)

• p. 28 Proof of Corollary 24

  (1 + δ) = 1/α implying δ ≥1/2..

Judge's note: Page image confirms the text and the doubled period. If α ≤ 1/2 then 1/α ≥ 2, so δ ≥ 1. The printed δ ≥ 1/2 is still true and is enough for the δ = Ω(1) case of Theorem 21, so the proof stands. The defect is cosmetic or a minor looseness.

Second check: none (judge only)

• p. 29 Section 5.1

  so (i −j0 + 1)n−γ ≤n−γ′(1 + log n)

Judge's note: The page image (PDF p.29) shows the previous sentence: "The error probability over all j ∈{j0,...,i} is (i−j0+1)n^{−γ′}". The next line then writes n^{−γ} on the left and n^{−γ′} on the right. The intended chain is (i−j0+1)n^{−γ′} ≤ n^{−γ′}(1+log n) ≤ n^{−γ} for a suitable γ′. This is a notational slip, and the result is unaffected.

Second check: none (judge only)

• p. 30 Sec. 6

  indendently discovered

• p. 34 Sec. 6.4

  as an intial step

• p. 35 end of 6.4

  the variace

• p. 34 Sec. 6.4

  does not give a probablity bound

Judge's note: All four misspellings are visible on page images p030, p034 and p035. The same page also has "devation" (p.33), which the reviewers did not list.

Second check: none (judge only)

• p. 32 Claim 29

  h(k) depends on h(i), h(j), h(k)

• p. 32 Claim 29

  depends on h(i), h(j), h(k).

• p. 32 Claim 29

  such that h(k) depends on h(i), h(j), h(k)

• p. 32 Claim 29

  there is a unique key k such that h(k) depends on h(i), h(j), h(k)

Judge's note: The page image (PDF p.32) confirms h(k) as the final term. The claim is quantified over distinct i, j, q, and the proof reasons about {i,j,q} and {i,j,k,q}. A key depending on its own hash is vacuous, so the intended term is h(q).

Second check: none (judge only)

• p. 33 proof of Claim 29

  two distinct distinct characters on some positon

• p. 33 proof of Claim 29

  i, j, and q conincide

• p. 33

  r. If i, j, and q contain two distinct distinct characters on some

Judge's note: All three are visible on page image p033, in the first paragraph.

Second check: code check

• p. 34 Sec. 6.4

  the expected number of filled entries probes is O(α)

Judge's note: Seen on page image p034. The same paragraph also has "the expected number probes", with a missing "of".

Second check: none (judge only)

• p. 34

  h(1) = h(2) ⊕hC(3) ⊕hC(4).

Only the authors can say what is right here.

Judge's note: The page image (PDF p.34) shows h_C with subscript C on terms 3 and 4 but not on term 2, and a search of the text finds no definition of h_C. It may mean hashing restricted to the remaining columns C, but if so it should apply to all three terms. The notation is inconsistent.

Second check: none (judge only)

• p. 38 A.3, 5-indep-TZ-table

  The scheme is is rather

• p. 39 A.5, end of page

  the different schemes schemes now have to compete

• p. 38 A.3 5-indep-TZ-table

  The scheme is is rather complicated to implement

• p. 39 A.5

  the different schemes schemes now

Judge's note: All three are visible on the page images: 'is is' and '5-independet' in A.3 on page 38, and 'schemes schemes' on the last line of page 39.

Second check: code check

• p. 38 A.3

  We are free to chose the size

• p. 38 A.3

  providing a random value Ti[xi] with a random value

Judge's note: Both are visible in the simple-table paragraph on page 38.

Second check: none (judge only)

• p. 39 A.5 first paragraph

  the hash function needs good random properties are need for good performance on worst-case input

• p. 39 A.5

  the hash function needs good random properties are need for good performance

Judge's note: Visible in the first paragraph of A.5 on page 39. The sentence mixes two constructions.

Second check: none (judge only)

• p. 39 A.4

  The competetiveness of simple tabulation

Judge's note: Visible on page 39 in section A.4.

Second check: none (judge only)

• p. 42 Appendix A, Cuckoo hashing, 64-bit keys

  We set A = 8, giving 88 = 224 keys in S

• p. 42 Cuckoo hashing experiment, 64-bit keys

  We set A = 8, giving 88 = 224 keys in S.

• p. 42 Cuckoo hashing experiments

  We set A = 8, giving 88 = 224 keys

Judge's note: Page 42 image checked: the 32-bit line has brackets, A = [32], and the 64-bit line has A = 8 without brackets. 8^8 = 2^24 is correct.

Second check: none (judge only)

• p. 42 Appendix B

  hold if when each variable have a fixed mean even if the of the variables are not independent. Below shall use

Judge's note: Visible at the bottom of page 42: 'if when', 'variable have', 'the of the' (a noun is missing) and 'Below shall use' (missing 'we').

Second check: none (judge only)