Live data from Hacker News

Computer scientists invent an efficient new way to count

quantamagazine.org

281–290 of 299 posts

Re: Computer scientists invent an efficient new way to count

#281

Earlier quoted context omitted.

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

This doesn’t describe post tenure academia. You seem to be describing the life of a young tenured track academic.

Additionally while Knuth is clearly an outlier by any measure he’s also an outlier in his celebrity. There are a lot Knuths out there who aren’t well known outside their specialty, or are in industry. He played a seminal role in a field everyone studies in computer science and published a uniquely interesting and continuously revised set of fundamental books in the field. However in my time in academics there were people in say transactional memory for speculative out of order compute whose work powers every machine in use today and they still contribute similarly powerful work. They’re obsessive and very driven by the problem space. But for everyone one of those in academia there are a hundred tenured professors who paper mill their undergrads (generously).

You mention long hours but I said obsessive. That’s orders of magnitude more than working hard. It’s so distorted as to be pathological if they weren’t paid and rewarded for it. Yes many academics are pathologically obsessive. But unless they are bringing in funding or repute to fill a deficit in the department, there’s no work for them in current academic settings.

Finally Knuth isn’t a common occurrence because -he doesn’t bring in money-. Modern academia is oriented towards grant milking. The example of the txn memory guy is interesting because he brings in lots of research funding from intel and ARM and NVidia because his work is very commercial. Knuth - not so much I imagine. He brings repute, but you can only find so much repute with modern academic funding models before they’re a net negative on the department. Knuth is a fossil of a different era in academics (not used as a pejorative).

Re: Computer scientists invent an efficient new way to count

#282

Earlier quoted context omitted.

You are envious of him. Jealous is when you possess something you don’t want taken away by someone else

Well, that use of jealousy is only really common in certain romantic situations. Like if some super good looking dude hits on your girl and she responds in an ambiguously-flirty way, you might definitely be said to be jealous, even though she didn't run off with him. In most other domains, though, like this one, jealousy and envy are synonyms. https://www.merriam-webster.com/dictionary/jealousy#did-you-...

I read that link as supporting the distinction, not refuting it: "It is difficult to make the case, based on the evidence of usage that we have, [that they are] exact synonyms [or] totally different words."

An envious person would be happier having something that someone else also has. A jealous person feels threatened that someone else has or wants something. This distinction applies in romantic and non-romantic contexts. Both emotions can arise, for example, when someone observes someone else wanting something neither of them has, or when the thing wanted is inherently exclusive.

I don't lose a lot of sleep worrying about others' use or misuse of these words. But I do think it's essential for people to understand which of the two emotions they're having, because the solution really depends on that. Would I be happy if I destroyed that other kid's toy? (That's jealousy.) Would I be happy if my dad showed up and gave me a similar toy, so that the other kid and I could play together? (That's envy.)

Re: Computer scientists invent an efficient new way to count

#283

Earlier quoted context omitted.

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

> 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.

This kind of stuff is not useful to be posting where impressionable people (young students) can read it. The truth the majority of academics are managers and delegate hands-on work to postdocs and PhD students. I finished a PhD just last month and I never saw in 4 years anyone on my committee so much as look at code let alone write it (and I was not a theory student). Almost everyone in my cohort would echo this observation.

Re: Computer scientists invent an efficient new way to count

#284

Earlier quoted context omitted.

Actually quick is definitely something that comes to mind. Quick in politics is of course relative, but the speed with which he has enacted major changes (for example marijuana legalization) is pretty quick in the realm of politics when congress is of the other party.

He’s barely able to read a teleprompter, not too confident that Biden himself enacted those changes.

We've had nearly 4 years with no scandals and emerged from the pandemic with the best economic recovery of any country, and despite having no margin to spare in Congress, master legislator Joe Biden has secured massive climate change, infrastructure, and gun control bills, not to mention he's ended our two decade war in Afghanistan and overseen the fastest wage growth of the two lowest income quintiles seen in modern history.

And every time people actually watch him speak (not just a selected clip), there's weeks of coverage about how alive JB seems, not recognizing that all evidence points to that being typical.

Re: Computer scientists invent an efficient new way to count

#288

With other count-distinct algorithms, you can do unions and intersections on the "sets". (theta sketches, even bloom filiters) Can you do this with CVM?

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/3452021.3458333

Re: Computer scientists invent an efficient new way to count

#289

This algorithm seems to resemble HyperLogLog (and all its variants), which is also cited in the research paper. Using the same insight of the estimation value of tracking whether we've hit a "run" of heads or tails, but flipping the idea on its head (heh), it leads to the simpler algorithm described, which is about discarding memorized values on the basis of runs of heads/tails. This also works especially well (that…

You could merge these data structures as well. If the two instances to be merged are not at the same "round", take the one that's at an earlier round and advance it (by discarding half the entries at random) by the difference in rounds. Then just insert the values from one list to the other, ignoring duplicates; if the result is too large, discard half at random and increment the round number. I implemented exactly t…

Merging like that doesn't work -- it will tend to overestimate the number of distinct elements.

This is fairly easy to see, if you consider a stream with some N distinct elements, with the same elements in both the first and second halves of the stream. Then, supposing that p is 0.5, the first instance will result in a set with about N/2 of the elements, and the second instance will also. But they won't be the same set; on average their overlap will be about N/4. So when you combine them, you will have about 3N/4 elements in the resulting set, but with p still 0.5, so you will estimate 3N/2 instead of N for the final answer.

I have a thought about how to fix this, but the error bounds end up very large, so I don't know that it's viable.

Re: Computer scientists invent an efficient new way to count

#290

Earlier quoted context omitted.

The blog post was more than half padding. Good that the algorithm is so simple it's hard to write a full length blog post about it!

And yet the blog post still got it wrong: > Now you move forward with what the team calls Round 1. Keep going through Hamlet, adding new words as you go. If you come to a word that’s already on your list, flip a coin again. If it’s tails, delete the word; heads, and the word stays on the list. Proceed in this fashion until you have 100 words on the whiteboard. Then randomly delete about half again, based on the outco…

Yeah, I noticed the same thing. Quanta's version of the algorithm is not only confusing, it's also wrong.

I think the pseudocode in the paper is very hard to beat.

Post reply on HN