3 ms·

If you refer to the subtitle of the paper - An Algorithm for the (Text) Book - I think that is actually a reference to something *Paul Erdos allegedly said abou

If you refer to the subtitle of the paper - An Algorithm for the (Text) Book - I think that is actually a reference to something *Paul Erdos allegedly said about some proofs are so elegant in their simplicity and beauty that they are "from The Book", like representing some divine Platonic ideal. Given that Knuth himself reviewed it, he might have remarked that this was one of those algorithms! Perhaps the authors decided to include it in the title as a not-so-humble brag (which would be well-earned if that's the case!) edit: originally this comment said Knuth was the one who said this about some algorithms being from The Book, but that was my faulty memory.

kibibu 2y ago
I thought The Book was an Erdos thing. I wonder who used it first.
- stevesimmons 2y ago
  "During a lecture in 1985, Erdős said, `You don't have to believe in God, but you should believe in The Book.`" https://en.wikipedia.org/wiki/Proofs_from_THE_BOOK https://en.wikipedia.org/wiki/Proofs_from_THE_BOOK
- vanderZwan 2y ago
  I think you're right, I must have confused the two. I'll edit my comment to reduce the spread of misinformation.
usgroup 2y ago
From the abstract: "... All the current state-of-the-art algorithms are, however, beyond the reach of an undergraduate textbook owing to their reliance on the usage of notions such as pairwise independence and universal hash functions. We present a simple, intuitive, sampling-based space-efficient algorithm whose description and the proof are accessible to undergraduates with the knowledge of basic probability theory ...."
- Sharlin 2y ago
  The point is that the subtitle's is pretty clearly intended to have a dual meaning, it wouldn't be phrased like that otherwise.
- dchftcs 2y ago
  This is really twisting it, I don't find pairwise indepedence to be more advanced than applying a Chernoff bound. In this problem it'd mostly be the difference of using a Cherbyshev type bound or Chernoff bound. Pairwise independence is to give the algorithm stronger guarantees and let it work with a simple hash function like ax+b, otherwise probably most existing algorithms can be simplified in the same way. The most similar algorithm is BJKST, which is almost identical except for specifyimg the sampling mechanism to require less randomness. To someone who worked on this type of thing before, it's like seeing people familar with LLMs say "oh yet another X-billion parameter model on github doing more or less the same".
  - kuldeepmeel 2y ago
    The Chernoff bound needed in this work can be derived from Binomial distribution (with Stirling's approximation); I have worked on pairwise independent hash functions for a decade and every time I introduce such a function, it feels like magic. The notion of pairwise independence is easy to explain but the notion of pairwise independent hash functions isn't. The other strength of our work is that it can work for general settings of sets for which pairwise independent hash functions are not known. Please see: https://dl.acm.org/doi/10.1145/3452021.3458333 https://dl.acm.org/doi/10.1145/3452021.3458333
cschmidt 2y ago
I liked this part. They got Knuth to review it, and found mistakes. That's kind of cool, in its own way. We are deeply grateful to Donald E. Knuth for his thorough review, which not only enhanced the quality of this paper (including fixing several errors) but has also inspired us for higher standards.

kibibu 2y ago

I thought The Book was an Erdos thing. I wonder who used it first.

stevesimmons 2y ago
"During a lecture in 1985, Erdős said, `You don't have to believe in God, but you should believe in The Book.`" https://en.wikipedia.org/wiki/Proofs_from_THE_BOOK https://en.wikipedia.org/wiki/Proofs_from_THE_BOOK
vanderZwan 2y ago
I think you're right, I must have confused the two. I'll edit my comment to reduce the spread of misinformation.

usgroup 2y ago

From the abstract: "... All the current state-of-the-art algorithms are, however, beyond the reach of an undergraduate textbook owing to their reliance on the usage of notions such as pairwise independence and universal hash functions. We present a simple, intuitive, sampling-based space-efficient algorithm whose description and the proof are accessible to undergraduates with the knowledge of basic probability theory ...."

Sharlin 2y ago
The point is that the subtitle's is pretty clearly intended to have a dual meaning, it wouldn't be phrased like that otherwise.
dchftcs 2y ago
This is really twisting it, I don't find pairwise indepedence to be more advanced than applying a Chernoff bound. In this problem it'd mostly be the difference of using a Cherbyshev type bound or Chernoff bound. Pairwise independence is to give the algorithm stronger guarantees and let it work with a simple hash function like ax+b, otherwise probably most existing algorithms can be simplified in the same way. The most similar algorithm is BJKST, which is almost identical except for specifyimg the sampling mechanism to require less randomness. To someone who worked on this type of thing before, it's like seeing people familar with LLMs say "oh yet another X-billion parameter model on github doing more or less the same".
- kuldeepmeel 2y ago
  The Chernoff bound needed in this work can be derived from Binomial distribution (with Stirling's approximation); I have worked on pairwise independent hash functions for a decade and every time I introduce such a function, it feels like magic. The notion of pairwise independence is easy to explain but the notion of pairwise independent hash functions isn't. The other strength of our work is that it can work for general settings of sets for which pairwise independent hash functions are not known. Please see: https://dl.acm.org/doi/10.1145/3452021.3458333 https://dl.acm.org/doi/10.1145/3452021.3458333

cschmidt 2y ago

I liked this part. They got Knuth to review it, and found mistakes. That's kind of cool, in its own way. We are deeply grateful to Donald E. Knuth for his thorough review, which not only enhanced the quality of this paper (including fixing several errors) but has also inspired us for higher standards.