Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Computer scientists invent an efficient new way to count

quantamagazine.org

Post reply on HN
Print view View original

271–280 of 299 posts

Re: Computer scientists invent an efficient new way to count

#271

Post by kuldeepmeel »

dchftcs wrote: post #89
usgroup wrote: post #68

Earlier quoted context omitted.

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…

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 mos…

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

Re: Computer scientists invent an efficient new way to count

#272

Post by helix278 »

j_m_b wrote: post #257

I jumped on the code generation bandwagon pretty soon after ChatGPT was released. I like to think of similar to a catalyst in a chemical reaction, it lowers the activation barrier to writing code, especially in new contexts (to you). It makes it easier to just get started. However, it struggles with solving actual problems or even putting together the right context. If you know how to break the problem down to simple…

Wrong thread?

Re: Computer scientists invent an efficient new way to count

#273

Post by kuldeepmeel »

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/papers/cvm-note.pdf

Talk Slides: https://www.cs.toronto.edu/~meel/Slides/meel-distinct.pdf Talk Video: https://www.youtube.com/watch?v=K_ugk7OW0bI

The talk also discusses the general settings where our algorithm resolved the open problem of estimation of the union of high dimensional rectangles.

Re: Computer scientists invent an efficient new way to count

#274

Post by samatman »

aidenn0 wrote: post #220
samatman wrote: post #186

Earlier quoted context omitted.

IEEE 754 defines an exact binary result for the addition of any two floats. That this bit-identical result is not the same operation as addition of real numbers is irrelevant, because floats aren't reals. f1 + f2 is not an estimation. Even treating it as an approximation will get you into trouble. It's not that either, it's a floating-point result, and algorithms making heavy use of floating point had better understa…

Cool, so next time I have numbers that aren't reals to perform math on, I can use floats.

Or if you have numbers that aren't integers to perform math on, you can use integers.

It's not a new problem, and it isn't specific to floats. Computers do discrete math. Always have, always will.

Re: Computer scientists invent an efficient new way to count

#275

Post by fnordpiglet »

MaxBarraclough wrote: post #252
almostgotcaught wrote: post #205

Earlier quoted context omitted.

> He recognized patterns in minutes that would take me days, if not weeks, to recognize... he actually writes and runs code, overnight if need be 70-80 years of actually being hands-on and i bet you'd be pretty quick too. dude is definitely naturally "gifted" but it seems pretty obvious being hands-on has a lot to do with it.

Disagree, there are thousands of highly experienced and hard-working computer scientists. If we grant that very few of them are the equivalent of Knuth, there must be something else at play.

Most computer scientists I know at that age don’t touch a computer any more and hang with grand kids. That’s not a value judgement - Knuth is impressive but as a human being most people choose their humanity over their careers in some way. Beyond being simply smart and productive knuth is also likely obsessive about his work and his life is warped around it. As long as that works for everyone that’s great. But most people don’t live that life.

Re: Computer scientists invent an efficient new way to count

#276

Post by fnordpiglet »

mc32 wrote: post #261
throw10920 wrote: post #230

Earlier quoted context omitted.

> Biden's been hands-on in his domain for over 50 years, yet "quick" is definitely not the word that comes to most people's mind when they think of him nowadays. Please don't post flamebaity political tangents on HN. > Eschew flamebait. Avoid generic tangents. https://news.ycombinator.com/newsguidelines.html

It’s a counterpoint anyone can identify with. One can interpret it uncharitably as flame bait if one wants to, but it need not be. It could have been Reagan in his second term, but some may not know who he was. Or Lee Smolin.

I’d avoid the Reagan or other comparison as well even if I have medical evidence for their decline as you see with Reagan. In this specific case of Biden there’s not even that so it’s purely a political opinion and it’s definitely bait for flame even if not intended as such.

Re: Computer scientists invent an efficient new way to count

#277

Post by MaxBarraclough »

fnordpiglet wrote: post #275
MaxBarraclough wrote: post #252

Earlier quoted context omitted.

Disagree, there are thousands of highly experienced and hard-working computer scientists. If we grant that very few of them are the equivalent of Knuth, there must be something else at play.

Most computer scientists I know at that age don’t touch a computer any more and hang with grand kids. That’s not a value judgement - Knuth is impressive but as a human being most people choose their humanity over their careers in some way. Beyond being simply smart and productive knuth is also likely obsessive about his work and his life is warped around it. As long as that works for everyone that’s great. But most p…

> Most computer scientists I know at that age don’t touch a computer any more and hang with grand kids.

That doesn't sound right to me at all. Modern academia is highly competitive, and career academics typically have long working hours.

If they aren't doing programming, that's likely because it isn't relevant to their job. A theoretical computer scientist is closer to a mathematician than to a typical programmer.

> Knuth is impressive but as a human being most people choose their humanity over their careers in some way

We're talking about scientists, not most people.

Getting a PhD is no cakewalk, and there are far more PhDs than faculty positions. You can try being a workaholic, but if your competitors are doing the same, that won't make you stand out.

> obsessive about his work and his life is warped around it

Again this describes every modern scientist. Deep knowledge of one's field, and deep commitment to it, are just table stakes.

Re: Computer scientists invent an efficient new way to count

#278

Post by kuldeepmeel »

zero_k wrote: post #202
jandrese wrote: post #198

Earlier quoted context omitted.

So now we have you to blame for a delay on the release of his next book. :)

Not me, the authors -- I'm a fly on the wall compared to them ;) This is some serious work, I just did a fast implementation. Re implementation -- it turns out that there are parts of some standard libraries that this problem pushes to its limits, that we had to go around during implementation. So there were still some cool challenges involved. I was also pretty happy about the late binding/lazy evaluation thing I ca…

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

Re: Computer scientists invent an efficient new way to count

#279

Post by shkkmo »

throwaway290 wrote: post #244
shkkmo wrote: post #189

Earlier quoted context omitted.

Counting is a subset of estimation, not a synonym. If I estimated the number of quarters in a stack by weighing them, that would be different from estimating the number of quaters in a stack by counting them. Both methods of estimation have error bars. The list you provide is of categories that don't have clear definitions. If you have a sufficiently clear definition for a category given your population, it has a pre…

It's close enough to counting for the purposes of a magazine article like uuids are close enough to being unique for the purposes of programming.

The algorithm accuracy scales with the ratio of memory to set size so you don't actually know if it is "close enough" without an estimate of of the set size.

I think the headline is clickbaity and the article makes no effort to justify it's misuse of the wors 'counting'. The subheadline is far more accurate and doesn't use that many more words.

Re: Computer scientists invent an efficient new way to count

#280

Post by lokar »

throwaway14356 wrote: post #231
lokar wrote: post #229

Earlier quoted context omitted.

You want every distinct item to have the same chance at the end. So when items repeat you need to reduce (not increase) the odds of keeping any given occurrence.

does that mean you could also split the set in half multiple times then run it on each half of a half (etc) and combine it with its other half? that would seem simpler to me. edit: oh but then you would need to keep the results which defeats the purpose

You would need to assume a uniform distribution of items, which I don’t think this does
Post reply on HN