thomasahle

3 ms·

1.
by thomasahle 5d ago
Yes, a good example is tabulation hashes which is h(x1, x2, ...) = T[1, x1] ^ T[2, x2] ^ ... but most fast hashes are actually algebraic, typically using polynomials in some way. I'm not sure they fit into the same pattern?
2.
by thomasahle 5d ago
Non-cryptographic hashing should not mean "no guarantees". Unfortunately it's very hard to empirically test if a pseudorandom function works well on all inputs. We analyzed 30 popular hashes and found Key-independent collisio
3.
Claude Found Seed-indpendent collisions in most popular hash functions(thomasahle.com)
6 points by thomasahle 6d ago|0 comments
4.
by thomasahle 8d ago
Also Bada
5.
by thomasahle 8d ago
> Where this differs from Bend is that what we have supplied here is everything required to prove the correctness of the program, without having a LLM waste time and tokens on building up a 442 line proof from first principles. We can ru
6.
by thomasahle 15d ago
Sorry I meant P_i = x_{2i} + (x_{2i+1} + z^3)(P_{i-1} + z^2)
7.
by thomasahle 15d ago
I'm happy to take a PR if you have a good layout in mind!
8.
by thomasahle 15d ago
> Hopefully that answers your question about why someone might still choose to use heuristic hashing Not really. Our method is also 2x faster than xxh3. Sure, AES make the heuristic hashes harder to break, but they still provide (1) slow
9.
by thomasahle 16d ago
It's true that you can use AES instructions now on some computers, bit I honestly don't see why you'd use a heuristic hash (even if cryptographic) when you can get provable guarantees with k-wise independent hashing. Our pape
10.
by thomasahle 16d ago
I'm not sure, since we only do univariate polynomials and k-path has lots of variables, right? But maybe this work can inspire looking for other small, constant factor saving circuits for different classes of polynomials. Would be cool
11.
by thomasahle 16d ago
> the "universality" property of such hashes seldom provides any substantial benefit over alternative hash functions that do not have this property Do you mean hashes like xxh3? We have a section in the paper showing for a bunc
12.
by thomasahle 16d ago
It's the blessing and the course of a polynomial inverse: the inverse is the same degree as the polynomial, so its largest coeffecient is large and blows up. Knuth-Eve and Pan use the root of a degree d polynomial, which is slightly l
13.
by thomasahle 16d ago
> This method requires additional preprocessing of the coefficients, before starting to evaluate the polynomial. That preprocessing would slow the hashing algorithm more than what is gained during evaluation. There is no preprocessing at
14.
by thomasahle 16d ago
See also discussions here https://www.reddit.com/r/programming/comments/1wbgcke/commen... on how the actual math works out.
15.
by thomasahle 16d ago
Thank you! It was a lot of fun to make the website and see all the methods in practice after having just looked at the theory for a long time :D > have a separate source node for each x, x^2, x^4 used Do you mean a graph like this R&
16.
by thomasahle 16d ago
FFT multipoint evaluation is great when you know all the evaluation points in advance. However, for many practical applications the input is only streamed to you. E.g. a polynomial hash for a hashmap. Or preprocessing the taylor approximati
17.
by thomasahle 16d ago
In CRC8 you interpret the input as coefficients of a polynomial, and take mod `x⁸ + x² + x + 1`. The problem we solve here is a bit different: You know the coefficients in advance, and want to preprocess the polynomial to make it fast to ev
18.
by thomasahle 16d ago
If you are working over floating point, you probably with to use Estrin's method (see https://en.wikipedia.org/wiki/Estrin%27s_scheme - also tab 3 on the website.) It takes advantage of FMA (fused multiply add), h
19.
by thomasahle 16d ago
I don't know what happened to the URL, but it's supposed to link to this paper: https://www.gwizfl.org/email/cr.yp.to/antiforgery/pema-20071... It's a very nice construction (based on Rabin &am
20.
by thomasahle 16d ago
WyHash and xxh3 are not polynomial, in fact this is one of the issues we try to solve in the paper. Many "practical" hashes use heuristics instead of real field multiplications to be faster. But it means they are vulnerable to adv
21.
by thomasahle 17d ago
It's surprising that in 2026 they still haven't figured out how to remove the bezels. They are smaller than they used to be, but On something as compact a watch, all screen estate counts.
22.
by thomasahle 17d ago
They charge you 23%? I thought in the EU the maximum interchange fee for consumer credit cards is capped at 0.3% of the transaction value.
23.
Show HN: Compute polynomials twice as fast(thomasahle.com)
139 points by thomasahle 17d ago|42 comments
24.
by thomasahle 19d ago
1) That's maybe $180,000 per year, so much less than median OpenAI employee wages. 2) OpenAI doesn't pay API prices. 3) Compute costs are likely already their biggest expense, dwarfing wages.
25.
by thomasahle 21d ago
Do you want people here to try to convince you to have kids?
26.
by thomasahle 21d ago
Yes please. For a moment I thought Terrence Tao had scooped Anthropic.
27.
by thomasahle 23d ago
• 98.6% on ARC-AGI-3 • 97.6% on frontier math • 95.9% on CAD • 100% on ExploitBench Nothing modest about it
28.
by thomasahle 1mo ago
> Grades should come from hard randomized exams with unlimited retakes Exams will have to be a lot longer if you allow unlimited retakes. Generally exams work on a sample principle, but this breaks with retakes.
29.
by thomasahle 1mo ago
> had similar (slightly higher) performance. The data point around 80 minutes seems like noise to me. Looks like there isn't enough data/students who spend that much time and also used AI. It would be nice if AI was a force for
30.
by thomasahle 2mo ago
Has anyone started proving their sandboxes in Lean (or Coq, etc.)?

More ›