Viewing profile — kuldeepmeel

Unfortunately, not, and that's an interesting open problem as other count-distinct algorithms don't work for "structured sets", while this one does. https://dl.acm.org/doi/10.1145/…

I agree with zero_k on everything he said about Knuth and strongly disagree with his own (extremely modest) characterization of himself.

We are very grateful for the interest, and I thought I would link to some relevant resources. Paper: https://arxiv.org/pdf/2301.10191 Knuth's note: https://cs.stanford.edu/~knuth/p…

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 …

I fully agree with you and this is indeed one of my criticisms of modern academic writing -- we tend to write papers that are just very hard for anyone to read. So delta refers to …

You are indeed right; while has the added advantage of making the estimator unbiased -- i.e., not only strongly (epsilon,delta)-guarantees but also having an expectation of being c…

Yes, there is an error in the Quanta article [at the same time, I must add that writing popular science articles is very hard, so it would be wrong to blame them] Your fix is indee…

The following is also not correct. if k not in mem: mem += [k] if k in mem: # not the same than "else" here if np.random.rand() > p: mem.remove(k) Your final solution is indeed cor…

[I am one of the authors]. We have a follow-up work (admittedly, more technical) that can remove reliance on m completely: https://www.cs.toronto.edu/~meel/Papers/pods22.pdf But ye…