williamkuszmaul

8 ms·

1.
GPT and Claude both subvert shutdown(twitter.com)
12 points by williamkuszmaul 4mo ago|3 comments
2.
Speeding Slows You Down (By a Lot)(algorithmsoup.wordpress.com)
106 points by williamkuszmaul 3y ago|126 comments
3.
by williamkuszmaul 3y ago
Overall seems like a great book. The hashing chapter is a bit half baked though. It claims without reservation that deletions simply cannot be efficiently implemented with linear probing. But there are at least two two efficient to do this
4.
by williamkuszmaul 3y ago
1/100 is too large of a cutoff imo. If you have a class of 96 students, there's a decent chance that an innocent student gets flagged for no reason. I hope he lets the student on the bubble off the hook.
5.
by williamkuszmaul 3y ago
One thing I'm confused about: Did the author try vectorizing the linear search implementation? (Of course, it is possible that even if they did not, the compiler did.) I would imagine that vectorization is behind the advice to use line
6.
by williamkuszmaul 3y ago
Related recent paper in Science: https://www.science.org/doi/10.1126/science.aam9744
7.
by williamkuszmaul 3y ago
One important caveat: it is widely believed that randomization does make a big difference for data structures problems. For example hash tables (which use random hash functions) take O(1) time per operation, but it is conjectured that no
8.
by williamkuszmaul 4y ago
I think it would be fair to say that it's a kind of funny trie-hash-table hybrid. What's neat though is that it manages to achieve better space bounds than either a trie or a hash table would on their own. I didn't invent the
9.
This hash table uses less space than the items it stores(algorithmsoup.wordpress.com)
35 points by williamkuszmaul 4y ago|9 comments
10.
by williamkuszmaul 4y ago
But does the question ever say "all"...?
11.
by williamkuszmaul 4y ago
Unless I'm misreading, the question as stated in the blog post never says there is only one duplicate (there might be many!), so in that sense I think his answer may be wrong. A more robust solution is just to have an array of n counte
12.
by williamkuszmaul 4y ago
Using 64 bit integers, we can store the square of any 32 bit integer. Not that small...
13.
by williamkuszmaul 4y ago
Impressive! There are already implementations of sample sorting that are much faster than c++ sort (but I don't recall how much faster). I'd be very interested in a comparison to some of those... Also, since we are sorting integer
14.
by williamkuszmaul 4y ago
If the coin were unbiased, we could compute the exact probability of getting 10231 or more heads with 20000 flips as: "sum (20000 choose x)/2^20000 for x from 10231 to 20000", which Wolfram Alpha evaluates to 0.00056. The pro
15.
by williamkuszmaul 4y ago
From what I've heard, Perci Diaconis (one of the authors of the original paper) actually could do this. He was a magician before he became a mathematician, and a lot of his early mathematics work focused on math relating to the magic t
16.
by williamkuszmaul 4y ago
I think that many "software companies" are actually marketing companies that plan to make almost all of their profit from a product that has already been built. They're not necessarily a joke... it's just that software e
17.
by williamkuszmaul 4y ago
This is neat! Some if the alternative solutions discussed here seem to confuse compilation with evaluation. Fortran is trying to rewrite the computation in such a way that, later on , a machine that knows nothing about precedence can evalu
18.
by williamkuszmaul 4y ago
In case anyone is wondering, the only role of covid here is that shutdowns prevented technicians from being able to fix the issue in person.
19.
by williamkuszmaul 4y ago
One of the things that's cool about Bzip is that it makes use algorithmic techniques developed by theoretical computer scientists in order to perform the Burrows Wheeler Transform efficiently. It's a great example of theory and pr
20.
by williamkuszmaul 4y ago
One estimation trick that I've found effective is the following: (1) determine the smallest number that your sure is larger than the true answer. (2) determine the largest number that you are sure is smaller than the true answer. (3) t
21.
by williamkuszmaul 4y ago
MIT recently cut all of their relationships with Elsevier journals. Researchers are still allowed to publish in Elsevier, but when they do, even they won't have access to their own articles without going through a paywall. The widesp
22.
by williamkuszmaul 4y ago
I'm not sure why they claim that the total time grows quadratically. If tasks arrive arrive randomly at the same average rate as they can be processed, then the amount of time that the nth task will have to wait is proportional to sqrt
23.
by williamkuszmaul 5y ago
It's even worse than most people seem to realize. For many years the ISO standard for C included the line: "If both operands are nonnegative then the remainder is nonnegative; if not, the sign of the remainder is implementation-de
24.
by williamkuszmaul 5y ago
Another example of this would be if there are three candidates X,Y,Z. Suppose Alice strongly prefers X and Bob strongly prefers Y. Rather than each of Alice and Bob allocating 100 points to their preferred candidate, they can each allocate
25.
by williamkuszmaul 5y ago
It turns out that if you write down on the list of requirements that you would want from a voting system in order for it to be fair, the no deterministic voting system is fair. This is known as Arrow's theorem ( https://en.m.
26.
by williamkuszmaul 5y ago
In my field, at least, I think the problem is less about the medium, and more about the incentives. Researchers are incentivized to write papers that seem impressive (and intimidating) rather than clear and intuitive. To make matters worse,
27.
by williamkuszmaul 5y ago
Here is a (semi)recent paper in Science about the end of Moore's law. As I understand it (but I'm not an expert), Figure 2 seems to give pretty compelling evidence that Dennard scaling (i.e, the phenomenon that historically allowe
28.
by williamkuszmaul 5y ago
Interesting post! Small comment on the argument against anti-aging genes existing: "genes only propagate if selected for, and there’s no selective pressure for longevity after reproductive age" (I know that this was just a very mi
29.
by williamkuszmaul 5y ago
It seems like you may be jumping to conclusions a bit prematurely. The paper ( https://www.cs.unc.edu/~porter/pubs/fast15-final.pdf ) is very explicit that they start with a cold cache. They also go into detail fo
30.
by williamkuszmaul 5y ago
I'm not super familiar with bcachefs, but from what I can find it seems like it is based mostly on a standard (but I guess very well implemented) B-tree. Am I missing something?

More ›